множественное вращение дерева AVL

Question

Скажем, у меня есть неупорядоченный набор s {3,6,5,1,2,4}, и мне нужно построить дерево AVL,это хорошо ... я понимаю основные повороты, и я дохожу до этого:

                               5 
                             /   \
                            2      6
                           / \
                         1     3

, но все это разваливается, когда я пытаюсь вставить 4, и я получаю свой окончательный ответ как (левый)

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

И когда я ломаю его, я застреваю, делая то же самое вращениепоэтому я спрашиваю, как мне сделать ротацию с родителем, который действителен для этого AVL?

и действительно ли мое решение действительно?

Answer 1

Ну, насколько я понимаю, когда вы впервые добавляете 4, вы получаете следующее дерево.

    5
   / \
  2   6
 / \
1   3
     \
      4

Чтобы следовать, обратитесь к статье Википедии о деревьях AVL .Поскольку коэффициент баланса (обратите внимание, что это определено в статье) узла 5 равно +2, а коэффициент баланса узла 2 равен -1, сначала необходимо повернуть поддерево узла 2 влево.

      5
     / \
    3   6
   / \
  2   4
 /
1

Далее вам нужно повернуть все дерево вправо (около узла 5).

    3
   / \
  2   5
 /   / \
1   4   6

Имеет ли это смысл?