“对于remove的情况，再向上回溯的过程中，有可能出现 getBalanceFator(node.left) == 0 的情况” 。
来源：12-5 左旋转和右旋转的实现
next_n
2019-02-20
老师您好，发现您在给其他人的回复里，出现了这句话：“对于remove的情况，再向上回溯的过程中，有可能出现 getBalanceFator(node.left) == 0的情况。”
对于您这句话，我思考了一下这个问题，发现把getBalanceFator(node.left) == 0 的情况放在LR和RL的情况里整个逻辑跑完结果也是对的。如下所示
//LL:右旋
if( balanceFactor > 1 && getBalanceFactor(retNode.left) > 0) return rightRotate(retNode);
//RR:左旋
if( balanceFactor < -1 && getBalanceFactor(retNode.right) < 0) return leftRotate(retNode);
//LR:先左旋 后右旋
if( balanceFactor > 1 && getBalanceFactor(retNode.left) <= 0 ){
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
//RL:先右旋 后左旋
if( balanceFactor < -1 && getBalanceFactor(retNode.right) >= 0){
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
所以本质是要对于这样的情况进行一定的处理。
但是对删除元素时出现：getBalanceFator(node.left) == 0同时 getBalanceFator（node） > 1，这样的情况没有直观的理解，所以老师您可以举一个例子吗？
1回答
-
可以使用12-7小节包含删除测试的代码测试一下，使用你的逻辑会报异常。
在删除的时候，getBalanceFator(node.left) == 0的逻辑必须和LL(或者RR一起处理)。
直观地想，（以LL和LR为例），如果删除了某个节点以后，成如下形态，其中x是retNode的话
x / \ y T3 / \ T1 T2
假设T1, T2, T3都是同层子树，此时，x满足balanceFactor > 1 && getBalanceFactor(x.left) == 0
此时，如果使用LL的处理方式，只是进行一次右旋转，很容易得到：
y / \ T1 x / \ T2 T3
可以看出，整棵树依然是平衡的。
但是如果使用LR的方式，就需要先对x.left即y进行左旋转，这个过程显然很容易打破y本身的平衡。出现问题。
如果你一定要具体的例子的话，我构造了一个例子：
8 / \ 4 9 / \ \ 2 6 10 / \ \ 1 3 7
删除节点8以后，节点9将成为retNode，满足balanceFactor > 1 && getBalanceFactor(8.left) == 0 （也就是节点4的Balance Factor为0）。可以尝试一下，删除8，后续对于节点9采用LR的过程，整棵树将失去平衡：）
附测试代码：（当然希望你能手动跟踪一下，再仔细理解一下整个删除过程是如何运作的：））
AVLTree<Integer, Integer> tree = new AVLTree<>(); tree.add(8, null); tree.add(4, null); tree.add(9, null); tree.add(2, null); tree.add(6, null); tree.add(10, null); tree.add(1, null); tree.add(3, null); tree.add(7, null); tree.remove(8); if(!tree.isBalanced()) throw new RuntimeException("remove not Balanced");继续加油！：）
162019-05-02
相似问题