目标

通过 7 道 408 历年真题与 7 道王道习题，检查自己能否准确处理 AVL 树的平衡约束和红黑树的颜色性质。

完成后应能：

• 用最少结点递推 $N(h)=N(h-1)+N(h-2)+1$ 解决"高度—结点数"互推问题；
• 手工完成插入后的 LL/RR/LR/RL 判型与旋转，写出旋转后的树形；
• 分析"删除再插入"对树形的影响，并识别绝对表述中的反例；
• 用红黑树的五条性质判别合法树形、计算插入后的红结点数。

前置知识

建议先阅读 8.3 节 平衡查找树，掌握四种失衡形态、双旋流程与红黑树的性质清单。

环境、输入与预期输出

• 环境：任意现代浏览器；强烈建议准备纸笔，图形题先重画树形、标注平衡因子再作答。
• 输入：本页 14 道单项选择题，题面中的树形用 1(2(3,_),4) 式记法表示（括号内依次为左、右子树，_ 表示空指针）。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。

作答方法

1. 阅读题面后点击一个选项，先写下选择依据；
2. 点击"提交答案"，再核对对错、正确答案和题解；
3. 做错的题点击"重新作答"后再次推导，直到能说明其余选项为什么不成立；
4. 完成全部题目后再使用页面末尾的答案总览复核，避免只记答案字母。

选择题

答题进度已答 0/14正确 0

第 1 题

难度进阶考点平衡二叉树、最少结点递推标识search-wd73-q11

含有 20 个结点的平衡二叉树的最大深度为（ ）。

请选择一个答案

A4

B5

C6

D7

第 2 题

难度进阶考点平衡二叉树、形态计数标识search-wd73-q13

高度为 3 的平衡二叉排序树的形态共有（ ）种。

请选择一个答案

A4

B14

C16

D15

第 3 题

难度进阶考点平衡二叉树、结点计数标识search-408-2012-q04

若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（ ）。

请选择一个答案

A10

B20

C32

D33

第 4 题

难度进阶考点平衡二叉树、插入构建标识search-408-2013-q03

若将关键字 1, 2, 3, 4, 5, 6, 7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。

请选择一个答案

A0

B1

C2

D3

第 5 题

难度基础考点平衡二叉树、旋转标识search-wd73-q14

在平衡二叉树的基本操作中，可能发生两次旋转的操作是（ ）。

请选择一个答案

A添加、删除结点

B仅删除结点

C仅添加结点

D都不会

第 6 题

难度进阶考点平衡二叉树、有序插入、树高标识search-wd73-q15

将关键字 1, 2, 3, …, 1024 依次插入到初始为空的平衡二叉树中，假设只有一个根结点的二叉树的高度为 0，则插入结束后的平衡二叉树的高度是（ ）。

请选择一个答案

A8

B9

C10

D11

第 7 题

难度基础考点平衡二叉树、定义辨析标识search-408-2009-q04

下列二叉排序树中，满足平衡二叉树定义的是（ ）。选项以 1(2(3,_),4) 式记法表示树形：括号内依次为左、右子树，_ 表示空指针，标号仅为表述方便，不代表关键字大小。

请选择一个答案

A1(2(_,3),_)

B1(2(3,_),4(5,_))

C1(2,3(_,4(_,5)))

D1(2(3(4,_),5(_,6)),7)

第 8 题

难度进阶考点平衡二叉树、性质辨析标识search-408-2015-q04

现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。

请选择一个答案

A根结点的度一定为 2

B树中最小元素一定是叶结点

C最后插入的元素一定是叶结点

D树中最大元素一定是无左子树

第 9 题

难度进阶考点平衡二叉树、插入旋转标识search-408-2010-q04

在右图所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是（ ）。

24(13, 53(37, 90))

结构（文字版）：根 24，左孩子 13；右孩子 53 的左、右孩子分别为 37、90。

请选择一个答案

A13，48

B24，48

C24，53

D24，90

第 10 题

难度进阶考点平衡二叉树、插入旋转标识search-408-2021-q06

给定平衡二叉树如下图所示，插入关键字 23 后，根中的关键字是（ ）。

20(16, 30(25, 40))

结构（文字版）：根 20，左孩子 16；右孩子 30 的左、右孩子分别为 25、40。

请选择一个答案

A16

B20

C23

D25

第 11 题

难度进阶考点平衡二叉树、删除与插入标识search-408-2019-q04

在任意一棵非空平衡二叉树（AVL 树）T1 中，删除某结点 v 之后形成平衡二叉树 T2，再将 v 插入 T2 形成平衡二叉树 T3。下列关于 T1 与 T3 的叙述中，正确的是（ ）。

I. 若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同

II. 若 v 不是 T1 的叶结点，则 T1 与 T3 一定不相同

III. 若 v 不是 T1 的叶结点，则 T1 与 T3 一定相同

请选择一个答案

A仅 I

B仅 II

C仅 I、II

D仅 I、III

第 12 题

难度进阶考点红黑树、平衡二叉树、对比辨析标识search-wd73-q16

下列关于红黑树和 AVL 树的说法中，不正确的是（ ）。

I. 一棵含有 n 个结点的红黑树的高度至多为 $2{\log }_2(n+1)$

II. 若一个结点是红色的，则它的父结点和孩子结点都是黑色的

III. 红黑树的查找效率一般要优于含有相同结点数的 AVL 树

IV. 若 AVL 树的某结点的左右孩子的平衡因子都是零，则该结点的平衡因子也是零

请选择一个答案

AI、III

BIII

CII、IV

DIII、IV

第 13 题

难度进阶考点红黑树、性质标识search-wd73-q18

下列关于红黑树的说法中，正确的是（ ）。

请选择一个答案

A红结点的数目最多和黑结点的数目相同

B若红黑树的所有结点都是黑色的，则它一定是一棵满二叉树

C红黑树的任何一个分支结点都有两个非空孩子结点

D红黑树的子树也一定是红黑树

第 14 题

难度进阶考点红黑树、插入标识search-wd73-q20

将关键字 1, 2, 3, 4, 5, 6, 7 依次插入初始为空的红黑树 T，则 T 中红结点的个数是（ ）。

请选择一个答案

A1

B2

C3

D4

答案总览（建议完成全部题目后查看）

1. 第 1 题：C
2. 第 2 题：D
3. 第 3 题：B
4. 第 4 题：D
5. 第 5 题：A
6. 第 6 题：C
7. 第 7 题：B
8. 第 8 题：D
9. 第 9 题：C
10. 第 10 题：D
11. 第 11 题：A
12. 第 12 题：D
13. 第 13 题：B
14. 第 14 题：C

完成清单

• 14 道题均在提交答案前独立作答；
• 能默写最少结点递推式并推到 $N(6)$、$N(7)$；
• 能在纸面上完成至少两道 RL/LR 双旋并标注旋转后的平衡因子；
• 能列举红黑树五条性质，并解释"全黑必为满二叉树"；
• 能对"一定相同/一定不相同"类选项举出正例或反例。

思考题

1. 最少结点递推式为什么与 Fibonacci 数列同型？它给出了 AVL 高度的什么上界？
2. 插入最多一次双旋，删除为什么可能引发多次旋转？
3. 红黑树放宽了 AVL 的平衡约束，换来的是什么？查找、插入、删除各自的最坏路径长度受什么控制？

复盘

• 判型时我是否先找"最小失衡子树的根"，再看出事方向（L/R + L/R）？
• 遇到"一定"类选项，我是否主动构造了反例？
• 红黑树插入题我是否每一步都检查了"父红才调整、叔红只变色"？