多個AVL樹輪轉

Question

說我有一個無序集合{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 

要繼續，請參閱Wikipedia's article on AVL trees。由於節點5的平衡因子（請注意，這在文章中定義）爲+2，節點2的平衡因子爲-1，因此首先需要將節點2子樹左旋。

 5 
    /\ 
    3 6 
/\ 
    2 4 
/
1 

接下來，您需要旋轉整個樹（關於節點5）。

3 
/\ 
    2 5 
//\ 
1 4 6 

這有道理嗎？