algorithm - 不能绕枢轴旋转

Question

我正在尝试将一个新值插入到 AVL 树中。新的插入导致不平衡(根据Wikipedia上的文章，这应该属于左右情况)，因此需要旋转。然而，在目前的情况下，轮换是不可能的，因为两个 child 最终都变得比 parent 还小:

           15
         /    \
        10    27
       /  \      
      8   12

现在如果我想插入 11，结构就会变得不平衡:

           15
         /    \
        10    27
       /  \      
      8   12
         /
        11

由于左子树更长，而左子树有更长的右子树，根据维基百科的图表，这应该属于左右情况。但是，元素 4 有左子树和右子树，这使得旋转成为可能。但在这里，由于 12 只有左子树，旋转使它看起来像:

           15
         /    \
        12    27
       /  \      
      10   8
         /
        11

导致 12 的两个 child 都小于 12。我在这里做错了什么？

Answer 1

你似乎旋转错了。唯一具有错误平衡因子的节点是根，因此您围绕它旋转。

这种情况涉及检查 10(根的左 child )的平衡因子:它是 -1，所以我们需要两个不同的旋转(左右情况)。

首先，我们按照这张图片的左上部分向左旋转 10 度:

所以我们得到:

           15
          /  \
         12  27
        / 
       10    
      /  \
     8   11           

然后按照图片中的描述继续下一个旋转。