AVL树平衡

Question

我已经实现了一个AVL树,但我遇到了问题.

假设我有以下树:

并在添加另一个节点后:

现在我必须将node5旋转到左边:

但轮换后,它仍然是不平衡的.

我哪里弄错了？

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通过一次左旋转恢复平衡:

树又变得平衡了: