AVL树之LR情况疑问
来源：1-6 LR 和 RL
weixin_慕慕4340848
2020-11-13 14:45:11
老师好，对于LR情况我有一个疑问，比如下图
9是新添加元素，这种情况属于LR情况吗？
左旋转后得到如下二叉搜索树
老师这棵树如果以9为关注点的话，那么9可以看成是插入到根节点的左孩子的右子树。那么它还是LR
如果按照节点8的不平衡因子来看，8的不平衡因子大于0。那么它是LL的。
所以我想问，判断是LL情况还是LR情况的决定因素应该是以不平衡因子对吗？而不是看新元素在不平衡子树的哪个位置，这样理解对吗？
在这里输入代码，可通过选择【代码语言】突出显示
写回答
2回答
-
你的第一幅图是 LR。10 是不平衡节点，10 的左子树比右子树高 2（L），而 10 的左子树（5 为根节点）是右边比左边高（R）
处理 LR，首先对 10 的左孩子做左旋转。也就是在 5 上做左旋转。你的第二幅图是正确的。
现在，对于你的第二幅图，是 LL。10 是不平衡节点，10 的左子树比右子树高 2（L），而 10 的左子树（8 为根节点）是左边比右边高（L）。
现在，处理 LL，需要对 10 做右旋转（注意，处理 LR 的过程中，两次旋转对应的节点不同。）
对 10 作为右旋转，是这个样子：
8 / \ 5 10 / / \ 3 9 11
至此，整棵树平衡。
请再根据这个过程，回顾一下课程的代码：
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { // 注意：是对 node.left 左旋转 node.left = leftRotate(node.left); // 注意：是对 node 右旋转 return rightRotate(node); }继续加油！：）
0 -
假蛙工程师
2022-01-15
如果以9为关注点的话，那么9可以看成是插入到根节点的左孩子的右子树。那么它还是LR
没法这么看，9 插入之前就是LL
0
相似问题