重新平衡AVL樹

Question

我有以下AVL樹：

       10 
          / \ 
          5  12 
         /\ /\ 
          2 8 11 13 
         /\ /\ 
         1 4 7 9 

如果我插入3然後我得到：

       10 
          / \ 
          5  12 
         /\ /\ 
          2 8 11 13 
         /\ /\ 
         1 4 7 9 
         /
         3 

如果我計算的平衡因子爲每個節點似乎每BF是有效的： （節點：BF）→10：1,5：0,2：-1,1：0,4：-1,8：0,7：0,9：0,3：0,12 ：0，11：0,13：0 但顯然這棵樹需要重新平衡。哪裏有無效的BF，然後怎麼去做必要的旋轉。

Answer 1

10應該有一個平衡因子2與它的左子樹5-2-4-3及其右子樹12-13。一次旋轉後的有效樹可能看起來像5 | 2 10 | 1 4 8 12 | nil nil 3 nil 7 9 11 13.

一種可能的重新平衡方法是切割鏈接算法： 1.將非平衡節點z命名爲它的一個子節點y和它的一個子節點x。 2.將節點重命名爲a，b，c inorder-traversal，並讓其子節點從左到右依次爲T0，T1，T2和T3。 3.將b設置爲新的根，a作爲其左側的孩子，c作爲其右側的孩子。 4.將從左到右對應的四個子樹追加爲T0，T1，T2和T3。