AVL树：插入
看完你能徒手推演插入后平衡因子的变化并选定正确的旋转
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
AVL树：插入
看完你能徒手推演插入后平衡因子的变化并选定正确的旋转
AVL树平衡因子
插入新节点后，每个节点的「身高差」可能发生变化。我们需要一个数值来量化这种不平衡——这就是平衡因子。
左高减右高所得的差，就是「偏」了多少
插入操作的基本流程
AVL 的插入看似只是多了一步平衡检查，实际是一环扣一环的递归回溯。
插入后失衡的判断
新节点已经入位，但这棵树到底有没有被'压歪'？今天讲清楚怎么判断：从插入点沿父指针向上回溯，定位那个平衡因子刚变成 ±2 的祖先节点。
从加重位置往上数，最近那块倾斜超限的支点就是修复点
四种失衡类型总览
看失衡节点沿路径两次走的方向，决定失衡类型与修复方法
单旋的数学原理
前面我们看到，失衡分四种，每种用一次旋转修复。但有个疑问：祖先节点会不会也跟着失衡？要回答这个问题，得算清楚旋转前后子树的高度变化。
一侧坐太重板压低，把人挪到另一侧，板面回到原位高度
LL型旋转图解
LL型失衡做右单旋，本质是让左子B顶上来，把失衡节点A压到右边。
RR型旋转图解
RR型失衡通过一次左单旋修复，过程是LL型的镜像翻转。
LL与RR旋转对比
LL 与 RR 互为镜像，但旋转方向与判别条件容易记混。这一页把它们并排对照。
- 失衡节点 BF=+2，左孩子 BF=1 或 0
- 顺时针方向，整体右旋
- 原左孩子升为新根，原根变右孩子
- 失衡节点 BF=-2，右孩子 BF=-1 或 0
- 逆时针方向，整体左旋
- 原右孩子升为新根，原根变左孩子
双旋的数学原理
单旋能一次修好 LL/RR 的直线型偏斜。但 LR/RL 的失衡路径在根节点处拐了弯——只把高层子节点拉上来，深枝仍会挂在错误方向，所以要做两次旋转。
弯折处的关节先反向折一下拉直，再整体摆正——对应先局部旋再整体旋
LR型旋转图解
LR型失衡要把中间节点C分两次上提：先对B左旋把C摆到能继续上提的位置，再对A右旋完成平衡。
RL型旋转图解
RL 型失衡分两步：先对右孩子右旋，再对失衡节点左旋。
LR与RL旋转对比
LR 与 RL 是双旋的两种镜像情形，旋转方向一正一反，最容易记混或做反。
- 失衡位置：新节点在 A 右孩子的左子树（路径 R→L）
- 旋转顺序：先对 B 左旋变成 RR 型，再对 A 右旋
- 结构示意：A—右—B—左—C，旋转后 C 升为新根
- 失衡位置：新节点在 A 左孩子的右子树（路径 L→R）
- 旋转顺序：先对 B 右旋变成 LL 型，再对 A 左旋
- 结构示意：A—左—B—右—C，旋转后 C 升为新根
旋转选择决策树
从失衡节点出发，先看自身BF正负，再看重侧孩子的BF，两步定位旋转方法。
失衡类型判断
AVL树插入新节点后，失衡节点A的平衡因子为+2，其左孩子B的平衡因子为-1，新节点位于B的右子树中。该失衡属于哪种类型，应如何修复？
插入算法框架
前面我们看了四种旋转的样子，现在退一步看全貌：插入其实只有两个阶段——向下找到位置放新节点，向上回溯时顺手检查并修复失衡。把这两段拼起来，就是完整的插入算法。
包裹落到末端→逐层向上汇报重量→某层超载就拆分重组
AVL树插入完整代码
含四种旋转的 AVL 树插入完整 C 实现，可直接编译。
插入回溯时先 updH 再取 bf；按 bf 与 key 方向落入 LL/RR/LR/RL 四种旋转，单旋一次完成，双旋先旋子树再旋根。
关键要点回顾
- ✓平衡因子=左高−右高，超±1即失衡
- ✓LL与RR单旋，LR与RL双旋，均为O(1)
- ✓旋转后子树高度复原，整树插入O(log n)
- ✓失衡判首个不平衡祖先，类型看新节点路径
课后思考
先自己默想 30 秒，再点开参考答案对照思路。
参考答案因为旋转会恢复从该节点向上的整条路径的平衡因子，只需处理最近的那个失衡点即可，再往上必然已经平衡。
参考答案可能 O(log n) 次。因为删除可能让多个祖先失衡，且旋转后未必能修复上层，必须一路向上回溯修复。
参考答案换来查找稳定 O(log n) 且树高最小；付出是插入删除需频繁旋转，写操作代价更高，节点额外存平衡因子。