無法圍繞樞軸旋轉

Question

我正嘗試在AVL樹中插入新值。新的插入導致不平衡（根據Wikipedia上的文章，這應該屬於左右情況），因此需要輪換。然而，它是不可能在當前形勢下旋轉，因爲兩個孩子變得比父母更小的結束：

  15 
     / \ 
     10 27 
    /\  
     8 12 

現在，如果我想插入11，結構變得不平衡：

  15 
     / \ 
     10 27 
    /\  
     8 12 
     /
     11 

由於左子樹較長，並且左子樹具有較長的右子樹，根據維基百科圖，這應該屬於左右情況。但是，在那裏，元素4同時具有左右子樹，因此可以旋轉。但在這裏，因爲12只有左子樹，旋轉使它看起來像：

  15 
     / \ 
     12 27 
    /\  
     10 8 
     /
     11 

導致12比12少兩個孩子我在做什麼錯在這裏？

Answer 1

你似乎在旋轉錯誤。唯一具有錯誤平衡因子的節點是根，所以你圍繞它旋轉。

這種情況涉及檢查10（根的左孩子）的平衡因子：它是-1，所以我們需要兩個不同的旋轉（左 - 右情況）。

首先，我們大約10向左旋轉，按這一形象的左上部分：

所以我們得到：

  15 
     /\ 
     12 27 
     /
     10  
    /\ 
    8 11   

然後你繼續下一旋轉，如圖中所述。