AVL树高度平衡难题：旋转节点平衡因子判定疑问

这个问题的核心要结合AVL树的插入规则和失衡检测逻辑来理解——毕竟旋转操作只会在插入（或删除）后触发，而且我们只会处理第一个出现失衡的节点（从新节点往上回溯的第一个平衡因子绝对值为2的节点）。下面一步步拆解：

先明确前提：触发x旋转的条件 #

AVL树在插入前是完全平衡的（所有节点平衡因子绝对值≤1）。x之所以需要旋转，是因为插入新节点后，它的平衡因子变成了+2或-2。这意味着：

• 插入前x的平衡因子必然是+1或-1（如果插入前是0，插入后最多变成±1，不会失衡）；
• 插入的节点落在了x的“较高侧”子树（也就是y所在的子树），导致这侧子树的高度比另一侧高了2。

为什么y的平衡因子不能是0？ #

我们以x平衡因子为+2的LL旋转场景为例（y是x的左孩子，RR场景逻辑完全对称）：

1. 插入前y的平衡因子为0的情况 #

此时y的左右子树高度相等，设为h，那么y的子树总高度是h+1。因为插入前x的平衡因子是+1，所以x的右子树高度是(h+1)-1 = h。
当我们在y的任意一侧子树插入新节点后：

• y的对应子树高度变为h+1，y的总子树高度变成h+2（比原来高1）；
• y的平衡因子会变成+1或-1（左右子树高度差从0变成1）；
• x的左子树高度现在是h+2，右子树还是h，平衡因子变成+2，触发旋转。
  此时旋转前y的平衡因子是±1，不是0。

2. 插入前y的平衡因子为±1的情况 #

这种情况下，插入节点的位置会决定是否触发x的失衡：

• 插入到y的“较高侧”子树：比如y的平衡因子是+1（左子树更高），插入到y的左子树。此时y的左子树高度再+1，y的平衡因子会变成+2——这时候y会成为第一个失衡的节点，我们会先处理y的旋转，轮不到x失衡。
• 插入到y的“较低侧”子树：比如y的平衡因子是+1，插入到y的右子树。此时y的右子树高度+1，平衡因子变成0，但y的总子树高度没有增加（原来左子树高度是h+1，右子树是h，插入后右子树变成h+1，总高度还是h+2）。x的左子树高度没有变化，所以x的平衡因子还是+1，不会触发旋转。

结论 #

只有当插入后y的平衡因子是±1时，才会导致x的平衡因子变成±2，同时y本身没有失衡（不会被优先处理）。如果y的平衡因子是0，要么是插入后x没有失衡，要么是y会先于x失衡被处理——所以在需要旋转x的场景下，y的平衡因子只能是±1，不可能是0。

内容的提问来源于stack exchange，提问作者Paras Gupta