AVL Tree Rotation's

Question

Просто быстрый вопрос об деревьях avl. Если бы я это дерево:

27 
/\ 
    9 50 
/\ 
2 15 
     \ 
     21 

Почему балансировать на этот ответ ?:

15 
/\ 
    9 27 
//\ 
2 21 50 

Вместо этого (или оба они действительны?):

21 
/\ 
    15 27 
/\ \ 
2 9 50 

Answer 1

Согласно к алгоритму восстановления для дерева AVL балансировка выполняется в два этапа:

I. left rotation сделано для левого поддерева:

|    | 
    9    15 
/\   /\ 
2 15 => 9 21 
    \  /
     21  2 

II. right rotation делается для всего дерева:

 27   15 
    /\  /\ 
    15 50 => 9 27 
/\  //\ 
    9 21  2 21 50 
/
2 

Второй ответ просто неверно, так как она не сохранила порядок элементов.