algorithm - AVL 树平衡

Question

我已经实现了一个 AVL 树，但是我有一个问题。

假设我有以下树：

添加另一个节点后：

现在我必须将 node5 向左旋转：

但是旋转之后，还是不平衡。

我在哪里犯错？

Answer 1

呈现的场景符合此 Wikipedia描述中的Right-Left案例。

您的错误是您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
}

所以有时需要进行两次旋转，有时只需进行一次。

这在Wikipedia上有很好的可视化：

顶行显示需要两次旋转的情况。中间一行展示了一个轮换就足够的可能场景。额外的旋转将任何顶行场景转换为中间行场景。

特别是，对于这棵树：

添加后7：

的余额5为2。这符合上面伪代码中标有注释的场景，也符合维基百科图片中的顶行场景（右侧）。所以在5左旋之前，它的右子树11需要右旋：

它变成：

只是现在，这是一个简单的情况（维基百科图片中的中间行右场景）5通过一个左旋转来恢复平衡：

树再次变得平衡：

Answer 2

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

AVL 的插入：

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

现在，案例（a）。[if balance > 1] LL(left - left) 节点 X 违反 {-1, 0, 1} 约束并且左侧高度大于右侧 - 给出 L 的第一个左侧有一个左侧子孩子 Y，其左侧高度更大比右.. 再次 L 动作 - 顺时针旋转 Y。IE。一右旋转。

case (b) (L -R case)假设某个Z节点要被插入，对于Z，它首先被评估，它被放置在左边或右边的哪个叶子上。右，如果更重，左，如果更轻。比如说，Z'，新节点，wt(Z') > wt(Z)，即Z'作为Z的右孩子插入，L-R的情况，整个链接ZZ'逆时针旋转，现在是LL 情况，因此使用上述情况 (a) 解决。IE。一左一右旋转。

case (c) [if balance < -1] (R - R case) 类似地，R - R case，只需应用二分搜索规则进行调整，这种情况就有效。IE。一左旋转。

case (d) (R - L case) 首先将其转换为 RR case，因此使用上述 case (c) 求解。IE。一右一左旋转。