bobo老师想问您有关AVL插入结点旋转的问题
来源：12-6 LR 和 RL
江景又妍和
2019-05-19
老师，对比您RL的讲解图中我知道了，是当插入28时，以34为轴先进行右转，再以98为轴进行左转。
但是我不理解的是RL指的是插入的元素在不平衡的结点的右侧的左侧叫RL，第一个不平衡的点是23啊，它的右侧的左侧并没有不平衡啊。。。
另外我觉得您的图中为了不失一般性，也给Z结点加了两个子结点，这样感觉逻辑上说不通，这样算是添加了一棵树导致不平衡的吗？(我能明白您这样讲的话，拓展性更强，类似的树都可以这样的旋转，比如我图片上那道题，如果单纯对比形状的话，我就能知道如何去旋转)
写回答
1回答
-
好认真，字也好漂亮：）
首先，RL是针对23说的，没有问题。但是，我们在具体纠正23的这个RL不平衡的时候，需要动这个23的右孩子。也就是我们代码中的：
// RL的情况 if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { // 先对node的右孩子做右旋转 node.right = rightRotate(node.right); // 再对node做左旋转 return leftRotate(node); // 这样的两步，维护了node这个节点的RL不平衡；LR同理 }至于我在图中，会给z加入其他节点，是因为，在我们递归回溯的过程中，这个不平衡，不一定出现在最底下，也就是不一定是在T2为空且T3为空的地方。对于此，向AVL树中添加元素，是没有问题的。但是，后续你就会看到，我们在AVL树中删除元素，使用的是同样的平衡维护方式。但是，由于我们删除元素的位置可能是在树的中间，那么这个需要平衡维护的RL状态，也可能出现在整棵树的中间：）
继续加油！：）
112019-05-20
相似问题