平衡二叉树平衡维护时的条件
来源：12-5 左旋转和右旋转的实现
禅与编码
2020-01-03
平衡二叉树平衡维护时的条件：
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 必要吗？在什么情况下满足前面的条件而不满足后面的？
写回答
1回答
-
我是不是没有特别理解你的问题。
注意：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
对于上面的情况，仅仅右旋转不够，在后续会具体介绍如何处理。
继续加油！：）
032020-01-29
相似问题