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

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

http://img1.sycdn.imooc.com//climg/5ff59c4209a8f71708070226.jpg

看bobo老师的条件是

LL的情况:当前节点的平衡因子大于1,左子树的平衡因子大于等于0,LR类似

这个getBalanceFactor(node.left) >= 0 是否应该改成getBalanceFactor(node.left) > 0更为准确,因为

如果是在左侧的左侧添加新节点导致破坏二叉树的平衡的话,左节点的平衡因子一定是大于0的,不会等于0

正在回答

登陆购买课程后可参与讨论,去登陆

2回答

在添加的时候,确实不会出现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");


继续加油!:)


假蛙工程师 2022-01-14 16:39:39

我也产生了如此的疑问。"在左侧的左侧添加新节点导致破坏二叉树的平衡的话,左节点的平衡因子一定是大于0的,不会等于0”,十分赞同。看了老师的解释后终于理解了原因,因为此旋转不仅用于添加操作,还用于删除操作。删除操作,打破平衡,可能存在getBalanceFactor(node.left) = 0的情况,综合两种操作,条件才是大于等于0,只考虑添加操作是没有必要等于0的

  • 这里的回复存在一些问题,我以为getBalanceFactor(node.left)是在leftRotate或者rightRotate中使用,其实是在add和remove方法中使用。


    个人认为,add中虽然不可能出现 = 情况,从代码实现的角度看,不写 = 本来就正确执行。但是为什么还写等于的情况呢?这应该是从代码语义的角度看的,如果某个节点不平衡,它的形状是getBalanceFactor(node.left) >= 0, 我们应该如何处理,这样语义上并没有什么问题。同时也统一了add和remove的代码

    2022-01-15 15:53:28
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师