关于判断AVLTree进行左旋右旋的条件
看bobo老师的条件是
LL的情况:当前节点的平衡因子大于1,左子树的平衡因子大于等于0,LR类似
这个getBalanceFactor(node.left) >= 0 是否应该改成getBalanceFactor(node.left) > 0更为准确,因为
如果是在左侧的左侧添加新节点导致破坏二叉树的平衡的话,左节点的平衡因子一定是大于0的,不会等于0
正在回答
在添加的时候,确实不会出现0的情况。
对于remove的情况,再向上回溯的过程中,有可能出现 getBalanceFator(node.left) == 0 的情况。
在这里,简单说明一下为什么删除会出现 ==0 的情况,你学完删除以后,可以再回来看一下这个问题:
==========
可以使用12-7小节包含删除测试的代码测试一下,不包含 == 0 会报异常。
在删除的时候,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");
继续加油!:)
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧
0 星