AVL树的平衡

Question

我已经实现了AVL树，但我遇到了一个问题。

假设我有以下树： 在添加另一个节点之后： 现在我必须将节点5向左旋转： 但是旋转后，它仍然不平衡。

我在哪里犯了错误？

- MRB

---

需要进行双重旋转，先旋转11次，然后再旋转5次。 - StoryTeller - Unslander Monica

@StoryTeller 谢谢，我不知道那个。我读了维基百科的文章，但是我不太明白如何确定需要双旋转。你能简单地解释一下吗？ - MRB

顺便提一下，在右节点上应该画7。 - Grzegorz

@Grzegorz 为什么？它小于10，我认为它必须在左边。 - MRB

@MohammadRB: 哈哈！我不知道它是10。我以为它是1（有一个点）。对此感到抱歉！ - Grzegorz

@Grzegorz 还有波斯语;) - MRB

Answer 1

这个场景符合维基百科描述中的“右-左”情况。

你的错误在于一次性旋转不平衡节点 (5)，而没有先对其子树进行旋转。

通常情况下，在插入时应遵循以下规则：将P作为不平衡节点，L作为其左子树，R作为其右子树。

balance(N) = Depth(Nleft) - Depth(Nright)

if (balance(P) > 1)  // P is node 5 in this scenario
{
    if (balance(L) < 0)
    {
        rotate_left(L);
    }

    rotate_right(P);
}
else if (balance(P) < -1) // P is node 5 in this scenario
{
    if (balance(R) > 0)  // R is node 11 in this scenario
    {
        rotate_right(R); // This case conforms to this scenario
    }

    rotate_left(P);      // ... and of course this, after the above
}

有时需要执行两次旋转，有时仅需要一次旋转。这在维基百科上得到了很好的视觉展示。

顶行显示需要两次旋转的情况。中间行呈现了只需要一次旋转就足够的可能情况。额外的旋转将任何顶行情况转换为中间行情况。

特别地，对于这棵树：

添加了7之后：

5的平衡因子是2。这符合上面伪代码中标注的场景以及维基百科图片右侧的顶行场景。因此，在5被左旋之前，它的右子树11需要进行右旋操作：

然后它变成：

现在只需要进行一次左旋转（维基百科图片中的中间右行场景），就可以将平衡恢复到5。

然后树又重新平衡了：

- BartoszKP

Answer 2

让我尝试更全面地分析一下， 对于一个二叉树来说，要成为AVL树，从任何最左侧的叶子到任何最右侧的叶子的每个节点的高度差必须在{-1, 0, 1}之间。

AVL插入：

AVL插入有四种情况- L - L L - R R - R R - L

现在， 情况(a). [如果平衡度> 1] L-L（左-左）节点X违反了{-1, 0, 1}约束条件， 并且左侧高度大于右侧 - 给出第一个左侧的L 有一个左子节点Y，其左高度大于右高度..再次是L 操作- 围绕Y顺时针旋转。即一次右旋转。

情况（b）（L-R情况）假设要插入某个Z节点，对于Z，首先评估它应该放在哪个叶子上，左边还是右边。如果权重更大，则放在右边；如果权重更小，则放在左边。例如，Z'是新节点，wt(Z') > wt(Z)，即将Z'作为Z的右子节点插入，这种情况属于L-R情况，整个链接ZZ'逆时针旋转，现在是L-L情况，因此使用上述情况（a）进行解决。即先左旋再右旋。

情况（c）[如果平衡度<-1]（R-R情况）同样，对于R-R情况，只需应用二进制搜索规则进行调整即可解决此问题。即一次左旋。

情况（d）（R-L情况）首先将其转换为R-R情况，然后使用上述情况（c）进行解决。即先右旋再左旋。

- hi.nitish