我已经实现了AVL树,但我遇到了一个问题。
假设我有以下树:
在添加另一个节点之后:
现在我必须将节点5向左旋转:
但是旋转后,它仍然不平衡。
我在哪里犯了错误?
假设我有以下树:
![enter image description here](https://istack.dev59.com/TZ1zE.webp)
![enter image description here](https://istack.dev59.com/5Q6MJ.webp)
![enter image description here](https://istack.dev59.com/RoZra.webp)
我在哪里犯了错误?
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
。
然后树又重新平衡了:
让我尝试更全面地分析一下, 对于一个二叉树来说,要成为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)进行解决。即先右旋再左旋。