algorithm - 不能绕枢轴旋转

Question

我正在尝试将新值插入AVL树中。新的插入会导致不平衡（根据维基百科上的文章，这应该属于左右情况），因此需要旋转。但是，在当前情况下不可能轮换，因为两个孩子最终都变得比父母小：

           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           

然后您继续下一个旋转，如图像中所述。