平衡二叉树(AVL)插入、删除与旋转调整全解秒杀模型
核心心法(刻在脑子里)
- 默认落位铁律:无论插入还是建树,新元素永远严格按 BST「左小右大」逐层比对,默认作为新叶子结点挂入!
- 失衡命名秒杀口诀:==抓 A 倒着看(首个 ),向下两步定类型!左左 LL、右右 RR、左右 LR、右左 RL;LL 右旋,RR 左旋,LR 先左后右,RL 先右后左==!
- 做题画树中位数登基:骨架三节点 排序,中间的「中位数」直接提拔为新根,较小者在左,较大者在右,其余子树按 BST 区间自然挂入!
- 次数对比天堑:插入失衡最多只需 1 次旋转(调完高度复原);==删除失衡最坏需一路连锁调整至根节点 ==!
- 删除再插入真理(2022 真题):无论 是叶结点还是非叶结点,删除后再插回, 与 均「可能相同,也可能不相同」(非叶结点删后插回,触发 LR 旋转仍可复原)!
平衡二叉树解题决策全景图
流程图使用指南(看图 3 秒做题)
- 先走顶部 3 步:落位 倒着找第 1 个 的爷节点 从 顺路径往下走 2 步圈出 ;
- 再对号入座中间 4 张图:看 连成什么形状(左斜线 LL、右斜线 RR、左拐折线 LR、右拐折线 RL),直接按图中的圆圈变换把新树画出来;
- 考场终极偷懒:直接看底部黑条——把 三个数比大小,中间那个数直接提上来当新根,小的放左、大的放右!
一、生命周期:创建、插入与默认落位规则
1.1 动态插入的标准流程(默认落位在哪里?)
考场上很多同学总纠结:“新节点到底插到哪去?”
默认落位铁律
新结点的插入永远遵循二叉排序树(BST)的标准规则:
- 从整棵树的根节点开始,将待插关键字与当前节点比较:
- 若待插值 当前节点值 走入左子树;
- 若待插值 当前节点值 走入右子树;
- 一路向下比对,直到到达空的指针位置(叶子节点下方),默认且必然作为新的叶子结点挂入!
- 挂入后,新叶子结点导致其所在分支的高度 ,此时自底向上回溯检查是否发生平衡失衡。
1.2 创建 / 构建整棵 AVL 树(完整建树图解实例)
- 物理过程:从一棵空树开始,给定一个关键字序列,依次逐个按 BST 规则插入叶子位置。
- 构建核心铁律:每插入一个关键字,必须立即自底向上检查平衡性;一旦失衡,必须当场旋转调整恢复平衡后,才能继续插入下一个关键字!
实战建树演示:将序列 10, 20, 30, 25, 28 依次插入空树
第 1 步:依次插入 10、20、30(触发 RR 左单旋)
- 插入
10、20时均平衡;插入30后,结点10的 (失衡爷 ,,)。 - 三节点 取中位数
20登基当根,当场调整完后才能插下一个数:
插入 30 瞬间(RR 失衡): 当场左单旋调整后(恢复平衡):
10 <-- A (BF = -2) 20
\ / \
20 <-- B 10 30
\
30 <-- C第 2 步:继续插入 25(全树平衡,无需调整)
- 从当前根
20比对: 走右, 走左,挂为30的左叶子。此时各结点 ,不旋转:
插入 25 后(平衡):
20 (BF = -1)
/ \
10 30 (BF = 1)
/
25第 3 步:继续插入 28(局部子树触发 LR 双旋转)
- 从根
20比对:,挂为25的右叶子。 - 从下往上倒着查失衡:
25平衡30的左高 2、右高 0,(抓出最小失衡爷 )! - 从 向下走两步:(左 L),(右 R) LR 型失衡。
- 局部三节点 取中位数
28升级顶替原来30的位置,小者25在左,大者30在右:
插入 28 瞬间(局部 LR 失衡): 局部中位数 28 登基后(最终建成的 AVL 树):
20 20
/ \ / \
10 30 <-- A (BF = 2) 10 28 <-- 局部新根
/ / \
B --> 25 25 30
\
28 <-- C1.3 动态删除操作(三大情形与连锁失衡)
删除结点的流程同样先按 BST 规则进行,分为三类:
- 删除叶结点:直接脱链抹除,原父节点对应指针置空;
- 删除只有一棵子树的结点:直接用其唯一的孩子子树顶替该结点的位置;
- 删除有两棵子树的双孩子结点:
- 选取该结点的直接前驱(左子树最大值)或直接后继(右子树最小值);
- 用前驱或后继的关键字值覆盖替换待删除结点的值;
- 进而转化为删除该前驱或后继结点(此时被删除结点的度必然变为 0 或 1)。
综合实战大例:删除度为 2 的根结点(前驱替换 + 树高失衡 + 中间行李过继)
学长划重点:为什么必须练综合大例?
考研真题如果考删除,绝不会考一眼能看出答案的简单叶子脱链。 高分必须吃透:双孩子结点的“前驱替换”、左子树底层脱链引发根部失衡、以及旋转后“原本挂在中间的子树(行李)如何过继”!
步骤 1:原平衡二叉树(初始状态,树高 = 4)
这是一棵严格合法的 AVL 树,所有结点的 :
30 (BF = -1)
/ \
10 (BF = -1) 50 (BF = -1)
\ / \
20 40 60 (BF = -1)
\
70- 左子树(以
10为根):高度为 2(); - 右子树(以
50为根):高度为 3(); - 根结点
30:(平衡)。
步骤 2:删除度为 2 的根结点 30(路线 A:选【直接前驱】替换法)
💡 核心规则提醒:删除度为 2(有左右双孩子)的结点时,既可以选直接前驱(左子树最大值),也可以选直接后继(右子树最小值),两者在 408 考纲中 100% 等价合法!这里我们先演示【路线 A:直接前驱】,下方再对比演示【路线 B:直接后继】。
- 定位直接前驱:
30拥有左右两个孩子,找其左子树的最右下结点(最大值) 结点20; - 数值替换覆盖:用
20覆盖原根结点30的位置; - 转化底层删除:问题转化为在左子树中删除原本的叶结点
20(直接脱链移除)。
底层 20 脱链后的树形如下:
20 <-- A (左高 1, 右高 3, BF = -2, 根结点失衡!)
/ \
10 (高 1) 50 (高 3)
/ \
40 60
\
70步骤 3:自底向上倒查平衡,锁定最小失衡根与特征命名
- 倒查平衡因子:
- 叶子
10脱链后只剩自己,左子树高度实打实从 2 降为了 1; - 右子树(以
50为根)没有变动,高度仍然为 3; - 新根结点
20的平衡因子: 锁定最小失衡根 !
- 叶子
- 看腿定名(从 A 向较高子树走两步):
- 从 沿较高侧(右侧)走第 1 步:到达孩子结点 (向右记为 R);
- 从 沿其较高侧(右侧 高 2,左侧 40 高 1)走第 2 步:到达孙子结点 (向右记为 R);
- 走向为 右 右 判定为 ==RR 型失衡,官方旋转名称为 RR 旋转 / 逆时针左单旋转==!
步骤 4:骨架中位数登基 + 随身行李(中间子树 40)过继挂接
- 确定骨架三节点: 排序后中位数为
50; - 新根登基:
50升级为整棵树的新根; - 较小者下沉:原根
20(带着其左孩子10)下沉为50的左孩子; - 较大者归右:
60(带着其右孩子70)顺理成章作为50的右子树; - 🌟 核心难点:随身行李
40的过继去向:50升为新根后,其原本的左指针需要指向下沉的20,那么原本挂在 50 左边的40挂到哪里?- 按 BST 大小区间法则:!
- 因此
40刚好过继作为下沉结点20的右孩子!
最终调整恢复平衡的 AVL 树(树高从 4 降为 3):
50 (BF = 0)
/ \
20 (BF = 0) 60 (BF = -1)
/ \ \
10 40 70对比路线 B:如果删除 30 时选的是【直接后继 40】会怎样?
- 定位直接后继:找
30的右子树最左下结点(最小值) 结点40; - 替换与脱链:用
40覆盖根结点30,并拔掉右子树中原先的叶结点40:
40 (总根)
/ \
10 (高 2) 50 <-- A (左高 0, 右高 2, BF = -2, 局部失衡!)
\ \
20 60 <-- B
\
70 <-- C- 局部失衡与旋转:
- 拔掉
40后,结点50的左子树变空(高 0),右子树60 -> 70高 2, 最小失衡根锁定在局部结点 ! - 走向:
50 -> 60(右 R)-> 70(右 R),触发局部 ==RR 左单旋转==; - 局部三节点 取中位数
60升为右子树新根,50为左,70为右:
- 拔掉
40 (BF = 0)
/ \
10 (BF = -1) 60 (BF = 0, 局部新根)
\ / \
20 50 70考场破题潜规则:前驱 vs 后继 到底怎么选?
- 为什么两个都能选?:在中序递增序列
10, 20, [30], 40, 50, 60, 70中,紧挨着30左边的是前驱20,紧挨着右边的是后继40。用它们俩谁去顶替30,都不会破坏 BST“左小右大”的铁律!- 做选择题时怎么应对?:如果题干没有强制规定用前驱还是后继,两条路线算出来的树都是 100% 正确的标准答案!在考场上先随便选一个(比如习惯先找前驱),如果算出来的树形不在 A/B/C/D 选项里,立刻换后继算,秒选出正确选项!
深度领悟:为什么删除可能引发连锁失衡?
观察对比:
- 删除前原树高度为 4;
- 经删除与左单旋调整后,树高降为了 3(整棵子树变矮了 1 层!);
- 若 上方还有更高的祖先结点,高度变矮可能会打破上层祖先的高度平衡,从而需要继续向上回溯检测与旋转,最坏需要一路调整到整棵树的根结点( 次旋转)!
插入 vs 删除 旋转调整次数的核心天堑(408 极高频考点)
操作类型 失衡子树调整后的高度变化 是否引发向上连锁失衡? 最多旋转调整次数 插入操作 最小失衡子树经旋转后,高度恢复到插入前的高度 绝对不会(上层所有祖先高度不变,自动恢复平衡) 最多只需 1 次旋转() 删除操作 最小失衡子树经旋转后,高度可能再变矮 1 层 可能引发连锁失衡(上层祖先的高度差被打破) 最坏需要一路调整至根结点( 次旋转)
二、失衡特征判定与官方旋转名称对照表
考生核心痛点破解:做题我会做,但题目问我“名字”怎么答?
很多同学做题靠直觉或者用中位数法秒杀出图,但选择题一旦考“该失衡属于什么类型?采用了什么旋转?”时就抓瞎。 记住学长的**“看腿定名法”:名字绝不是死记硬背的,它是直接由失衡根向下走的两步方向**命名的!
2.1 锁定“骨架三代” 、、
- 抓最小失衡根 (爷爷):
- 从新插入的叶子(或删除落位处)出发,**沿着双亲指针链自底向上(倒着看)**计算各结点的平衡因子:
- 遇到的**==第一个 的祖先结点==**,立即圈定为 !( 以上的更高层祖先全部忽略)。
- 抓孩子 与孙子 (向下走两步,走满立刻止步):
- 从 沿着通往新插入结点的路径向下走第 1 步 到达孩子结点 (向左记为 L,向右记为 R);
- 从 顺着路径继续向下走第 2 步 到达孙子结点 (向左记为 L,向右记为 R);
- ⚠️ 走满两步立刻止步!哪怕新结点插在曾孙、玄孙更深层,骨架依然只有 三节点!
灵魂拷问:明明新插的是 23,凭什么只调整 {20, 30, 25}?为什么不带 23 玩?
很多同学死活转不过弯:“明明是 23 引发了失衡,为什么争夺新根的骨架里根本没有 23?” 学长用三个层次给你彻底捅破这层窗户纸:
- 谁坏了找谁算账(谁失衡,谁才是调整的主角):
- 插入 23 之后,从 23 倒着往上看:
- 结点 25:左高 1、右高 0,(平衡!25 本身完全合法);
- 结点 30:左高 2、右高 1,(平衡!30 本身也合法);
- 根结点 20:左高 1、右高 3,(失衡!整棵树里唯一非法的只有 20!)。
- 既然是以 20 为根的这棵大树坏了,旋转的唯一目的就是拯救 20,把以 20 为顶的右侧长分支从 3 层压扁到 2 层!
- 旋转在物理上只能同时编排“祖孙三代”:
- 无论是左单旋、右单旋还是双旋,计算机代码中指针修改的本质,永远只能重新组织 3 个层级的节点(爷 A、子 B、孙 C)。
- 爷子孙三代原本在一条深线上(高度为 3),旋转就是把这 3 个人拉平重构成一个 2 层的三角形(中位数当根,小的在左,大的在右,高度降为 2)。
- 23 的真正身份是“行李挂件”,不参与大人的排座次:
- 23 只是孙子 25 的随身行李(左子树挂件)。
- 当大人重组座次:孙子 25 登基当新根、爷爷 20 变成 25 的左孩子后,23 就像行李一样被 25 顺手“过继”给了 20 的右孩子(因为 )。
- 大人开董事会选董事长,行李挂件当然不可能坐上董事长的椅子! 它只要在座次排好后,按 BST 大小顺序依附在最合适的空位上即可。这就是为什么无论新节点挂在多深的第 5 层、第 10 层,骨架参与旋转的永远只有失衡根 A 往下看的 祖孙三代!
2.2 4 种失衡类型与官方旋转名称终极对照表
| 从 向下两步走向 | 失衡类型官方全称 | 题干可能出现的别名 | 对应旋转操作官方名称 | 旋转具体物理动作 | 最终升级为新根的结点 |
|---|---|---|---|---|---|
| 左(L) 左(L) | ==LL 型失衡== | 左左型失衡 | ==LL 旋转 / 右单旋转== | 顺时针旋转(Right Rotation):以 为轴对 右旋 | 孩子结点 升为新根 |
| 右(R) 右(R) | ==RR 型失衡== | 右右型失衡 | ==RR 旋转 / 左单旋转== | 逆时针旋转(Left Rotation):以 为轴对 左旋 | 孩子结点 升为新根 |
| 左(L) 右(R) | ==LR 型失衡== | 左右型失衡 | ==LR 旋转 / 先左后右双旋转== | 先对 进行左单旋拉直,再对 进行右单旋 | 孙子结点 升为新根 |
| 右(R) 左(L) | ==RL 型失衡== | 右左型失衡 | ==RL 旋转 / 先右后左双旋转== | 先对 进行右单旋拉直,再对 进行左单旋 | 孙子结点 升为新根 |
名字背后的物理内涵(听完绝不混淆)
- 为什么叫 LL?:表示“在失衡点 的**左孩子(L)的左子树(L)**中插入了新结点导致失衡”。
- 为什么 LL 型做“右单旋”?:因为左边太沉了,必须像天平一样顺时针向右转动(右旋),把左孩子 向上提拔,让爷节点 下沉为右孩子!
- 为什么 LR 型叫“先左后右”?:因为 形成了一个拐弯的折线(左拐后右拐)。先对子树 做左单旋,把折线“拉直”成一条向左倾斜的直线(转化为标准 LL 型),再对 做一次右单旋!
三、考场实战终极大招:【三节点中位数秒杀法】
应试核心境界
问你名字,你按上面的表格秒答; 如果是做选择题求“旋转后的根是谁”或“调整后的树形”,绝不要去脑补复杂的指针翻转!
3.1 中位数法三步秒出答案
- 提取骨架三节点:抓出最小失衡子树的 (爷)、(父)、(孙);
- 数值排序取中位数:
- 秒杀组装新子树:
- ==中位数结点必然升级为该子树的新根!==
- 较小的结点下沉为中位数的左孩子;
- 较大的结点下沉为中位数的右孩子;
- 其余挂载的子树,严格根据 BST“左小右大”的区间范围,自然挂到对应一侧!
- 若 原本就是整棵树的总根,则中位数结点直接荣升整棵大树的总根!
四、经典真题全景复盘与避坑精解
4.1 2021 年 408 统考第 6 题(定位深层路径与中位数秒杀)
【2021 统考真题】
给定平衡二叉树如下图所示,插入关键字 23 后,根中的关键字是( )。
A. 16 B. 20 C. 23 D. 25原树结构: 20 / \ 16 30 / \ 25 40
解题全过程:
- 默认落位: 且 ,严格按 BST 比较,插入作为 25 的左孩子(叶子结点)。
- 自底向上找首个失衡点 :
- 结点 25:(平衡)
- 结点 30:左高 2(25-23),右高 1(40) (平衡)
- 根结点 20:左高 1(16),右高 3(30-25-23) (首个失衡点!锁定 )
- 向下两步定类型与名字:
- 从 向下走第 1 步:走向右孩子 (向右 R);
- 从 向下走第 2 步:走向左孩子 (向左 L);
- 走满两步立刻停!两步走向为“右 左”,官方失衡名称为 ==RL 型失衡,采用 RL 旋转(先右后左双旋转)==!
- 中位数法秒杀根节点与调整后树形:
- 骨架三节点为 ,数值排序:。
- 中位数
25直接提拔为整棵树的新根,较小者20放左,较大者30放右; - 新节点 23 去哪了?:23 原本是 25 的左孩子(行李挂件),当 25 升为总根后,根据二叉排序树的大小范围(),23 顺理成章过继给
20当右孩子! - 因为题目问整棵树的根,直接秒选 D(25)!
插入 23 瞬间(A=20 发生 RL 失衡): 中位数 25 登基秒杀后的最终树形:
20 <-- A (BF = -2) 25 <-- 【新总根】
/ \ / \
16 30 <-- B 20 30
/ \ / \ \
C --> 25 40 16 23 40 <-- 23 挂在 20 右侧
/ (行李挂件)
23 (新插叶子,不参与抢根)为什么 23 不参与抢根?(解开你的最大心结)
- 失衡的是 20,不是 23,也不是 25! 插入 23 后,
25的 、30的 ,它们都是合法的。整棵树里唯一平衡因子超标()的是总根20!- 旋转调整的本质是**“局部压矮”**:把以失衡根 为顶的这根过长右支( 这 3 层)拉平成一个 2 层的三角形( 为顶,左 右 )。
- 真正构成这个过长骨架的只有祖孙三代 。挂在孙子 25 身上的 23 只是更深层的叶子挂件,大人(骨架三代)重新排座次,挂件 23 自然不参与抢根!
4.2 2022 年 408 统考第 4 题(删除再插入的结构变异真相)
【2022 统考真题】
在任意一棵非空平衡二叉树(AVL 树) 中,删除某结点 之后形成平衡二叉树 ,再将 插入 形成平衡二叉树 。下列关于 与 的叙述中,正确的是( )。
I. 若 是 的叶结点,则 与 可能不相同
II. 若 不是 的叶结点,则 与 一定不相同
III. 若 不是 的叶结点,则 与 一定相同
A. 仅 I B. 仅 II C. 仅 I、II D. 仅 I、III
考场思维避坑:绝不能想当然认为“非叶结点删后再插入一定变样”!
很多辅导资料在此题上存在误导解析。学长带你用严密的数学反例彻底秒杀:
深度解析:
- 分析命题 I(叶结点情况):
- 构造 4 节点 AVL 树 ,删除叶结点 触发右单旋得到 ,再插回 得到 :
原树 T1: 删叶 5 后右旋得 T2: 再插回 5 得 T3:
4 2 2
/ \ / \ / \
2 5 1 4 1 4
/ \
1 5- 对比发现 (根为 4)(根为 2)。命题 I “可能不相同” 完全正确!
- 分析命题 II 与 III(非叶结点情况):
- 极简 3 结点杀手级反例:取非叶结点 (根节点),用后继
3顶替删除,再把2插回触发 LR 双旋转:
- 极简 3 结点杀手级反例:取非叶结点 (根节点),用后继
原树 T1: 删根 2 后得 T2: 插回 2 瞬间(LR失衡): LR 旋转后得 T3:
2 3 3 (A) 2
/ \ / / / \
1 3 1 1 (B) 1 3
\
2 (C)- 震撼结论: 与最原始的 完全一模一样()!
- 这彻底证明了:即使 不是叶结点,删掉再插回,经过旋转调整依然完全可能恢复原样!
- 因此:命题 II(一定不相同)是错误的;命题 III(一定相同)显然也是错误的。
- 最终结论:选 A(仅 I 正确)。
五、树高与最少/最多结点数模型(计算题秒杀)
5.1 最少结点数模型(斐波那契平衡树)
题眼特征
题目出现“所有非叶结点的平衡因子均为 1(或 -1)”或“高度为 的平衡二叉树拥有的最少结点数”时直接套用!
- 递推公式:
| 树高 | 最少结点数递推展开 | 最少结点数 | 对应满二叉树最多结点数 |
|---|---|---|---|
| 0 | 0 | 0 | |
| 1 | 1 | ||
| 2 | 2 | ||
| 3 | 4 | ||
| 4 | 7 | ||
| 5 | 12 | ||
| 6 | 20 | ||
| 7 | 33 |
- 秒杀范例:
- 正向:高度为 6 且所有非叶结点 查表直接秒选 20!
- 逆向:结点数为 12 的 AVL 树最大高度 落在 与 之间,最大高度为 5!