平衡二叉树平衡维护时的条件

Question

平衡二叉树平衡维护时的条件：
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
return rightRotate(node);
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
return leftRotate(node);

后面的条件getBalanceFactor(node.left) >= 0，getBalanceFactor(node.right) <= 0 必要吗？在什么情况下满足前面的条件而不满足后面的？

Answer 1

liuyubobobo 2020-01-03 11:48:57

我是不是没有特别理解你的问题。

注意：balanceFactor 和 getBalanceFactor(node.left) 描述的是两个节点的平衡因子。balanceFactor 描述的是 node 的平衡因子；getBalanceFactor(node.left) 描述的是 node 的左孩子的平衡因子。

以 if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) 为例：

如果 node 是 0。

以下例子是 balanceFactor > 1 && getBalanceFactor(node.left) >= 0

      3
     / \
    2   4
   / 
  1
 /
0

以下例子是 balanceFactor > 1 && getBalanceFactor(node.left) < 0

    2
   / \
  0   4
   \
    3
   /
  1

对于上面的情况，仅仅右旋转不够，在后续会具体介绍如何处理。

继续加油！：）

• 提问者 禅与编码 #1

  老师辛苦。上面你的例子，
  “如果 node 是 0。以下例子是 balanceFactor > 1 。。。”
  如果 node 是 0，balanceFactor 难道不是 1 吗？怎么会是 > 1?

• liuyubobobo 回复 提问者 禅与编码 #2

  你是对的。我原本给出的例子已经平衡了。我进行了修改。

• 提问者 禅与编码 #3

  非常感谢！