Rééquilibrer une arborescence AVL

Question

J'ai l'arborescence AVL suivante:

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9

Si j'insère 3, j'obtiens:

                               10
                             /    \
                            5     12
                           / \   /  \
                          2  8   11  13
                        /  \ /\   
                        1  4 7 9
                          /
                         3

Si je calcule le facteur d'équilibre pour chaque nœud, il semble que chaque BF est valide: (Nœud: BF) -> 10: 1, 5: 0, 2: -1, 1: 0, 4: -1, 8: 0, 7: 0, 9: 0, 3: 0, 12: 0, 11: 0, 13: 0 Mais apparemment, cet arbre a besoin d'être rééquilibré.Où y a-t-il un BF invalide et comment procéder pour effectuer les rotations nécessaires.

Answer 1

10 devrait avoir un facteur d'équilibre de 2 avec son sous-arbre gauche 5-2-4-3 et son sous-arbre droit 12-13.Un arbre valide après une seule rotation pourrait ressembler à 5 |2 10 |1 4 8 12 |néant néant 3 néant 7 9 11 13.

Une méthode possible de rééquilibrage est l'algorithme cut-link-algorithm: 1. Nommez le nœud z déséquilibré, l'un de son enfant y et l'autre de son enfant x. 2. Renommez les nœuds en a, b, c en traversée en ordre et laissez leurs enfants être T0, T1, T2 et T3 de gauche à droite. 3. Définissez b comme nouvelle racine, a comme enfant gauche et c comme enfant droit. 4. Ajoutez les quatre sous-arborescences correspondant de gauche à droite comme T0, T1, T2 et T3.