AVL樹餘額

Question

我已經實現了AVL樹，但是我遇到了問題。

假設我有以下三種：

，加入另一個節點後：

現在我必須旋轉節點5至左：

但旋轉後，仍然不平衡。

我在哪裏犯錯？

Answer 1

所示場景符合左右案例來自this的說明。

您的錯誤是您一次旋轉不平衡節點（5），而沒有先執行其子樹的旋轉。

一般有P的不平衡節點，L作爲其左子樹和R作爲其右子樹下面的規則應遵循在插入：

balance(N) = Depth(Nleft) - Depth(Nright) 

if (balance(P) > 1) // P is node 5 in this scenario 
{ 
    if (balance(L) < 0) 
    { 
     rotate_left(L); 
    } 

    rotate_right(P); 
} 
else if (balance(P) < -1) // P is node 5 in this scenario 
{ 
    if (balance(R) > 0) // R is node 11 in this scenario 
    { 
     rotate_right(R); // This case conforms to this scenario 
    } 

    rotate_left(P);  // ... and of course this, after the above 
} 

所以有時兩個旋轉需要要執行，有時只有一個。

這是很好的可視化在Wikipedia：

最上面一行顯示的情況時，需要兩個旋轉。當一次旋轉就足夠時，中間行呈現可能的場景。額外的輪轉將任何頂行場景轉換爲中行場景。

特別是，此樹：

7之後：

的5餘額爲2。這符合上面在僞代碼中註釋的方案，也符合維基百科圖片中的頂行方案（右圖）。所以5前左旋轉，右子樹11需要是右旋：

它變成：

只是現在，它的簡單情況（維基百科圖片中的中間行右方案）通過一個左旋轉來恢復餘額5：

，樹再次變爲平衡：

Answer 2

讓我試圖更全面地分析， 對於二叉樹爲AVL樹，從任何最左邊的葉各節點的高度差到任何最右邊的葉必須位於{-1,0,1}內。

插入爲AVL：

有四種情況爲AVL插入 - L - 大號 L - - [R 的R - - [R - [R L -

現在， 情況（a）。 [如果平衡> 1] LL（左 - 左）節點X違反了{-1,0,1}約束條件，並且 的左高度高於右 - 給出L 的左邊第一個左子女Y的左高度大於右..再次L 動作 - 順時針旋轉Y.即。 右轉一圈。 （b）（L -R case）假設要插入一個Z節點，對於Z，它首先被評估，放在哪個葉子左邊或右邊。對，如果更多的重量，如果重量較輕，就留下。假設Z'，新節點wt（Z'）> wt（Z），即Z'作爲Z的右子插入，L-R的情況下，整個鏈路ZZ'逆時針旋轉，現在它是LL情況，因此使用上述情況（a）解決。即。 一左一右旋轉。 （c）[如果餘額爲< -1]（R-R case）同樣，R-R情況下，簡單地應用二進制搜索規則進行調整並且這種情況起作用。即。 左轉一圈。 （d）（R-L情況）首先轉換爲R-R情況，並因此使用上述情況（c）解決。即。 一右一再左轉一圈。