无法围绕枢轴旋转

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   

然后你继续下一旋转，如图中所述。