Mise en œuvre des rotations

Un arbre déséquilibré devient équilibré en effectuant une opération de rotation appropriée. La section Rééquilibrage des arbres illustre comment effectuer des rotations au niveau d'un nœud. Le code ci-dessous donne l'algorithme de rotation LL, comme illustré dans la figure ci-dessous.

1 soldeLL(TreeNode A, TreeNode parentOfA) {
2 Soit B l'enfant gauche de A.
3
4 si (A est la racine)
5 Soit B la nouvelle racine
6 autres {
7 si (A est un enfant gauche de parentOfA)
8 Soit B un enfant gauche de parentOfA ;
9 autres
10 Soit B un bon enfant de parentOfA ;
11>
12
13 Faites de T2 le sous-arbre gauche de A en attribuant B.right à A.left;
14 Faites de A le bon enfant de B en attribuant A à B.right ;
15 Mettre à jour la hauteur du nœud A et du nœud B ;
16 } // Fin de la méthode

Notez que la hauteur des nœuds A et B peut être modifiée, mais les hauteurs des autres nœuds de l'arborescence ne sont pas modifiées. Vous pouvez mettre en œuvre les rotations RR, LR et RL de la même manière.

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!