AVL树重平衡算法：子节点平衡因子为0时如何区分Zig-Zig与Zig-Zag

首先明确统一命名约定，方便梳理逻辑：

• 最先检测到失衡的节点记为z
• z的高度更高的子节点记为y
• y的高度更高的子节点记为x

核心结论 #

这种失衡节点z的子节点y平衡因子为0的场景，仅会出现在删除操作中，插入操作不可能出现该情况。此时无需纠结Zig-Zig或Zig-Zag的选择，直接执行单旋转即可，完全不需要考虑双旋方案：

• 如果y是z的左子节点，直接对z执行右单旋转（也就是你提到的70-44-33对应的Zig-Zig操作）
• 如果y是z的右子节点，直接对z执行左单旋转

结合你给出的场景验证 #

你描述的案例逻辑如下：

1. 删除节点78后，根节点70的右子树高度减1，平衡因子变为+2（左子树比右子树高2），成为失衡节点z
2. 更高的子节点y是左孩子44，此时44的平衡因子为0
3. 按照规则直接对70执行右单旋转，即可得到正确的平衡结果，完全不需要做先左旋44再右旋70的双旋操作。

双旋出错的原因 #

当y的平衡因子为0时，y的左右子树高度完全相等。双旋操作会强行把y的另一侧子树提为中间节点，最终会导致新的根节点左右子树高度差仍超过1，也就是你遇到的错误重平衡结果。

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