AVL树四次旋转不起作用
AVL树四次旋转不起作用
提问于 2016-11-20 08:53:41
为了保持二叉树的平衡，我们可以使用RR LL RL LR foure来使不平衡树保持平衡，但是如果我们有一个平衡树作为fllows：
885
/ \
/ \
659 912
/ \ \
/ \ 934
212 759
/ \
/ \
11 344如果我们向这棵树添加一个节点(168)，并且树如下所示：
885
/ \
/ \
659 912
/ \ \
/ \ 934
212 759
/ \
/ \
11 344
\
168树不是平衡的，但是我不能使用四个旋转(RR，LL，RL，LR)中的任何一个来再次实现树的平衡。有人告诉我为什么吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-11-20 09:35:32
树的左边很重，但是树的左边子树不是很重，你只需要做一个正确的旋转。在正确旋转之后，树将如下所示：
659
/ \
/ \
212 885
/ \ / \
/ \ / \
11 344 759 912
\ \
\ \
168 934尝试使用以下算法来决定执行哪种方法：
IF tree is right heavy {
IF tree's right subtree is left heavy {
Perform Double Left rotation
}
ELSE{
Perform Single Left rotation
}
}
ELSE IF tree is left heavy {
IF tree's left subtree is right heavy {
Perform Double Right rotation
}
ELSE {
Perform Single Right rotation
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40702253
复制相关文章
相似问题
腾讯云开发者
