如何平衡AVL树中的悬挂节点？插入序列失衡问题求解

你完全没错——不能直接把73硬塞到75和70之间，AVL树的平衡必须严格遵循旋转规则。我们一步步拆解插入73后的平衡过程：

第一步：定位失衡节点 #

插入73后，从新节点向上回溯，找到第一个平衡因子绝对值大于1的节点：根节点50。

• 50的左子树高度为1（仅包含22），右子树高度为3（75→70→73）
• 平衡因子 = 左高 - 右高 = 1 - 3 = -2，属于右-左（RL）型失衡（失衡节点的右子树左重）

第二步：执行两次旋转修复平衡 #

RL型失衡需要通过「右旋+左旋」的组合旋转来修复：

1. 右旋70节点 #

把73提升为70的父节点，70变为73的左子节点，调整后的树结构：

50
 /  \
22  75
   /  \
  73  80
 /
70

2. 左旋50节点 #

把73提升为新的根节点，50变为73的左子节点，75变为73的右子节点，最终平衡的AVL树：

73
 /  \
50   75
/ \  / \
22 70 空 80

验证平衡状态 #

检查所有节点的平衡因子（左高-右高）：

• 22、70、80：0（左右子树高度一致）
• 50：0（左高1，右高1）
• 75：-1（左高0，右高1）
• 73：0（左高2，右高2）

所有节点的平衡因子绝对值都≤1，完全符合AVL树的平衡要求。

总结RL型失衡处理逻辑 #

当某个节点出现右重（平衡因子=-2），且它的右子节点是**左重（平衡因子=+1）**时：

1. 先对右子节点的左分支执行右旋，将其转为右重结构
2. 再对原失衡节点执行左旋，即可让整棵树恢复平衡

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