数据结构第 7 章：查找

408 数据结构「查找」复习：核心知识点、真题题型、通用解法与易错点。

这里的数据结构第 7 章，按常见教材/王道体系就是查找。已参考本站中对应的 408 真题“查找”页和408 模拟选择题“第 7 章查找”页。需要注意：真题区由于没有把“串”单独列章，所以把“查找”编号成第 6 章；模拟题区则按教材编号为第 7 章。此处所指的是后者意义上的第 7 章查找。(Any Docs)

这一章的核心不是背一堆树，而是解决一个统一问题：

给定关键字 $k$ ，如何尽可能少地确定它存在还是不存在？如果数据还会频繁插入、删除，又怎样维持高效查找？

从 408 真题分布看，最值得投入时间的是：

BST / AVL → B 树 / B+ 树 → 散列表 → 折半查找 → 红黑树 → 分块/顺序查找。

一、第 7 章总框架

可以把全章看成下面这棵“方法树”：

查找
│
├─ 线性结构上的查找
│  ├─ 顺序查找
│  ├─ 折半查找
│  └─ 分块查找
│
├─ 树形查找
│  ├─ 二叉排序树 BST
│  ├─ 平衡二叉树 AVL
│  └─ 红黑树
│
├─ 多路查找树
│  ├─ B 树
│  └─ B+ 树
│
└─ 散列查找
   ├─ 散列函数
   ├─ 冲突
   ├─ 开放定址
   └─ 链地址

它们的本质差别是：

方法	核心思想	典型复杂度	是否要求有序
顺序查找	一个个找	$O (n)$	否
折半查找	每次排除一半	$O (lo g n)$	是
分块查找	先找块，再找元素	介于二者之间	块间有序
BST	大的向右，小的向左	平均 $O (lo g n)$ ，最坏 $O (n)$	树内有序
AVL	严格限制 BST 高度	$O (lo g n)$	是
红黑树	较宽松地限制高度	$O (lo g n)$	是
B/B+树	一个结点放很多关键字	$O (lo g_{m} n)$ 级树高	是
Hash	关键字直接映射地址	平均接近 $O (1)$	否

二、查找的基本概念

1. 查找成功与失败

所谓查找，就是给一个关键字 $k$ ，判断是否存在关键字等于 $k$ 的记录。

最重要的性能指标叫平均查找长度 ASL：

A S L = i = 1 \sum n p_{i} c_{i}

其中：

$p_{i}$ ：查找第 $i$ 个元素的概率；
$c_{i}$ ：找到它需要比较关键字的次数。

若等概率：

p_{i} = \frac{1}{n}

于是：

A S L = \frac{1}{n} i = 1 \sum n c_{i}

408 经常不是直接问复杂度，而是给出具体结构，要求计算 每个元素究竟比较几次。

2. 静态查找表与动态查找表

这是理解后面各种树的关键。

静态查找表

主要操作：

查找；
遍历。

数据几乎不发生插入删除。

适合：

有序数组 + 折半查找。

动态查找表

除了查找，还有：

插入；
删除。

适合：

BST；
AVL；
红黑树；
B 树；
Hash。

3. 一个很容易混淆的模拟题

竟成模拟二-10：二叉堆、BST、B 树、红黑树中，一般查找任意关键字效率最低的是谁？

答案是二叉堆。

很多人看见“堆”就觉得它效率高，这是错的。

堆只能保证：

大根堆：
父 ≥ 孩子

小根堆：
父 ≤ 孩子

但两个子树内部之间没有大小顺序。

因此：

找最大/最小值：快；
找指定关键字 37：可能得扫一大片结点。

最坏：

O (n)

而 AVL、红黑树、B 树都能把高度控制在对数级。(Any Docs)

三、顺序查找

这是最简单的，但不要完全忽略。

1. 基本思想

比如：

23  18  91  34  52  17

找 52：

23 → 18 → 91 → 34 → 52

比较 5 次。

2. 等概率成功 ASL

假设共有 $n$ 个元素，从第一个开始找。

比较次数依次：

1, 2, 3, \dots, n

所以：

A S L_{成功} = \frac{1 + 2 + \dots + n}{n}

即：

A S L_{成功} = \frac{n + 1}{2}

时间复杂度：

O (n)

四、折半查找——408 高频基础题

这里开始进入真正高频区。

折半查找一定要记两个条件：

① 有序。

② 必须能够快速随机访问中间元素。

因此最适合：

有序顺序表 / 有序数组

而不是链表。

五、题型一：折半查找最多比较多少次

真题：2010 年

题目大意：

一个长度为 16 的有序顺序表，折半查找一个不存在的元素，最多比较多少次？

答案：5 次。(Any Docs)

为什么？

折半查找构成一棵判定树。

含 $n$ 个元素时，最大比较次数：

⌊ lo g_{2} n ⌋ + 1

因此：

⌊ lo g_{2} 16 ⌋ + 1 = 5

真题：2023 年

题目大意：

600 个元素的有序顺序表，折半查找最多进行多少次关键字比较？

有：

2^{9} = 512 < 600 < 1024 = 2^{10}

因此最大比较次数：

10

真题答案也是 10。(Any Docs)

考场秒杀公式

看到“最多比较多少次”，优先想到：

h = ⌊ lo g_{2} n ⌋ + 1

也可以写成：

h = ⌈ lo g_{2} (n + 1) ⌉

六、题型二：折半查找能不能用于这种结构

2024 年真题

题目给出：

有序链表；
无序数组；
有序静态链表；
无序静态链表。

问哪些不适合直接使用折半查找。

答案：全部都不适合。(Any Docs)

判断模板非常简单：

条件 1：有序吗？

无序 → 直接排除。

条件 2：能不能 $O (1)$ 找到中间元素？

链表：

head → ... → ... → middle

必须顺着走。

即使知道 middle 是第 500 个元素，也不能直接访问。

所以链表不适合直接做折半查找。

七、题型三：判断某个序列是否可能是折半查找比较序列

这是非常重要的一类。

2015 年真题

题目给出若干比较序列，例如其中一个是：

500 → 200 → 450 → 180

问哪个不可能由折半查找产生。

核心不是画树，而是维护：

目标值的合法区间。

假设目标是 $x$ 。

先比较 500：

x < 500

再比较 200：

200 < x < 500

再比较 450：

200 < x < 450

那么下一次比较的元素必须在：

(200, 450)

可是下一项是 180。

显然：

180 \in / (200, 450)

所以这个序列不可能。(Any Docs)

八、一个非常重要的统一技巧：上下界法

后续可以发现：

折半查找比较序列、BST 查找路径、BST 判断算法，本质上全是“维护上下界”。

初始：

l o w = - \infty, hi g h = + \infty

遇到值 $v$ ：

如果目标 $x < v$ ：

hi g h = v

如果目标 $x > v$ ：

l o w = v

下一结点必须满足：

l o w < v_{next} < hi g h

这个方法请直接背成万能法。

九、题型四：折半查找成功 ASL

模拟题里有一道很典型：

王道卷三 Q08

题目：

长度为 12 的有序顺序表，各元素等概率，折半查找成功 ASL 是多少？

按折半查找判定树，各层元素数为：

第1层：1
第2层：2
第3层：4
第4层：5

于是：

A S L = \frac{1 \times 1 + 2 \times 2 + 4 \times 3 + 5 \times 4}{12}

得到：

A S L = \frac{37}{12}

关键技巧：

元素所在判定树第几层，就需要比较几次。

(Any Docs)

十、折半查找判定树

408 很喜欢把数组问题转换成树问题。

对于一个折半查找表：

内部结点 = 表中元素；
根 = 第一次比较的中间元素；
左子树 = 左半区；
右子树 = 右半区；
外部失败结点 = 查找失败的位置。

含 $n$ 个元素，一共有：

n + 1

个失败区间。

典型模拟题

有 20 个内部结点的折半查找判定树，问失败查找长度的最小值。

因为：

2^{4} - 1 = 15 < 20 < 31 = 2^{5} - 1

所以判定树有 5 层。

最浅的失败位置可以出现在第 4 层某结点下面，因此最少比较 4 次。(Any Docs)

十一、分块查找

分块查找一定记住八个字：

块间有序，块内无序。

例如：

块1：12  3  8  6
块2：23  19  17  21
块3：37  31  28  35

虽然块内乱序，但是：

max (B_{1}) < min (B_{2})

并且：

max (B_{2}) < min (B_{3})

模拟题：竟成模拟六-10

题目问分块查找的数据组织形式。

正确表述就是：

块间有序；
块内不必有序；
用每块最大关键字等建立索引。(Any Docs)

十二、分块查找为什么存在？

它是一个折中方案：

顺序查找
   ↓ 更快
分块查找
   ↓ 更快
折半查找

但对数据组织的要求则反过来提高。

如果共有 $n$ 个元素，每块 $s$ 个，则约有：

b = \frac{n}{s}

个块。

如果索引也顺序查找，大致：

A S L \approx \frac{b + 1}{2} + \frac{s + 1}{2}

即：

A S L \approx \frac{1}{2} (\frac{n}{s} + s) + 1

其最优数量级在：

s \approx n

附近。

这不是近年最核心考点，但可以帮助理解分块思想。

十三、二叉排序树 BST——本章第一个超级重点

BST 的定义必须达到条件反射。

对于任意结点 $x$ ：

左子树所有结点：

k ey < x . k ey

右子树所有结点：

k ey > x . k ey

并且左右子树自身也是 BST。

十四、BST 最重要性质：中序遍历有序

BST 的中序遍历：

左 → 根 → 右

得到严格递增序列。

例如：

中序：

25 30 40 60 80

十五、题型五：判断某序列能不能成为 BST 的查找路径

2011 年 408 真题

有一组选项中出现路径：

95 → 22 → 91 → 24 → 94 → 71

问哪一条不可能成为 BST 的查找路径。

继续用刚才的上下界法。

比较 95：

x < 95

比较 22：

22 < x < 95

比较 91：

22 < x < 91

比较 24：

24 < x < 91

那么下一结点必须：

24 < v < 91

结果给出：

94

不合法。

所以这条路径不可能。(Any Docs)

注意

此处需要意识到：

折半查找路径

维护：

l o w, hi g h

BST 查找路径

仍然维护：

l o w, hi g h

完全一个套路。

十六、模拟题再强化：查找 52

王道卷五 Q08：

题目给若干序列，问哪个不可能是在 BST 中查找关键字 52 时经过的结点。

其中有：

95 → 59 → 84 → ...

找 52。

到 59 后：

52 < 59

以后只能进入 59 的左子树。

因此后续关键字必须：

< 59

结果下一结点是 84。

立即判错。(Any Docs)

所以这类题不要画树。

画树反而慢。

直接：

维护下界 L
维护上界 R

即可。

十七、题型六：判断序列能不能生成指定 BST

2020 年 408 真题

目标 BST 大致为：

给若干插入序列，问哪个不能得到这棵树。

例如：

4,5,1,2,3

插入过程：

4
 \
  5

再插 1：

    4
   / \
  1   5

插 2：

插 3：

左子树变成右斜链，自然不可能得到目标树。

因此这个序列是错误选项。(Any Docs)

十八、BST 删除

必须会三个情况。

情况 1：删除叶结点

直接删。

情况 2：只有一个孩子

让孩子顶替。

情况 3：有两个孩子

不能随便删。

通常用：

中序前驱；
或中序后继；

替换该结点。

即：

左子树最大值

或：

右子树最小值

十九、2013 真题：删了再插回来一样吗？

题目：

在 BST $T_{1}$ 中删除结点 $v$ ，得到 $T_{2}$ ，再把 $v$ 插回去得到 $T_{3}$ 。

问：

$v$ 是叶结点时如何？
$v$ 不是叶结点时如何？

结论：

$v$ 是叶结点

删除它不会改变其他结点。

重新插入又会沿原路径回原位置。

所以：

T_{1} = T_{3}

$v$ 是非叶结点

删除会发生顶替。

再插回来时 $v$ 通常作为新的叶结点插入。

所以：

T_{1} \neq = T_{3}

真题答案对应“叶结点相同、非叶结点不同”。(Any Docs)

二十、2022 大题：怎么判断一棵树是不是 BST

这是一道非常值得掌握的算法题。

题目大意：

一棵二叉树使用数组顺序存储，空结点用 $- 1$ 表示，设计尽可能高效的算法判断它是不是 BST。

(Any Docs)

错误思路

只检查：

左孩子 < 父亲
右孩子 > 父亲

是不够的。

例如：

局部看：

6 < 15

没问题。

但 6 在根 10 的右子树里，所以必须：

6 > 10

实际上违反 BST。

正确方法：祖先区间

根：

(- \infty, + \infty)

假设当前结点为 $x$ 。

左孩子：

(l o w, x)

右孩子：

(x, hi g h)

任何结点只要：

x \leq l o w

或者：

x \geq hi g h

立即判错。

这个算法特别重要

时间复杂度：

O (n)

辅助空间：

O (h)

这里体现的仍然是本章最重要的思想：

BST 的约束不是只有父子关系，而是所有祖先共同确定一个合法区间。

二十一、平衡二叉树 AVL——408 超级高频

普通 BST 最大问题：

如果按：

1,2,3,4,5,6

依次插入：

树高：

h = n

查找退化到：

O (n)

AVL 就是为了解决这个问题。

二十二、AVL 定义

对任意结点：

B F = h_{L} - h_{R}

并要求：

B F \in {- 1, 0, 1}

即：

∣ h_{L} - h_{R} ∣ \leq 1

二十三、AVL 必背：四种旋转

这是整章必须熟到不用思考的表。

失衡	插入位置	调整
LL	左孩子的左子树	右旋
RR	右孩子的右子树	左旋
LR	左孩子的右子树	先左旋，再右旋
RL	右孩子的左子树	先右旋，再左旋

记忆法：

外侧单旋，内侧双旋。

二十四、LL 型

例如插入：

30,20,10

得到：

对 30 右旋：

   20
  /  \
10   30

二十五、RR 型

插：

10,20,30

得到：

对 10 左旋：

   20
  /  \
10   30

二十六、LR 型

先让 10 左旋：

再让 30 右旋：

  20
 /  \
10  30

二十七、RL 型

先对 30 右旋，再对 10 左旋：

   20
  /  \
10   30

二十八、2010 真题：插入 48 后 AVL 如何调整

站内 2010 真题给出一棵 AVL，插入 48 后出现：

右孩子的左子树增高，即 RL 型失衡。

因此：

先对右孩子右旋；
再对失衡根左旋。

最终 37 的左右孩子分别是：

24，53

真题选 C。(Any Docs)

这类题最重要的不是死画，而是：

从新插入结点向上寻找第一个失衡结点，然后看插入点位于哪一侧。

二十九、2021 真题：插入 23 后根是谁

插入路径：

20 → 30 → 25

23 成为 25 左孩子。

于是：

20 的右子树
        ↓
     又向左

所以是：

RL 型。

双旋后根变成：

25

(Any Docs)

三十、AVL 最小结点数——重要公式

如果 AVL 高度为 $h$ ，要让结点尽可能少：

一边高度：

h - 1

另一边：

h - 2

于是：

N_{h} = N_{h - 1} + N_{h - 2} + 1

初值：

N_{0} = 0

N_{1} = 1

于是：

N_{2} = 2

N_{3} = 4

N_{4} = 7

N_{5} = 12

N_{6} = 20

2012 真题

题目：

高度为 6，所有非叶结点平衡因子均为 1，结点总数是多少？

实际上每个结点都取“高度差正好为 1”的最稀疏状态。

因此：

N_{6} = 20

答案 20。(Any Docs)

三十一、这个递推还能反过来考

模拟题：

只有 15 个结点的 AVL，能不能存在长度为 6 的查找路径？

高度 6 最少需要：

N_{6} = 20

而：

15 < 20

所以不可能。

因此遇到：

“给 $n$ 个结点，某条查找路径是否可能这么长？”

立刻想到：

N_{h} = N_{h - 1} + N_{h - 2} + 1

(Any Docs)

三十二、2019 真题：AVL 删除再插入能恢复吗？

这是很好的概念题。

在普通 BST：

删除叶结点再插入，一定回到原位置。

但是 AVL 不一定。

为什么？

因为：

删除可能引起旋转。

删除某叶子后祖先可能失衡：

删除
 ↓
旋转
 ↓
整棵树结构改变

再把原元素插回来时，新的插入调整未必把此前旋转“反演”回来。

因此即使删的是叶结点：

T_{1}

和重新插入后的：

T_{3}

也可能不同。这是 2019 真题的核心。(Any Docs)

三十三、AVL 最容易掉坑的三个结论

错误 1

“AVL 任意两个叶结点层数相差不超过 1。”

错。

AVL 只保证：

同一个结点的左右子树高度差不超过 1。

它并没有规定整棵树中最深、最浅叶结点只差 1。

模拟题也专门考过这一点。(Any Docs)

错误 2

“最后插入的结点一定是叶结点。”

普通 BST 插入那一刻是。

但 AVL 后面可能旋转。

旋转以后不一定仍为叶结点。

错误 3

“AVL 是完全二叉树。”

错。

完全二叉树只是 AVL 的一种可能形态。

三十四、红黑树

红黑树是近年来非常值得防的新考点，站内模拟题明显加强了这一部分。(Any Docs)

首先需要明确：

红黑树也是 BST。

因此首先满足：

左 < 根 < 右

在此基础上增加颜色约束。

三十五、红黑树五条性质

通常按带 NIL 空结点的定义：

每个结点非红即黑；
根为黑；
NIL 空结点为黑；
红结点的孩子必须是黑；
从任一结点到其后代 NIL 的所有路径包含相同数量的黑结点。

第 4、5 条最重要。

三十六、红黑树到底“平衡”在哪里

AVL 要：

∣ h_{L} - h_{R} ∣ \leq 1

非常严格。

红黑树没有这个要求。

它只是通过：

红结点不能连续；
每条路径黑结点数一致；

保证：

最长路径不会超过最短路径的大约两倍。

所以红黑树属于：

近似平衡 BST

而不是 AVL 意义上的严格平衡。

三十七、红黑树高度界

若红黑树有 $n$ 个内部结点，则高度满足：

h \leq 2 lo g_{2} (n + 1)

因此：

h = O (lo g n)

查找、插入、删除最坏都是：

O (lo g n)

三十八、红黑树 vs AVL 高频比较

站内王道模拟题专门考过。(Any Docs)

AVL

更严格平衡。

所以通常：

树更矮；
查找更有优势。

红黑树

平衡要求稍松。

所以通常：

插入删除调整较少；
动态更新更合适。

二者最坏复杂度都为：

O (lo g n)

不能说：

“红黑树查找一定比 AVL 快。”

通常恰恰是 AVL 的查找路径更短。

三十九、红黑树模拟题：41,38,31,12,19,8

站内模拟题让这些关键字依次插入红黑树，最后得到的结构为：

        38(B)
       /     \
    19(R)    41(B)
    /   \
 12(B) 31(B)
 /
8(R)

由此可判断：

红结点：19、8；
黑结点：38、12、31、41；
8 是 12 的孩子；
黑结点之间可以相邻。

这类题非常适合检查对红黑树插入的变色 + 旋转是否真正掌握。(Any Docs)

四十、B 树——本章另一个超级大重点

为什么需要 B 树？

如果磁盘里有几百万条数据，用 BST：

读一个结点
↓
读磁盘
↓
再读一个结点
↓
又一次磁盘 I/O

磁盘 I/O 太贵。

于是希望：

一个磁盘块一次装很多关键字。

BST 一个结点只有 2 个分支。

B 树一个结点可以有：

几十、几百、几千个分支

树高就大幅降低。

四十一、m 阶 B 树定义——必须背熟

设：

t = ⌈ \frac{m}{2} ⌉

任意结点最多

子树：

m

关键字：

m - 1

因为有 $k$ 个关键字时，有：

k + 1

棵子树。

非根非叶结点至少

子树：

⌈ \frac{m}{2} ⌉

关键字：

⌈ \frac{m}{2} ⌉ - 1

根若不是叶结点

至少：

2

棵子树。

因此至少：

1

个关键字。

所有叶结点

处于同一层。

四十二、2009 真题：B 树与 B+ 树概念区别

题目问：

哪一个不是 B 树定义要求？

其中有：

叶结点之间通过指针连接。

答案就是这个。

因为：

叶结点按顺序链接是 B+ 树的典型性质。

不是 B 树的要求。(Any Docs)

四十三、B 树最少关键字数

这是超级常考公式。

设树高为 $h$ ，根为第一层：

第1层：1 个根
第2层：至少 2 个结点
第3层：至少 2t 个
第4层：至少 2t² 个
...

其中：

t = ⌈ \frac{m}{2} ⌉

最终可以得到高度为 $h$ 的非空 B 树最少关键字数：

n_{m i n} = 2 t^{h - 1} - 1

因此：

n \geq 2 t^{h - 1} - 1

所以最大高度满足：

h \leq 1 + lo g_{t} \frac{n + 1}{2}

考试选项通常会写成取整形式。

四十四、2013 真题：5 阶 B 树高度 2，最少多少关键字？

5 阶：

m = 5

所以：

t = ⌈ \frac{5}{2} ⌉ = 3

根至少：

1

个关键字。

根至少有 2 个孩子。

每个非根结点至少：

t - 1 = 2

个关键字。

因此：

1 + 2 \times 2 = 5

答案 5。(Any Docs)

四十五、2018 真题：3 阶 B 树高度 5，最少多少关键字？

对于 3 阶：

t = ⌈ \frac{3}{2} ⌉ = 2

因此：

n_{m i n} = 2 \times 2^{5 - 1} - 1

即：

n_{m i n} = 31

答案 31。(Any Docs)

四十六、B 树最多关键字

如果高度 $h$ ，每个结点都达到最大分支数 $m$ 。

各层结点数：

1, m, m^{2}, \dots, m^{h - 1}

每个结点最多：

m - 1

个关键字。

因此：

n_{m a x} = (m - 1) (1 + m + \dots + m^{h - 1})

得到：

n_{m a x} = m^{h} - 1

站内模拟题也直接考过这个结论。(Any Docs)

四十七、B 树插入——必须真正会画

过程只有三句话：

向叶子插 → 溢出就分裂 → 中间关键字上提。

假设是 4 阶 B 树。

最多关键字：

m - 1 = 3

一个结点若插入后变成 4 个关键字：

[a b c d]

溢出。

于是：

左半部分形成一个结点；
右半部分形成一个结点；
中间分隔关键字上提。

如果父结点也溢出：

继续向上分裂。

如果根也溢出：

生成新根。

因此特别重要：

B 树高度增加发生在根部。

四十八、2020 真题：完整 B 树插入

题目依次插入：

5,6,9,13,8,2,12,15

到空 4 阶 B 树。

4 阶最多：

3

个关键字。

先：

[5 6 9]

插入 13 后溢出：

[5 6 9 13]

发生第一次分裂，上提关键字。

继续插入，右侧叶结点再次溢出，再向根提升。

最终根中关键字：

6,9

真题答案为 B。(Any Docs)

四十九、B 树删除——比插入更重要

删除一定用以下模板。

情况 1：删除叶结点后仍不低于最小关键字数

直接删除。

情况 2：删除内部关键字

用：

前驱；
或后继；

替换。

然后问题转化成：

删除叶层关键字。

情况 3：删除后下溢

先看兄弟。

兄弟有富余

借。

过程是三者旋转：

兄弟 → 父
父 → 当前结点

情况 4：兄弟也没得借

合并：

当前结点 + 父关键字 + 兄弟

形成一个新结点。

父结点少一个关键字。

如果父又下溢：

继续向上处理。

五十、2012 真题：删除 78

3 阶 B 树中删除 78 后，目标叶结点下溢。

左兄弟还有富余关键字。

因此不是立即合并，而是：

向兄弟借。

站内题图中具体过程是：

父中的 65 下移；
左兄弟最大关键字 62 上移；
最右叶结点最终保留 65。

答案 D。(Any Docs)

五十一、模拟题：删除 71，连续合并

这道比普通题更有价值。

删除叶结点 71 后下溢。

兄弟只有最少关键字：

不能借。

所以第一次合并。

结果父结点又发生下溢。

再与另一兄弟以及祖先关键字合并。

最终原根为空：

树高降低 1。

所以 B 树：

插入导致树高增加：根分裂；
删除导致树高降低：根变空。

(Any Docs)

五十二、2023 真题：B 树概念综合判断

题目考四个说法，大意包括：

插入可能增加树高；
删除会影响叶层；
查找一定要到叶结点；
新插入关键字最终一定留在叶结点。

正确的是前两个。(Any Docs)

为什么第三个错？

B 树：

      [30 60]
     /   |   \

如果找 30：

在根就找到了。

不需要到叶。

为什么第四个错？

插入时最初确实：

插到叶结点。

但如果叶结点溢出：

中间关键字可能向上提升。

所以它最终可能出现在内部结点。

五十三、B+ 树

B+ 树一定与 B 树对比着学。

B 树

内部结点：

可以直接保存记录。

所以搜索可能在内部结点结束。

B+ 树

非叶结点：

只充当索引。

真正的数据记录集中在叶结点。

并且叶结点：

← → ← → ← → ← →

按关键字顺序连接。

五十四、为什么数据库喜欢 B+ 树？

2017 年 408 真题直接问：

哪种应用适合使用 B+ 树？

答案：

关系数据库索引。

(Any Docs)

原因至少背四点。

1. 分支更多

内部结点不保存完整记录。

同一个磁盘页可以装更多索引项。

于是：

树更矮

磁盘 I/O 更少。

2. 范围查询强

查：

100 ≤ key ≤ 500

定位 100 后：

100 → 105 → 110 → ... → 500

沿叶结点链即可。

3. 顺序访问方便

天然有叶层链表。

4. 查询路径更稳定

真正记录都在叶层。

五十五、2016 真题：B+ 树和 B 树的区别

题目选项包括：

是否含关键字；
是否同层；
是否能顺序查找等。

真正具有典型区分度的是：

B+ 树特别适合顺序和范围查找。

因为叶结点按顺序链接。(Any Docs)

五十六、B 树与 B+ 树总表

性质	B 树	B+ 树
内部结点保存记录	可以	通常不保存完整记录
查找成功位置	任意层	最终到叶层
叶结点顺序链接	通常没有	有
范围查询	一般	很强
单结点分支数	较多	通常更多
数据库索引	可以	更典型

模拟题中的 B/B+ 树综合题也把这几项全部列为核心差异。(Any Docs)

五十七、散列表 Hash——本章计算题重灾区

散列表与前面的思维完全不同。

BST 是：

不断比较大小。

Hash 是：

直接算地址。

五十八、散列函数

例如：

H (k ey) = k ey mod 7

如果：

k ey = 22

则：

H (22) = 1

于是优先去地址 1 查。

理想情况下：

O (1)

五十九、冲突与同义词

假设：

H (k) = k mod 7

则：

H (22) = 1

H (43) = 1

H (15) = 1

多个不同关键字得到同一散列地址：

冲突。

这些关键字称为同义词。

六十、装填因子

超级重要：

α = \frac{n}{m}

其中：

$n$ ：实际存放关键字数；
$m$ ：散列表长度。

装填因子越大

表越满。

通常：

冲突越多；
ASL 越大。

所以：

不是装得越满越好。

2011 真题就考过：增大装填因子并不能提高散列查找效率；减少冲突、避免聚集才是正确方向。(Any Docs)

六十一、开放定址法

发生冲突就继续找另一个槽位。

最常见：

线性探测

H_{i} = (H_{0} + i) mod m

探测：

H0
H0+1
H0+2
H0+3
...

二次探测

常见形式：

H_{i} = (H_{0} + d_{i}) mod m

其中：

d_{i} = 1^{2}, - 1^{2}, 2^{2}, - 2^{2}, \dots

或者题目直接给出具体公式。

考试一律以题目给出的探测公式为准。

双散列

类似：

H_{i} = (H_{1} (k ey) + i H_{2} (k ey)) mod m

六十二、线性探测的缺点：聚集

例如：

地址： 0 1 2 3 4 5 6 7
       × × × × × ×

一旦形成连续占用区，后来映射到附近的关键字都会被迫加入这个区域。

这就是：

一次聚集 / 堆积现象。

2014 真题直接考：

聚集现象最直接影响什么？

答案：

平均查找长度 ASL。

因为探测次数增加。(Any Docs)

六十三、2018 真题：成功 ASL

题目：

长度 7，散列函数：

H (k) = k mod 7

依次插入：

22,43,15

三者：

22 mod 7 = 1

43 mod 7 = 1

15 mod 7 = 1

线性探测：

22 → 地址1
43 → 地址2
15 → 地址3

成功查找次数：

22：1次
43：2次
15：3次

所以：

A S L_{成功} = \frac{1 + 2 + 3}{3}

得到：

A S L_{成功} = 2

(Any Docs)

六十四、Hash 成功 ASL怎么计算

千万不要看元素最终地址决定。

例如：

key 的原始地址 = 3
最终存到 = 7

它成功查找时必须重新：

3 → 4 → 5 → 6 → 7

所以比较次数：

5

核心：

从初始散列地址重新模拟查找。

六十五、Hash 失败 ASL——最容易错的部分

失败查找的基本规则：

从某一个合法初始地址出发，一直探测，直到遇到“从未使用过的空位置”。

于是每个可能初始地址都有一个失败查找长度。

然后求平均。

六十六、2019 真题：经典失败 ASL

题目：

散列表长度 11：

H (k ey) = k ey mod 7

线性探测。

插入：

87,40,30,6,11,22,98,20

最终 0～7 连成连续占用区，8 为空。(Any Docs)

特别注意：

虽然表长为：

11

但是散列函数：

k ey mod 7

其初始地址只能是：

0, 1, 2, 3, 4, 5, 6

所以失败 ASL 的分母：

7

不是 11。

这是 408 极其喜欢挖的坑。

从 0～6 开始，到首次遇到空地址 8，探测次数：

9,8,7,6,5,4,3

所以：

A S L_{失败} = \frac{9 + 8 + 7 + 6 + 5 + 4 + 3}{7}

得到：

A S L_{失败} = 6

六十七、Hash 失败 ASL最关键一句话

一定分清：

表长 $m$

和

散列函数能生成多少种初始地址

二者不一定相同。

例如：

m = 11

但：

H (k ey) = k ey mod 7

则失败查找平均通常从：

0 \sim 6

这 7 个初始地址统计。

六十八、开放定址删除——大陷阱

假设：

地址：5 6 7 8
     A B C

A、B、C 可能都因为冲突形成一个探测链。

如果把 B 删除后直接变：

地址：5 6 7 8
     A 空 C

以后查 C：

5 → 6

看到空位置。

程序以为：

C 不存在。

但实际上 C 在 7。

所以开放定址法删除时：

不能简单置为“从未使用”。

而应该标记：

DELETED

也叫：

删除标记 / 墓碑标记 tombstone。

六十九、2023 真题：删除标记 + 失败 ASL

题目：

长度 5：

H (k) = (k + 4) mod 5

线性探测，插入：

2022,12,25

然后删除 25。

关键就在：

25 原位置不能作为“从未使用的空槽”，必须留下删除标记。

失败查找从五个初始地址开始的探测次数为：

1,3,2,1,2

所以：

A S L_{失败} = \frac{1 + 3 + 2 + 1 + 2}{5}

即：

A S L_{失败} = 1.8

(Any Docs)

七十、2024 真题：Hash 综合大题，非常值得吃透

这是最近非常典型的一道综合计算题。

题目大意：

长度 11 的空散列表，依次插入：

20,3,11,18,9,14,7

散列函数：

H_{0} = (3 k ey) mod 11

冲突探测：

H_{k} = (H_{0} + k^{2}) mod 11

问：

构造散列表并求装填因子；
查 14 的关键字比较序列；
查 8 时在哪个地址确定失败。

(Any Docs)

第一步：20

H (20) = 60 mod 11 = 5

放地址 5。

3

H (3) = 9

放 9。

11

H (11) = 33 mod 11 = 0

放 0。

18

H (18) = 54 mod 11 = 10

放 10。

9

H_{0} = 27 mod 11 = 5

5 被占。

取：

k = 1

得到：

H_{1} = (5 + 1^{2}) mod 11 = 6

放 6。

14

H_{0} = 42 mod 11 = 9

9 被占。

H_{1} = (9 + 1) mod 11 = 10

又被占。

H_{2} = (9 + 4) mod 11 = 2

放地址 2。

7

H_{0} = 21 mod 11 = 10

10 被占。

H_{1} = 0

也占。

H_{2} = 3

放地址 3。

最终：

地址	0	1	2	3	4	5	6	7	8	9	10
key	11	空	14	7	空	20	9	空	空	3	18

装填因子：

α = \frac{7}{11}

七十一、查找 14 的比较序列

重新算：

H_{0} (14) = 9

地址 9：

比较一次。

再探地址 10：

比较一次。

再探地址 2：

成功。

所以比较序列：

3 → 18 → 14

七十二、查 8 什么时候确认失败？

H_{0} (8) = 24 mod 11 = 2

探测：

2

3

6

0

7

地址 7 是真正空槽。

所以：

在地址 7 确认失败。

这道 2024 真题几乎把 Hash 的所有基本操作串起来了。

七十三、链地址法

与开放定址法完全不同。

如果：

H (22) = H (43) = H (15) = 1

可以：

地址1：
22 → 43 → 15

也就是：

每个散列地址挂一条链。

七十四、开放定址 vs 链地址

	开放定址	链地址
冲突	找其他空槽	挂链表
装填因子可否 $> 1$	不可	可以
聚集	可能	没有线性探测那种聚集
删除	需注意 tombstone	链中直接删除
存储	数组	数组 + 链结构

七十五、模拟题：什么时候装填因子可以超过 1？

答案：

链地址法。

因为开放定址每个槽最多一个关键字：

n \leq m

所以：

α \leq 1

链地址一个槽可以挂很多结点，所以可能：

n > m

于是：

α > 1

(Any Docs)

七十六、Hash 的 ASL 由什么决定？

2022 年 408 真题直接考了：

装填因子；
散列函数；
冲突解决方法。

三个都会影响。

答案：

全部。

(Any Docs)

不要产生错误理解：

“Hash 查找就是 $O (1)$ ，跟其他东西都没关系。”

所谓接近：

O (1)

只是平均意义。

如果：

散列函数很差；
装填因子很高；
冲突严重；

完全可能恶化。

七十七、这一章最值得建立的“统一思想”

若用五个思想总结整章，可归纳为下面五个。

思想一：比较型查找就是“不断缩小候选范围”

折半：

[L, R]

BST：

(l o w, hi g h)

BST 合法性判断：

(l o w, hi g h)

完全是一个思想。

思想二：树形查找的效率，本质取决于树高

BST：

查找代价 \approx h

AVL：

h = O (lo g n)

红黑树：

h = O (lo g n)

B 树：

h = O (lo g_{m} n)

所以看到树：

第一反应永远应该是“高度是多少？”

思想三：AVL / 红黑树都在拿更新成本换高度保证

普通 BST：

不调整。

所以插入简单，但可能退化。

AVL：

强平衡。

查找更稳定，更新调整更多。

红黑树：

弱一些的平衡。

牺牲一点查找高度，换更温和的动态维护。

思想四：B/B+ 树优化的不是 CPU 比较次数，而是磁盘 I/O

这是理解 B 树的灵魂。

一个 B 树结点内部可能比较很多关键字。

但这些关键字已经一次读进内存。

真正昂贵的是：

又去磁盘读下一层。

所以目标是：

尽量降低树高

思想五：Hash 不保证“没有冲突”，而是控制冲突成本

好的散列函数不是要求：

永远不冲突。

一般做不到。

真正目标：

分布均匀；
装填因子合理；
冲突处理高效。

七十八、408 中各种结构的比较题

这张表非常值得最后背熟。

结构	查找	插入删除	最坏高度	主要场景
有序数组 + 折半	$O (lo g n)$	$O (n)$	—	静态数据
BST	平均 $O (lo g n)$	平均 $O (lo g n)$	$O (n)$	普通动态查找
AVL	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	查找频繁
红黑树	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	动态更新频繁
B 树	$O (lo g_{m} n)$ 层	对数级	很低	外存
B+ 树	$O (lo g_{m} n)$ 层	对数级	很低	数据库、范围查询
Hash	平均 $O (1)$	平均 $O (1)$	不以树高计	精确匹配

七十九、考场最容易丢分的 12 个坑

有序链表不能直接高效折半查找。
折半/BST 路径判断要维护祖先共同上下界。
判断 BST 不能只检查父子大小。
BST 可能退化成单链。
AVL 不是完全二叉树。
AVL 任意两个叶子的高度差不一定 $\leq 1$ 。
AVL 删除后旋转可能向祖先继续传播。
红黑树不等于 AVL。
B 树关键字可以在内部结点被找到。
B 树插入的新关键字不一定最终留在叶子。
Hash 失败 ASL 的分母不一定等于整个表长。
开放定址删除不能随便把槽置成“从未使用”。

八十、按 408 真题价值，建议这样刷

第一梯队：必须完全掌握

1. 2015 折半查找路径

训练：

区间约束法。

(Any Docs)

2. 2011 BST 查找路径

训练：

把同样的区间法迁移到 BST。

(Any Docs)

3. 2010 / 2021 AVL 插入

训练：

LL、RR、LR、RL 判断 + 旋转。

(Any Docs)

4. 2012 AVL 最少结点数

训练：

N_{h} = N_{h - 1} + N_{h - 2} + 1

(Any Docs)

5. 2022 BST 算法大题

训练：

递归上下界思想。

(Any Docs)

6. 2020 B 树插入

训练：

叶层插入 → 分裂 → 上提 → 继续分裂。

(Any Docs)

7. 2012 / 2022 B 树删除

训练：

前驱/后继 → 借 → 合并 → 向上调整。

(Any Docs)

8. 2019 Hash 失败 ASL

训练：

初始地址空间与表长不同。

(Any Docs)

9. 2023 Hash 删除标记

训练：

tombstone。

(Any Docs)

10. 2024 Hash 综合题

训练：

插入 + 二次探测 + 装填因子 + 成功路径 + 失败路径。

(Any Docs)

八十一、第二梯队：用模拟题补真题空白

重点补三个地方。

红黑树

真题覆盖相对有限，但模拟题已经反复考：

黑高；
红红禁止；
AVL 与红黑树比较；
插入结果；
结构判断。

(Any Docs)

B 树高度公式

模拟题频繁考：

n_{m i n} = 2 ⌈ \frac{m}{2} ⌉^{h - 1} - 1

以及：

n_{m a x} = m^{h} - 1

(Any Docs)

Hash 删除后的 ASL

模拟题把：

链地址；
开放定址；
删除；
成功 ASL；
失败 ASL；

放在同一道题里比较，非常有训练价值。(Any Docs)

八十二、可以预测的几种新考法

结合近年真题和本站模拟题，尤其建议防下面几类。

预测 1：AVL + BST 路径约束综合

给：

AVL 共 $n$ 个结点；
一条看似合法的 BST 查找路径；

问是否可能。

这时要同时满足：

BST 条件

上下界合法。

AVL 条件

路径长度不能超过该结点数允许的最大高度。

模拟题实际上已经出现类似考法。(Any Docs)

预测 2：红黑树高度 + 黑高联合判断

例如：

某红黑树黑高为 $b$ ，最多可能多高？

由于红结点不能连续：

h \leq 2 b

再结合：

h \leq 2 lo g_{2} (n + 1)

做综合判断。

预测 3：B 树连续分裂

给一串关键字：

按顺序插入

让某一次插入：

叶子溢出
↓
父溢出
↓
根溢出
↓
新根

考查是否理解：

B 树树高是在顶部增加。

模拟题也专门强调了这一性质。(Any Docs)

预测 4：B+ 树范围查找过程

很可能不给出只考一句概念，而是：

在内部索引中定位；
到叶结点；
顺着叶链扫描范围。

这是最符合 B+ 树实际应用的考法。

预测 5：Hash 删除 + 二次探测

2023 已考删除标记，2024 又考二次探测。

很自然可以组合：

二次探测表中删除若干元素后，计算失败 ASL。

解法仍然是：

已删除槽 ≠ 从未使用槽。

八十三、最后压缩成考前“脑内公式表”

折半查找最大比较次数

⌊ lo g_{2} n ⌋ + 1

AVL 平衡因子

B F = h_{L} - h_{R}

要求：

∣ B F ∣ \leq 1

AVL 最少结点数

N_{h} = N_{h - 1} + N_{h - 2} + 1

其中：

N_{0} = 0, N_{1} = 1

AVL 旋转

LL → 右旋
RR → 左旋
LR → 先左后右
RL → 先右后左

m 阶 B 树最多关键字/结点

一个结点最多：

m - 1

个关键字。

m 阶 B 树非根结点最少关键字

⌈ \frac{m}{2} ⌉ - 1

高度为 h 的 m 阶 B 树最少关键字

令：

t = ⌈ \frac{m}{2} ⌉

则：

n_{m i n} = 2 t^{h - 1} - 1

最多关键字

n_{m a x} = m^{h} - 1

Hash 装填因子

α = \frac{n}{m}

Hash 成功 ASL

A S L_{成功} = \frac{各已存关键字成功探测次数之和}{关键字数}

Hash 失败 ASL

A S L_{失败} = \frac{各可能初始散列地址的失败探测次数之和}{可能初始散列地址数}

最后这一条一定要记住是可能的初始散列地址数，不能机械写成散列表长度。

八十四、第 7 章真正应形成的解题反射

做题时可以直接按这个判断流程：

看到折半查找
→ 有序吗？
→ 能随机访问吗？
→ 比较次数 / 判定树 / 上下界

看到 BST
→ 左<根<右
→ 查找路径用上下界
→ 删除分 0/1/2 个孩子

看到 AVL
→ 先按 BST 插
→ 自下而上找最低失衡结点
→ LL/RR/LR/RL
→ 涉及高度就想最少结点递推

看到红黑树
→ 先是 BST
→ 根黑、NIL黑、红不相邻、黑高相同
→ 近似平衡，不是 AVL

看到 B 树
→ 先算 m-1
→ 再算 ceil(m/2)-1
→ 插入：溢出→分裂→上提
→ 删除：下溢→先借→不能借再合并

看到 B+ 树
→ 数据在叶层
→ 叶结点链接
→ 数据库 / 范围查询

看到 Hash
→ 先算 H(key)
→ 严格按题目探测公式
→ 成功 ASL 从初始地址重新找
→ 失败查找到真正空槽
→ 删除标记不能当空槽

如果这些反射已经形成，那么第 7 章绝大多数 408 选择题实际上都能稳定解决；真正需要重点练熟的计算过程，就是 AVL 旋转、B 树插删和 Hash ASL。站内真题的命题集中度也正好印证了这一点。(Any Docs)

另外，本站真题“查找”页末尾还收录了 KMP，但按照当前采用的教材体系，KMP 属于前面已经学过的第 4 章串，所以本章未把它重复塞进第 7 章；第 7 章应以折半查找、树形查找、B/B+树和散列查找为主。(Any Docs)