multiple rotation de l'arbre AVL

Question

Dire que j'ai un ensemble de {3,6,5,1,2,4 non ordonnée} et j'ai besoin de construire un arbre AVL,
ce bien est très bien ... je comprends les rotations de base et je reçois ce point ici:

                               5 
                             /   \
                            2      6
                           / \
                         1     3

mais tout se désagrège quand je tente d'insérer 4 et je reçois ma réponse finale (celle de gauche)

             4      But the actual answer is:      3
           /   \                                 /   \
          2     5                               2     5
         / \     \                             /     / \
        1   3     6                           1     4   6

Et quand je le décomposer je suis bloqué à faire la même rotation
donc im demander comment puis-je faire une rotation avec le parent qui est valide pour cette AVL?

et est ma solution valable?

Answer 1

Eh bien, si je comprends bien, quand vous ajoutez 4 vous obtenez l'arbre suivant.

    5
   / \
  2   6
 / \
1   3
     \
      4

Pour suivre, reportez-vous à l'article de Wikipédia sur les arbres AVL . Parce que le facteur d'équilibre (notez que cela est défini dans l'article) du nœud 5 est 2 et le facteur d'équilibre du noeud 2 est -1, vous devez d'abord faire tourner le nœud 2 sous-arbre gauche.

      5
     / \
    3   6
   / \
  2   4
 /
1

Ensuite, vous devez faire pivoter l'ensemble de droite de l'arbre (environ 5 nœuds).

    3
   / \
  2   5
 /   / \
1   4   6

Est-ce logique?