平衡二叉树右旋转的问题

Question

在做右旋转的时候 判断左子树的加载因子为什么等于0也需要旋转呢？不应该是等于1吗 如果出现等于0的情况不是说明这个左节点下树是平衡的吗？ 这个时候按我的理解好像要看他的右子树的加载因子是不是等于1啊 。 这块不是太理解

Answer 1

liuyubobobo 2019-12-19 01:59:34

下面的情况，对于节点 A（node 指向 A），是 balanceFactor > 1（至少为2），且 getBalanceFactor(node.left) == 0 的情况。

    A
   / 
  B
 / \
C   D

此时，对于 A 节点来说，要使用右旋转。

注意，这个条件下，balanceFactor > 1 衡量的是 A；getBalanceFactor(node.left) == 0 衡量的是 B。

至于 getBalanceFactor(node.left) == 0 的情况，可以参考这个问答：https://coding.imooc.com/learn/questiondetail/73992.html

继续加油！：）

• 提问者 qq_太阳照常升起_3 #1

  非常感谢！明白了

Answer 2

提问者 qq_太阳照常升起_3 2019-12-18 14:39:53

刚又看了一下 ， 好像虽然>=0 但是前边判断balanceFactor了之后是不会出现等于0的情况的 不知是不是这样。 

• liuyubobobo #1

  可以参考这里：https://coding.imooc.com/learn/questiondetail/73992.html 继续加油！：）