Remplacement de la méthode insert

Insérer un élément dans un arbre AVL revient à l'insérer dans un BST, sauf que l'arbre peut avoir besoin d'être rééquilibré. Un nouvel élément est toujours inséré en tant que nœud feuille. Suite à l’ajout d’un nouveau nœud, la hauteur des ancêtres du nouveau nœud feuille peut augmenter. Après avoir inséré un nouveau nœud, vérifiez les nœuds le long du chemin depuis le nouveau nœud feuille jusqu'à la racine. Si un nœud déséquilibré est trouvé, effectuez une rotation appropriée en utilisant l'algorithme dans le code ci-dessous.

1 balancePath(E e) {
2 Obtenez le chemin du nœud qui contient l'élément e jusqu'à la racine,
3 comme illustré sur la figure 26.9 ;
4 pour chaque nœud A du chemin menant à la racine {
5 Mettez à jour la hauteur de A ;
6 Soit parentOfA désignant le parent de A,
7 qui est le prochain nœud du chemin, ou null si A est la racine ;
8
9 commutateur (balanceFactor(A)) {
10 cas -2 : si balanceFactor(A.left) == -1 ou 0
11 Effectuer la rotation LL ; // Voir Figure 26.2
12 autres
13 Effectuer la rotation LR ; // Voir Figure 26.4
14 pause ;
15 cas +2 : si balanceFactor(A.right) == +1 ou 0
16 Effectuer la rotation RR ; // Voir Figure 26.3
17 autres
18 Effectuer une rotation RL ; // Voir Figure 26.5
19 } // Fin du switch
20 } // Fin de pour
21 } // Fin de la méthode

L'algorithme considère chaque nœud sur le chemin allant du nouveau nœud feuille à la racine. Mettez à jour la hauteur du nœud sur le chemin. Si un nœud est équilibré, aucune action n’est nécessaire. Si un nœud n'est pas équilibré, effectuez une rotation appropriée

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!