AVL Tree Rotation的

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 

二， right rotation是整個樹進行：

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

第二個答案是不正確只是因爲它沒有保存元素的順序。