一 真题2010-4
2010-04. 在右图所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。 在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是（ ）
A. 13, 48 B. 24, 48 C. 24, 53 D. 24, 90
24
/ \\
13 53
/ \\
37 90
二 题目要素解析
核心概念：平衡二叉树（AVL 树）
- 平衡因子（BF）：节点的左子树高度 – 右子树高度，AVL 树要求所有节点的 BF ∈ {-1, 0, 1}。
- 插入失衡修复：插入节点后若 BF 超出范围，需通过旋转（左旋 / 右旋） 恢复平衡，常见旋转类型包括 LL、RR、LR、RL。
操作流程：插入 48 → 检查平衡因子 → 定位失衡节点 → 旋转修复 → 确定 37 的子节点。
关键节点：插入 48 后，需跟踪 53、37 等节点的子树结构变化。
三 哔哔详解
步骤 1：按 BST 规则插入 48
原树结构：
24
/ \\
13 53
/ \\
37 90
- 48 > 24 → 走右子树 53。
- 48 < 53 → 走左子树 37。
- 48 > 37 → 成为 37 的右孩子。
插入后临时结构：
24
/ \\
13 53
/ \\
37 90
\\
48
步骤 2：计算平衡因子，定位失衡节点
从插入点 48 向上回溯：
- 节点 37：左高 0，右高 1 → BF = -1
- 节点 53：左高 2，右高 1 → BF = 1
- 节点 24：左高 1，右高 3 → BF = -2（失衡！）
失衡类型为 RL 型（失衡节点 24 的右孩子 53 的左子树插入导致失衡）。
步骤 3：执行旋转修复
右旋 53
（先处理右孩子的左子树）：
- 37 成为 53 的父节点。
- 53 成为 37 的右孩子。
- 37 原来的右孩子 48 保持不变。
24
/ \\
13 37
/ \\
空 53
/ \\
48 90
2.左旋 24（修复根节点失衡）：
- 37 成为新的根节点。
- 24 成为 37 的左孩子。
- 53 保持为 37 的右孩子。
最终修复后的平衡二叉树：
37
/ \\
24 53
/ / \\
13 48 90
步骤 4：确定 37 的子节点
从最终结构可见：
- 37 的左子节点：24
- 37 的右子节点：53
这正好对应选项 C。
四 参考答案
C ✅
五 考点精析
5.1 平衡二叉树概念和性质特征
5.1.1 基本概念
平衡二叉树（AVL Tree）：
它是一棵二叉排序树（BST），且在 BST 的基础上增加了 “平衡” 的限制条件：
- 空树是平衡二叉树。
- 若非空树，则其左、右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。
平衡因子（Balance Factor, BF）：
- 定义：BF(T)=hL−hR （左子树高度 – 右子树高度）。
- AVL 树要求：对于树中每一个节点，都有 BF∈{−1,0,1}。
5.1.2 性质特征
结构自平衡：
在插入或删除节点时，如果破坏了平衡条件（即出现了 BF=2 或 BF=−2 的节点），树会通过旋转操作自动恢复平衡。
高度与节点数的关系：
平衡二叉树的高度 h 与节点数 n 之间的关系是$ h = O(\\log_2 n)$。
- 这保证了 AVL 树的查找、插入、删除操作的时间复杂度均为
O
(
log
n
)
O(\\log n)
O(logn)。
最小节点数：
设 $ N_h $ 为高度为 $ h $ 的 AVL 树的最少节点数，则递推公式为：
N
h
=
N
h
−
1
+
N
h
−
2
+
1
N_h = N_{h-1} + N_{h-2} + 1
Nh=Nh−1+Nh−2+1
初始条件：
N
0
=
0
,
N
1
=
1
N_0 = 0,\\quad N_1 = 1
N0=0,N1=1
-
记忆：类似斐波那契数列。
高度 h
h
h最少节点数N
h
N_h
Nh0 0 1 1 2 N
1
+
N
0
+
1
=
1
+
0
+
1
=
2
N_1 + N_0 + 1 = 1 + 0 + 1 = 2
N1+N0+1=1+0+1=23 N
2
+
N
1
+
1
=
2
+
1
+
1
=
4
N_2 + N_1 + 1 = 2 + 1 + 1 = 4
N2+N1+1=2+1+1=44 N
3
+
N
2
+
1
=
4
+
2
+
1
=
7
N_3 + N_2 + 1 = 4 + 2 + 1 = 7
N3+N2+1=4+2+1=7
5.2 四种旋转（LL/RR/LR/RL）步骤速记
这是考试中画图和做选择题的关键。判断旋转类型的核心在于 “看失衡节点的哪一侧子树更高，以及导致失衡的新节点在那一侧的哪一边”。
1. 核心判断口诀
“看失衡，找孩子；左左 LL，右右 RR；左右 LR，右左 RL。”
- LL 型：失衡节点的左孩子高，且新节点插入在左孩子的左子树。
- RR 型：失衡节点的右孩子高，且新节点插入在右孩子的右子树。
- LR 型：失衡节点的左孩子高，且新节点插入在左孩子的右子树。
- RL 型：失衡节点的右孩子高，且新节点插入在右孩子的左子树
2🌳 旋转操作总览及示例（以节点 A 为失衡点）
| LL | A → 左(B) → 左© | A 右旋 | B | 左左 → 右旋 |
| RR | A → 右(B) → 右© | A 左旋 | B | 右右 → 左旋 |
| LR | A → 左(B) → 右© | B 左旋 + A 右旋 | C | 左右 → 先左后右 |
| RL | A → 右(B) → 左© | B 右旋 + A 左旋 | C | 右左 → 先右后左 |
✅ 关键：
- A：第一个 BF 超限的祖先（失衡点）
- B：A 的孩子（左或右）
- C：B 的孩子（插入发生的位置）
1. LL 型（Left-Left）—— 右旋（Right Rotation）
🔍 判断
- 插入发生在 A 的左孩子的左子树
🔄 操作
- 对 A 执行右旋
- B 成为新根
📐 图例
A B
/ / \\
B → C A
/
C
🧠 说明
- B 的右子树（若有）成为 A 的左子树
- 保持 BST 性质：C < B < A
2. RR 型（Right-Right）—— 左旋（Left Rotation）
🔍 判断
- 插入发生在 A 的右孩子的右子树
🔄 操作
- 对 A 执行左旋
- B 成为新根
📐 图例
A B
\\ / \\
B → A C
\\
C
🧠 说明
- B 的左子树（若有）成为 A 的右子树
- 保持 BST 性质：A < B < C
3. LR 型（Left-Right）—— 先左旋，后右旋
🔍 判断
- 插入发生在 A 的左孩子的右子树
🔄 操作
- C 成为新根
📐 图例
初始（LR 型）：
A
/
B
\\
C
Step 1：B 左旋 → 转为 LL 型：
A
/
C
/
B
Step 2：A 右旋 → 平衡：
C
/ \\
B A
🧠 说明
- C 的左子树 → B 的右子树
- C 的右子树 → A 的左子树
- 最终：B < C < A
4. RL 型（Right-Left）—— 先右旋，后左旋
🔍 判断
- 插入发生在 A 的右孩子的左子树
🔄 操作
- C 成为新根
📐 图例
初始（RL 型）：
A
\\
B
/
C
Step 1：B 右旋 → 转为 RR 型：
A
\\
C
\\
B
Step 2：A 左旋 → 平衡：
C
/ \\
A B
🧠 说明
- C 的左子树 → A 的右子树
- C 的右子树 → B 的左子树
- 最终：A < C < B
✅ 快速判断流程图（文字版）
插入新节点后，从插入点向上找第一个 |BF| > 1 的节点 A
│
├─ 若插入在 A 的左子树：
│ ├─ 若插入在 A.left 的左子树 → LL 型 → 右旋
│ └─ 若插入在 A.left 的右子树 → LR 型 → 先左旋(A.left)，再右旋(A)
│
└─ 若插入在 A 的右子树：
├─ 若插入在 A.right 的右子树 → RR 型 → 左旋
└─ 若插入在 A.right 的左子树 → RL 型 → 先右旋(A.right)，再左旋(A)
六 考点跟踪
| 2010 | 第4题 | 平衡二叉树插入 | ||
| 2019 | 第4题 | 平衡二叉树删除 | ||
| 2020 | 第5题 | 平衡二叉树生成 |
说明：本文内容基于公开资料整理，参考了包括但不限于《数据结构》（严蔚敏）、《计算机操作系统》（汤小丹）、《计算机网络》（谢希仁）、《计算机组成原理》（唐朔飞）等国内高校经典教材，以及其他国际权威著作。同时，借鉴了王道、天勤、启航等机构出版的计算机专业考研辅导系列丛书中的知识体系框架与典型题型分析思路。文中所有观点、例题解析及文字表述均为作者结合自身理解进行的归纳与重述，未直接复制任何出版物原文。内容仅用于学习交流，若有引用不当或疏漏之处，敬请指正。
