为什么LR不能直接进行右旋转？

来源：1-6 LR 和 RL

warren_au

2020-11-01 20:27:28

第一个问题：难道不能直接把8的左子树先记录下来，然后旋转变成

这样吗？这个不是跟上节课的右旋转定义一样吗？

    Node x = y.left;
    Node T3 = x.right;
  
    x.right = y;
    y.left = T3;

第二个问题：在那个复杂的LR中

8那个节点高度为2所以应高调整，但8的平衡点不小于0根据

getBalanceFactor(node.left) < 0
getBalanceFactor(node.left) >= 0
应该直接使用右旋转吗？这样理解正确吗
旋转完
      12
  /        \
 5       18
/  \     /  \
3   8    17
 \  / \
 4  7 11 
 这样的结果是正确的吗？

写回答

1回答

liuyubobobo

2020-11-03

已采纳

这页 ppt 有问题，我举的例子不正确。抱歉！

在这页 ppt 的例子中，节点 5 是平衡的；节点 8 是不平衡的，但其实是 LL，所以只需要右旋转就好。

在下面，我给出了一个正确的 LR 的例子。在这个例子中，节点 11 是不平衡的，且属于 LR。

再次抱歉！

继续加油！：）

hiuyubobobo

harren_au

h 对对对，数字有问题，看形状：）

h020-11-04

共2条回复

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2636 学习 · 1090 问题

查看课程

相似问题

关于判断AVLTree进行左旋右旋的条件

回答 2

AVL树之LR情况疑问

回答 2

balanceFactor>1 已经左边大了，是否可以直接可以右旋转

回答 1

对于红黑树，任何不平衡都会在三次旋转内解决？

回答 1

关于「插入的元素在不平衡的节点的左侧的左侧」

回答 1

打开慕课网App查看更多内容