平衡时AVL树中的右右旋转和右左条件如何选择

Question

我有这个AVL树：

 5
  \
  15
 /  \
10  20

父节点5是不平衡节点，两种旋转条件都存在：

1. 从 5-15-20 向右旋转
2. 从 5-15-10 左右旋转

那么选择哪一个以及为什么我们可以针对这两种情况进行轮换？

Answer 1

在 AVL 树上的标准操作过程中，可能会出现四种可能的平衡违规变体。正如维基百科还列出的那样：

令 X 为（临时）平衡因子为 −2 或 +2 的节点。它的左子树或右子树被修改。令 Z 为具有较高子树的子节点（见图 2 和图 3）。

[...]

违规行为有四种可能的变体：

• Right Right ⟹ Z 是其父 X 的右子节点且 BF(Z) ≥ 0
• Left Left ⟹ Z 是其父级 X 的左子级且 BF(Z) ≤ 0
• Right Left ⟹ Z 是其父 X 和 BF(Z) 的右子节点 < 0
• Left Right ⟹ Z 是其父级 X 的左子级且 BF(Z) > 0

所以这里的分类是毫无疑问的。没有重叠，每个类别都有相应的轮换来执行。

在您的示例树中，𝑋 是平衡因子为 +2 的根节点。 𝑍 是它的右孩子。所以我们处于场景 1。此场景需要向左进行简单旋转，其中𝑋成为𝑍的左子节点：

  15
 /  \
5    20
 \
  10

虽然您可以执行double旋转，但首先将以节点 15 为根的子树向右旋转，然后才在根节点处向左旋转，但这只会增加工作量：无需执行在节点 15 处旋转。在根处进行简单的旋转就足够了。