如果AVL树既是right-right case又是right-left case，应该如何旋转？

Question

下图中的AVL树是去掉子树T0中的一个叶子节点生成的

删除节点后，树变得不平衡。

我应该将以下情况视为右例还是右例？

Answer 1

这是一个Right-Right的情况，因为节点𝑦的平衡因子不是负的（它是零）。

维基百科关于 AVL 再平衡 的部分列出了这些可能性，但请注意节点的标记不同：

令 X 为具有（临时）平衡因子 −2 或 +2 的节点。它的左子树或右子树被修改了。让 Z 成为更高的孩子 [...]

• Right Right ⟹ Z 是其父 X 的右孩子并且 BF(Z) ≥ 0
• [...]
• Right Left ⟹ Z 是其父 X 和 BF(Z) 的右孩子 < 0

使用你的树的标签，你会这样想象它：

        ____44____             BF(X): 2
       /    X     \
     17          __62__        BF(Z): 0
    /  \        /  Z   \
   10  21   __50_       78
           /     \     /  \
         48      54   72  88
        /  \    /  \     /  \
       45  49  52  56   81  92

所以我们处于第一种（即对对）的情况下。

维基百科继续采取行动：

重新平衡的执行方式不同：

• 右右⟹X通过简单的旋转重新平衡

  rotate_Left

这个简单的旋转将给这棵树：

          ____62____
         /    Z     \
     __44__          78
    /  X   \        /  \
  17      __50_    72   88
 /  \    /     \       /  \
10  21  48      54    81  92
       /  \    /  \
      45  49  52  56