第 7 章 查找
408 数据结构第 7 章 查找复习讲义，涵盖核心概念、重点考点与典型题型。
Last updated on
配套选择题也高度集中在这些过程题上：折半查找路径与 ASL、BST 查找序列是否合法、AVL 旋转、红黑树性质、B 树高度与插删、哈希探测序列等。
一、先建立整章框架
第 7 章本质上只研究一个问题：
给我一个 key，怎样尽快找到它？
不同查找方法，本质区别是：
| 查找结构 | 代表方法 | 核心思想 | 典型复杂度 | 408重要度 |
|---|---|---|---|---|
| 无特殊结构 | 顺序查找 | 一个一个比 | ★★ | |
| 有序顺序表 | 折半查找 | 每次排除一半 | ★★★★★ | |
| 分块结构 | 分块查找 | 先找块，再找元素 | 约 | ★★★ |
| 二叉搜索树 | BST | 小的向左，大的向右 | 平均 | ★★★★★ |
| 高度平衡BST | AVL | BST + 强制平衡 | ★★★★★ | |
| 近似平衡BST | 红黑树 | 放松平衡条件 | ★★★★ | |
| 多路平衡树 | B树 | 一个结点放很多关键字 | 层 | ★★★★★ |
| 数据库索引树 | B+树 | 数据全放叶结点 | ★★★ | |
| 散列表 | Hash | 直接算地址 | 平均 | ★★★★★ |
所以这一章其实可以理解成：
顺序扫描 → 利用有序性 → 利用树结构 → 降低树高 → 最后直接算地址。
二、7.1 查找基本概念：重点是 ASL
1. 查找、查找表、关键字
查找就是在数据集合中寻找满足条件的数据元素。
结果只有两类：
- 查找成功；
- 查找失败。
用于查找的数据集合叫做查找表。
关键字 key 是能够标识记录的数据项。若能唯一确定记录，就是唯一关键字。
2. 静态查找表和动态查找表
这是后面各种结构的选择依据。
静态查找表主要进行查询，不经常插入、删除。
典型选择：
有序顺序表 + 折半查找。
动态查找表需要频繁地插入、删除、查询。
典型选择：
BST、AVL、红黑树、B树、散列表。
这里提醒一个资料内部的小口径问题：7.1 前部文字把“折半查找”也列入了动态查找相关方法，但同一资料后面的 BST 小节明确指出，对于需要频繁插删的动态表，应优先用二叉排序树，而折半查找对应的有序顺序表插删需要移动大量元素。这也是本章后续分析应采用的理解。
三、全章灵魂：平均查找长度 ASL
408这章大量计算题，最后都归结到它。
平均查找长度：
其中：
- ：查到第 个元素的概率；
- ：为了找到它进行关键字比较的次数。
等概率情况下：
于是：
一定记住：
ASL 算的不是元素下标，而是关键字比较次数。
四、7.2 顺序查找
1. 普通顺序查找
假设：
12 37 5 84 26 51查找 26。
就是：
12 ≠ 26
37 ≠ 26
5 ≠ 26
84 ≠ 26
26 = 26比较 5 次。
没有利用任何结构信息，因此最坏情况要把整个表检查一遍。
时间复杂度：
2. 哨兵技巧
资料中的实现从表尾向前搜索，并把第 0 号位置设成 key：
ST.elem[0] = key;
for (int i = ST.TableLen;
ST.elem[i] != key;
--i);
return i;为什么放一个 key？
因为原来每一次循环都需要判断：
i 是否越界？
elem[i] 是否等于 key？设置哨兵后，即使不存在目标，最后一定会在 0 号位置停止。
因此只需判断：
elem[i] != key这就是“哨兵”的意义：
人为制造一个必定成功的位置，消除循环中的边界判断。
五、顺序查找的 ASL
资料算法从后向前查。
如果目标在第 个元素：
等概率查找成功时：
于是：
普通无序表查找失败需要真正的 次关键字比较；资料采用哨兵算法的统计口径，把哨兵位置也计入，因此写为：
考试时应结合题目给出的算法和“比较次数”定义判断。
六、有序表的顺序查找
如果表已经升序：
5 12 18 27 36 51现在查找 25。
比较：
5 < 25
12 < 25
18 < 25
27 > 25看到 27 时就已经可以结束。
因为后面的：
36 51 ...只会更大。
因此有序表能够提前判失败。
失败结点
这是后面折半查找也会出现的重要思想。
对于：
10 20 30不存在的元素被划成：
(-∞,10)
(10,20)
(20,30)
(30,+∞)所以：
个关键字会划分出 个失败区间。
这个结论后面一定反复出现。
七、7.2.2 折半查找——★★★★★
这是第 7 章第一大核心。
资料明确强调折半查找要掌握：查找过程、判定树、查找路径、最多比较次数、成功和失败 ASL。
八、折半查找必须满足什么条件？
两个条件：
条件一：有序
例如：
2 10 25 35 40 65 70 75 81 82 88 100条件二：必须支持随机访问
因此通常要求：
顺序存储结构。
链表虽然也能找到“中间结点”，但需要从头走过去，本身就是 ，失去了二分的意义。
因此牢记：
有序链表也不能高效折半查找。
九、折半查找算法
核心代码：
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (A[mid] == key)
return mid;
else if (A[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;本质就三个分支：
key = mid → 找到
key < mid → 左半部分
key > mid → 右半部分所以每比较一次，问题规模约缩小一半。
十、用完整例子理解二分
数组：
7 10 13 16 19 29 32 33 37 41 43查找 11。
初始：
low = 0
high = 10
mid = 5得到：
A[5] = 29因为：
11 < 29所以：
high = 4现在范围：
7 10 13 16 19中间：
13仍然：
11 < 13进入：
7 10比较 7：
11 > 7于是最后比较 10：
11 > 10此后：
low > high查找失败。
这里一定把过程理解成：
每次比较不是“随便跳”，而是在维护一个可能区间。
十一、折半查找为什么是对数复杂度？
初始还有 个元素。
一次之后：
两次：
比较 次后：
所以：
得到：
因此：
十二、折半查找判定树——考试超级重要
折半查找的整个过程可以画成一棵二叉树。
例如：
1 2 3 4 5 6 7向下取整。
第一次 mid：
4第二层：
2 6第三层：
1 3 5 7所以：
4
/ \
2 6
/ \ / \
1 3 5 7这就是折半查找判定树。
十三、判定树到底表示什么？
根：
第一次比较的元素。
第二层：
第二次可能比较的元素。
第三层：
第三次可能比较的元素。
因此某元素位于第几层：
查找它就需要比较几次。
例如 5 在第三层：
十四、失败结点
不仅成功能画出来，失败也能画。
如果有 个真实关键字，则：
所以判定树里通常画：
- 圆形：成功结点；
- 方形：失败结点。
查找失败时的比较次数：
等于失败结点的父结点所在层数。
因为失败结点本身不存在，并没有真正与它进行比较。
这是 ASL 失败题最容易错的地方。
十五、折半查找树的高度
资料给出：
因此最大关键字比较次数就是树高。
例如有 20 个元素：
所以需要 5 层判定树。
配套题中就直接考过“20 个结点的折半判定树，失败查找长度最小是多少”，这种题就是利用判定树层次做。
十六、折半查找 ASL 怎么算？
最可靠的方法：
不要死背总公式，直接按照判定树逐层统计。
假设某棵树：
第1层：1 个结点
第2层：2 个结点
第3层：4 个结点
第4层：3 个结点共有 10 个元素。
成功 ASL：
得到：
这正是配套模拟题考查的形式。
一个非常典型的 12 元素题
长度为 12，采用向下取整。
各层结点数为：
第1层：1
第2层：2
第3层：4
第4层：5所以：
即：
这就是你配套题里【王道·卷三-Q08】的计算核心。
十七、折半查找路径是否合法怎么判断？
也是高频题。
例如查 52，题目给：
80 → 22 → 76 → 25 → 37 → 52不要只看：
一会变大、一会变小真正的方法是：
维护 key 可能存在的上下界。
目标：
52开始：
(-∞,+∞)看到 80：
52 < 80所以以后必须：
< 80看到 22：
52 > 22以后必须：
22 < x < 80看到 76：
22 < 52 < 76以后：
22 < x < 76不断收缩区间即可。
这一技巧同样适用于：
判断 BST 查找路径是否合法。
十八、7.2.3 分块查找
也叫：
索引顺序查找。
它是顺序查找和折半查找之间的一种折中。
例如数据分 4 块。
重要条件不是：
每块内部有序。
而是：
块内可以无序，但块间必须有序。
例如：
块1：13 7 19
块2：31 22 28
块3：45 50 38满足：
块1所有元素 < 块2所有元素
块2所有元素 < 块3所有元素即可。
配套题也直接考这一性质。
十九、索引表
每一块建立索引项，通常记录：
该块最大关键字
+
该块起始地址查找分两步：
key
↓
查索引表
↓
确定在哪一块
↓
在块内顺序查找因此：
其中：
- ：查索引；
- ：块内查找。
二十、分块查找最优块大小
假设：
n 个元素
b 块
每块 s 个则：
索引和块内都顺序查找时：
因为：
可得到资料中的形式。
最优块长：
最小 ASL：
因此它比线性查找：
好，但又没有折半：
那么快。
优势是动态性更好。
二十一、7.3 树形查找
进入本章第二大模块。
发展路线非常重要：
BST
↓
可能退化
↓
AVL：严格保持平衡
↓
旋转次数可能较多
↓
红黑树：放宽平衡条件
↓
插删更友好二十二、7.3.1 二叉排序树 BST——★★★★★
BST定义：
对任意结点：
左子树所有关键字 < 根
右子树所有关键字 > 根而左右子树本身也必须是 BST。
最重要结论：
BST 的中序遍历必定递增。
例如：
6
/ \
2 8
/ \
1 4
/
3中序：
1 2 3 4 6 8二十三、BST 查找
假设查找 4：
6
/
2
\
4过程：
4 < 6
→ 左
4 > 2
→ 右
4 = 4
→ 成功因此 BST 本质也是：
不断缩小 key 的可能范围。
二十四、BST 查找序列题怎么做？
目标查 363。
假设已经访问：
500因为：
363 < 500以后必须小于 500。
如果再访问：
200因为：
363 > 200以后必须处在：
200 < x < 500接着出现任何：
x < 200或者：
x > 500立即不可能。
所以高频题的万能方法仍然是：
动态上下界法。
你的模拟题连续出了多道这种题。
二十五、BST 插入
BST 的插入其实就是：
先查找，查找失败的位置就是新结点应该插入的位置。
例如依次插入：
45 24 53 12得到：
45
/ \
24 53
/
12新插入结点一定首先成为：
叶结点。
二十六、插入顺序决定树形
这是 BST 最核心的问题。
插入：
1 2 3 4 5得到：
1
\
2
\
3
\
4
\
5已经退化成链表。
查找 5 需要：
5 次比较而如果插入顺序适当：
3 2 4 1 5树高明显降低。
所以：
同一组关键字可以形成不同的 BST。
但：
中序遍历结果相同。
二十七、BST 删除——★★★★★
删除分三类，这个必须完全掌握。
情况 1：叶结点
直接删。
8
/
3删除 3：
8情况 2：只有一个孩子
例如：
8
/
3
/
1删除 3：
8
/
1本质：
让孩子顶替自己。
二十八、情况 3：左右孩子都有
例如：
50
/ \
30 80
/ \
60 90删除 50。
不能直接把整个子树删掉。
选择：
中序前驱或中序后继替换。
中序后继：
右子树中最小的元素。
这里是：
60所以：
50 → 60再去原位置删除 60。
为什么这样能简化？
因为：
中序后继一定没有左孩子。
同理：
中序前驱一定没有右孩子。
于是“两个孩子”问题被转化为“零个或一个孩子”问题。
二十九、BST 的性能
如果树近似平衡：
如果退化成单支树：
资料给出的最坏等概率成功 ASL 为：
所以普通 BST 最大缺陷是：
不能保证高度。
这正是 AVL 出现的原因。
三十、为什么动态查找表更喜欢 BST？
折半查找：
查找快：
但插入、删除要移动数组元素：
BST：
平均查找：
平均插入删除：
而且只改指针。
因此资料总结为：
静态表更适合“有序顺序表 + 折半查找”；动态表更适合 BST。
三十一、7.3.2 AVL 平衡二叉树——★★★★★
AVL =
BST + 高度平衡约束。
定义平衡因子：
AVL 任意结点必须满足：
也就是：
三十二、为什么 AVL 一定快？
普通 BST 最大问题：
1
\
2
\
3
\
4AVL 不允许它这样倾斜。
所以高度稳定在：
于是：
三十三、最小不平衡子树
插入一个结点后，从新结点往根方向回溯。
找到：
离新插入结点最近的，第一个平衡因子绝对值变成 2 的祖先。
记为 A。
以 A 为根的子树称：
最小不平衡子树。
考试旋转时：
只盯这个 A，不要一开始就重画整棵树。
三十四、AVL 四种旋转——必须滚瓜烂熟
最推荐的判断方法：
看从不平衡结点 A 到新结点的路径。
LL
A
/
B
/
C路径：
左 → 左所以 LL。
调整：
右单旋。
结果：
B
/ \
C A口诀：
LL → 右旋。
RR
A
\
B
\
C路径：
右 → 右调整：
左单旋。
结果：
B
/ \
A C口诀：
RR → 左旋。
三十五、LR
A
/
B
\
C路径：
左 → 右不能一次解决。
先：
对 B 左旋。
再：
对 A 右旋。
即：
LR
=
先左旋
+
再右旋三十六、RL
A
\
B
/
C路径：
右 → 左所以：
RL
=
先右旋
+
再左旋三十七、四种旋转一张表记住
| 类型 | 插入位置 | 操作 |
|---|---|---|
| LL | 左孩子的左子树 | 右旋 |
| RR | 右孩子的右子树 | 左旋 |
| LR | 左孩子的右子树 | 先左后右 |
| RL | 右孩子的左子树 | 先右后左 |
最值得记的不是名字，而是：
同向 → 单旋；反向 → 双旋。
并且：
LL 名字描述“失衡方向”，旋转方向恰好相反。
三十八、AVL 构造题应该怎么做？
例如资料中的序列：
15,3,7,10,9,8不要一次性画。
正确流程永远是：
① 按 BST 插入
② 从新结点往上算 BF
③ 找第一个 |BF|=2
④ 判断 LL/RR/LR/RL
⑤ 旋转
⑥ 再插下一个这是最稳妥的做法。
三十九、AVL 删除与插入最大的区别
插入造成失衡后：
通常调整最低的最小不平衡子树后，高度恢复，因此一次局部平衡调整即可。
删除不一样。
删除后某个子树可能真正变矮。
调整完 A 后：
A 子树高度又下降可能导致 A 的父亲继续失衡。
所以：
AVL 删除可能一路向上连续调整。
资料特别强调了这一点。
四十、AVL 最少结点数——重要计算
设高度为 的 AVL 最少有 个结点。
为了“高度尽量大而结点尽量少”，左右子树高度应差 1。
所以：
初值：
于是：
……
这个数列是 AVL“最多比较次数”题的核心。
因为：
给定 ，找最大的 ，满足 。
那么查找最多比较：
四十一、7.3.3 红黑树——★★★★
红黑树可以理解为：
不追求像 AVL 那样绝对平衡，而是追求“别太歪”。
这样插入删除时调整会少很多。
四十二、红黑树五条性质
这是必须背下来的。
1
每个结点：
红 or 黑2
根结点：
黑3
所有 NULL 外部叶结点：
黑4
不能有连续红结点：
红
/
红不允许。
所以：
红结点的父亲和孩子必须是黑色。
5
从某结点到它所有后代 NULL 叶结点的路径中：
黑结点数量相同。
这就是黑高约束。
四十三、红黑树不是 AVL
这是一个超级经典陷阱。
AVL：
红黑树：
不要求这个条件。
它只保证：
所以红黑树属于：
近似平衡 BST。
不是 AVL。
四十四、红黑树高度
资料给出：
因此它虽然不如 AVL 平衡，但仍然保证：
四十五、AVL vs 红黑树——必考比较
| 项目 | AVL | 红黑树 |
|---|---|---|
| 平衡程度 | 更严格 | 较宽松 |
| 树高 | 一般更低 | 可能稍高 |
| 查找 | 一般更好 | 稍逊但仍为 |
| 插入删除 | 调整可能更多 | 通常调整更少 |
| 适合 | 查找特别频繁 | 插删也很频繁 |
所以：
读多写少 → AVL。
频繁插删 → 红黑树。
两者的查找、插入、删除渐近复杂度都可以达到：
配套题就直接比较过 AVL 与红黑树这些性质。
四十六、红黑树插入：理解核心即可
资料对此讲得比较细。
新结点为什么先染红？
如果新结点染黑：
所在路径立刻多一个黑结点，容易破坏“各路径黑高相同”。
染红：
黑高不变。
因此：
如果父亲是黑色：
什么都不用做。
如果父亲也是红色：
出现“红红冲突”。
此时看叔叔。
叔叔也是红色
典型策略：
父亲 → 黑
叔叔 → 黑
祖父 → 红然后：
把祖父当作新的待调整结点继续向上。
叔叔是黑色
类似 AVL：
LL / RR / LR / RL通过：
旋转 + 重新着色
修复。
所以理解成：
AVL 主要靠旋转；红黑树靠“染色 + 旋转”。
四十七、红黑树删除
资料专门提示：
这一部分难度较大，考查概率较低。
因此408复习优先级明显低于：
- 五条性质；
- 高度；
- AVL vs 红黑树；
- 红黑树插入基本思想。
删除只需要先理解一个核心：
删红色通常容易，删黑色容易导致某些路径少一个黑结点。
于是引入“双黑”思想，通过：
- 兄弟颜色；
- 兄弟孩子颜色；
- 旋转；
- 重新着色；
逐步消除双黑。
若时间有限，不建议在第一轮复习里死背红黑树删除全部情况。
四十八、7.4 B 树——本章最大难点之一 ★★★★★
B树出现的根本原因是：
二叉树虽然 CPU 比较次数不多，但如果数据在磁盘上，树太高意味着磁盘 I/O 太多。
磁盘 I/O 比 CPU 比较慢太多。
于是：
二叉树
每结点只有2条分支改成：
一个结点存多个 key
有很多条分支于是树变得非常矮。
这就是 B 树。
四十九、m 阶 B 树是什么意思？
重点：
表示一个结点最多拥有的子树数。
所以：
最大子树数：
最大关键字数：
原因：
如果一个结点有：
K1 K2 K3它把数值区间划分成：
< K1
K1~K2
K2~K3
> K3三个关键字产生四棵子树。
因此：
这是 B 树最基础的关系。
五十、m 阶 B 树结点关键字数范围
除根之外的非叶结点至少：
棵子树。
所以至少关键字：
最多：
即非根结点：
根如果不是叶结点，至少：
2 棵子树也就是至少：
1 个关键字五十一、B 树为什么有序？
一个结点：
P0 K1 P1 K2 P2 ... Kn Pn关键字满足：
其中：
P0 子树 < K1
P1 子树在 K1 和 K2 之间
...
Pn 子树 > Kn这就是 BST 的多路版本。
BST：
< root | > rootB 树：
<K1
K1~K2
K2~K3
...
>Kn五十二、关于“叶结点”的口径要特别注意
你这份资料采用王道常见描述：
最底层的“叶结点”是外部失败结点，不实际存储关键字。
而真正最低一层存储关键字的结点常称：
终端结点。
所以看到题目说：
“B树所有叶结点在同一层”
一定先看题目采用的是哪套定义。
本资料的口径下：
终端结点
↓
外部叶结点（空指针、失败结点）五十三、B 树查找
例如某结点：
20 | 50 | 80查 63。
比较之后知道：
50 < 63 < 80所以进入：
50 与 80 之间的那棵子树进入下一结点继续。
因此一次查找过程包括：
磁盘读一个结点
↓
内存里查该结点的若干关键字
↓
找到下一条子树指针
↓
再读下一结点由于磁盘访问昂贵：
B树最关注的是树高，而不是结点内多比较几次。
五十四、B 树高度计算——高频★★★★★
假设：
n 个关键字
m 阶 B树
高度 h资料中的高度：
不包括最下面的外部失败叶结点。
最小高度
想让树最矮：
每个结点尽可能装满。
每个结点最多：
个关键字。
高度为 时最大关键字：
化简：
所以：
整数题再向上取整。
五十五、B 树最大高度
想让树最高：
每个结点尽可能少装关键字。
除根外每个非叶结点至少：
个孩子。
资料推导：
于是：
这是408非常常见的选择题公式。
你的配套题中就直接考了：
“含 个关键字的 阶 B 树最大高度”。
五十六、B 树插入——★★★★★
B树插入要牢记一句：
先插到最底层终端结点；满了就分裂，中间关键字上升。
步骤如下：
① 按 B 树规则查找插入位置
② 插入关键字
③ 判断结点是否溢出
④ 若溢出，分裂
⑤ 中间关键字上升到父结点
⑥ 父结点若又溢出，继续向上分裂五十七、什么时候溢出？
m 阶 B 树一个结点最多：
个关键字。
插入以后如果有：
个关键字：
溢出。
需要分裂。
五十八、B 树分裂怎么做？
假设插入后关键字为：
K1 K2 ... Km资料采用：
位置的关键字上升。
它左边：
留在原结点。
右边：
放入新结点。
中间关键字：
插入父结点。
5 阶 B 树举例
最大：
个关键字。
若插入后：
10 20 30 40 50出现 5 个关键字。
中间：
30上升。
得到：
30
/ \
10 20 40 50如果父亲也满：
父亲再分裂。
如果一路传到根：
根也分裂。
这时会创建一个新根：
注意：
B树高度增长发生在根部，不是底部。
这是经典陷阱。
五十九、B 树删除——★★★★★
比插入稍难，但其实只需要抓住：
删完不能低于最少关键字数。
除根之外最少：
六十、第一步：如果关键字在非终端结点
例如：
50
/ \
... ...删除 50。
先找：
- 中序前驱；或
- 中序后继。
用它替代 50。
然后：
去终端结点删除那个前驱/后继。
所以最终所有删除问题都可以归约成：
删除终端结点中的关键字。
这和 BST 删除思想高度相似。
六十一、终端结点删除三种情况
情况 1：删完仍然够
如果删除前关键字数至少为：
删除一个以后仍然至少：
所以：
直接删。
六十二、情况 2：自己不够，但兄弟够借
假设：
当前结点关键字太少
右兄弟很多结构：
[父关键字 P]
/ \
当前结点 右兄弟不能直接把兄弟元素横着搬过来，因为会破坏有序区间。
正确操作：
父关键字 P 下来
兄弟边缘关键字上去例如右兄弟够借：
父亲 71
右兄弟 74 ...那么：
71 ↓ 当前结点
74 ↑ 父亲所以本质是：
通过父结点中转。
六十三、情况 3：兄弟也不够借
那就：
合并。
结构：
左结点
+
父亲分隔关键字
+
右结点合并成一个结点。
父亲因此少一个关键字。
问题是：
父亲可能因此也不够。
于是：
删除不足可能向上传播。
这和 AVL 删除的“向上连锁调整”很像。
六十四、根结点的特殊情况
如果合并后：
根已经 0 个关键字，只剩一个孩子。
那么：
删除原根，让唯一孩子成为新根。
于是：
所以 B 树：
- 插入导致高度增加：发生在根分裂；
- 删除导致高度减少：发生在根被合并掉。
六十五、7.4.2 B+ 树——理解为主
资料明确说明：
B 树需要掌握基本操作；B+ 树主要考基本概念。
B+ 树是数据库索引里非常重要的结构。
六十六、B+ 树最核心的设计
B 树：
数据可能存放在任何层。
B+ 树：
真正的数据记录全部放在叶结点。
非叶结点只做：
索引。
因此：
索引
/ \
索引 索引
↓ ↓
叶结点—叶结点—叶结点
真正的数据六十七、B+ 树五个核心性质
按照本资料的口径：
- 分支结点最多 棵子树；
- 非根分支结点至少有：
棵子树；
- 一个分支结点的关键字个数 = 子树数；
- 所有关键字和记录指针最终都出现在叶结点；
- 叶结点按关键字有序，并互相链接。
六十八、B树 vs B+树——★★★★★
这张表务必掌握。
| 对比 | B树 | B+树 |
|---|---|---|
| 有 个关键字 | 棵子树 | 棵子树 |
| 数据位置 | 各层均可能 | 全在叶结点 |
| 非叶关键字 | 真正记录，只出现一次 | 索引副本 |
| 查到非叶相同 key | 可以成功结束 | 还要继续向叶结点 |
| 叶结点链表 | 通常没有 | 有 |
| 范围查找 | 较不方便 | 非常方便 |
| 数据库索引 | 可用 | 更常见 |
六十九、为什么数据库喜欢 B+ 树？
原因 1：非叶结点更小
B+ 树非叶结点不用存完整数据记录，只需要：
key + child pointer所以一个磁盘页可以塞更多索引项。
分支因子更大：
树更矮。
磁盘 I/O 更少。
原因 2：范围查询非常强
例如查：
100 ≤ key ≤ 500先通过树找到 100。
之后：
100 → 101 → ... → 500沿叶结点链表向右扫就行。
所以数据库特别喜欢 B+ 树。
七十、B+树查找的一个经典区别
B 树：
如果内结点已经找到 key，就可以成功。
B+ 树：
即使内结点 key 相等，也只是索引，还必须继续走到叶结点。
因此：
这也是选择题高频判断。
七十一、7.5 散列表 Hash——★★★★★
进入本章第三个超级重点。
前面的所有算法都需要不断：
比较 key
↓
缩小搜索范围散列表想做一件更激进的事：
能不能直接由 key 算出它在哪？
定义：
例如：
如果：
key = 27得到：
那么直接访问地址 1。
理想情况下：
七十二、冲突与同义词
例如：
那么：
同时：
两个不同 key 得到同一个地址。
这叫：
散列冲突。
14 和 27 叫：
同义词。
必须特别明确：
冲突不是程序设计错误，而是哈希中正常且基本无法彻底消除的问题。
真正要解决的是：
冲突以后放到哪里。
七十三、散列函数的构造
资料讲四种。
1. 直接定址法
或者：
优点：
不发生冲突。
缺点：
key 范围大、数据稀疏时特别浪费空间。
七十四、2. 除留余数法——最重要
通常：
取不超过表长、并尽可能接近表长的质数。
目的是尽量均匀。
这是考试中最常见的散列函数。
七十五、3. 数字分析法
例如电话号码、身份证号等。
不同位的分布可能不同。
如果某几位：
0~9 出现得比较均匀就选这些位组成地址。
适用于：
关键字集合预先已知且较稳定。
七十六、4. 平方取中法
先：
然后取中间几位。
因为平方结果的中间位往往同时受 key 多个位影响，所以分布可能更均匀。
七十七、哈希冲突处理——★★★★★
两大类：
开放定址法和：
拉链法七十八、开放定址法
核心：
冲突后，继续在散列表中寻找其他空位。
公式：
区别只在：
怎么选。
七十九、线性探测法
取：
例如：
5 占了。
查：
6
7
8
9
...到表尾后回到 0。
所以就是：
一路向后找空位。
优点：
只要表没满，一定能找到空位。
缺点非常重要：
堆积 / 聚集。
八十、什么叫堆积？
假设：
5 6 7 8已经连续被占。
一个本来散列到 5 的元素：
5 占
6 占
7 占
8 占
→ 放9以后本来散列到 6 的元素又要：
6 7 8 9 ...于是形成越来越长的连续区域。
结果：
冲突越来越严重。
这个现象就是：
一次聚集。
你的模拟题明确覆盖了这一类冲突探测题。
八十一、平方探测法
资料给出的增量：
于是探测：
H+1
H-1
H+4
H-4
H+9
H-9
...相比线性探测：
不再只挤在连续位置。
因此能缓解堆积。
按照本资料口径，使用该形式时表长 取：
形如 的素数。
八十二、双散列法
使用两个散列函数。
第一散列：
决定起点。
第二散列：
决定步长。
于是：
直观理解：
每个 key 都可能有不同的跳跃步长。
比线性探测更不容易形成大堆积。
八十三、伪随机探测
让：
采用伪随机序列。
考试知道思想即可。
八十四、开放定址法删除——经典陷阱★★★★★
假设：
H(A)=5但：
位置5被B占用所以 A 经探测存到：
6现在把 B 直接从 5 删除：
位置5变空以后查 A：
先查5发现：
空！算法会认为：
A 不存在。
但实际上 A 在 6。
所以开放定址法：
需要设置：
删除标记。
查找经过删除标记：
必须继续。
真正的从未使用空位置：
才可以说明失败。
这是非常高频的判断题。
八十五、拉链法
把相同散列地址的元素放到链表。
例如：
如果：
14 → 1
27 → 1
40 → 1就：
HT[1]
↓
14 → 27 → 40优点：
- 不需要在整个数组中四处探测；
- 插入删除方便；
- 特别适合动态表。
八十六、为什么拉链法装填因子可以大于 1？
装填因子：
其中：
n = 实际记录数
m = 哈希地址数开放定址：
每个数组位置最多放一个元素。
因此：
所以：
拉链法：
一个桶可以挂很多结点。
因此：
完全可能。
于是：
也是可能的。
你的王道配套题就直接问了这一点。
八十七、哈希查找过程
假设：
采用线性探测。
查 84：
若：
6：19不等。
继续：
7：20不等。
继续：
8：84成功。
于是比较次数：
八十八、Hash 成功 ASL 怎么算？——★★★★★
这是本章计算题最重要的方法之一。
原则：
每一个已有关键字，从它自己的初始散列地址重新模拟查找，数比较了几次。
例如：
A：1次
B：1次
C：3次
D：2次那么：
即：
千万不要看它最终所在下标直接算。
应该问：
“查找它时从 Hash(key) 开始，需要探测几个位置？”
八十九、Hash 失败 ASL 怎么算？——最容易错★★★★★
开放定址法中：
对每一个可能的初始散列地址，模拟一个不存在的 key，从该地址开始探测，直到碰到真正空位置。
注意：
真正空位置本身也要探测，因此计入查找长度。
例如某次：
起点4：占
5：占
6：占
7：空那么失败比较/探测长度：
不是 3。
因为要访问地址 7 后才能确认：
不存在。
九十、还有一个大坑：到底平均几个初始地址？
如果：
那么散列函数只可能产生：
0~12即 13 个初始地址。
即使物理散列表长度是：
16失败 ASL 也应首先根据题目散列函数的可能初始地址范围分析，而不是机械地除以 16。
这类题一定先看：
Hash 函数值域。
九十一、拉链法的失败 ASL
采用“关键字比较次数”口径时：
一个不存在 key 散到某条链上，需要把该链已有结点全部比较完。
若各桶链长：
0, 2, 0, 1, 3, 0, 1失败 ASL：
因此拉链法中：
空链查找失败可以是 0 次关键字比较。
你配套题的拉链法失败 ASL 正是在考这种统计方式。
九十二、影响散列表性能的三个核心因素
资料明确归纳为：
1 散列函数
分布是否均匀。
2 冲突处理方法
线性探测、平方探测、拉链等效果不同。
3 装填因子
一般：
越大，表越拥挤，冲突越多。
因此散列表 ASL：
不是只由表长决定。
也不是：
“只要 Hash 就一定 O(1)”。
准确说法是：
在散列函数合理、装填因子受控的情况下，平均查找复杂度可以接近 。
九十三、整章 ASL 统一起来理解
这是这一章最重要的抽象。
所有 ASL 本质都在做同一件事：
区别只是：
| 结构 | 比较次数从哪里来？ |
|---|---|
| 顺序查找 | 元素离起点多远 |
| 折半查找 | 判定树层数 |
| BST | 结点深度 |
| AVL | 结点深度 |
| B树 | 主要体现为访问层数 |
| Hash | 探测次数或链表比较次数 |
资料最后也把 ASL 作为整章的统一核心进行归纳。
九十四、成功和失败 ASL 要严格区分
成功：
失败：
个有序关键字：
通常对应 个失败区间。
如果分别假设成功元素等概率：
失败区间等概率：
不能把两个分母混在一起。
九十五、408最常见的五类题，你应该怎么做
第一类：折半查找
看到：
- 查找序列；
- 比较次数；
- 判定树；
- ASL；
- 查找失败。
第一反应：
画判定树。
特别是 ASL：
不要凭感觉，直接数每层结点数。
第二类：BST 路径是否合法
看到：
查找 key = x
访问序列 ...第一反应：
维护上下界。
每访问一个结点，就缩小 key 所在区间。
比死画 BST 快得多。
第三类：AVL 插入
第一反应：
普通 BST 插入
↓
找最低 |BF|=2
↓
看路径 LL/RR/LR/RL
↓
旋转不要直接猜旋转。
第四类：B 树插删
插入只问：
满了吗？
↓
满了
↓
中间关键字上升
↓
分裂删除只问：
删完够吗？
├─够 → 直接删
└─不够
├─兄弟够 → 借
└─兄弟不够 → 合并把这棵“决策树”背下来，B树删除就不会乱。
第五类：Hash
永远按真实过程画表：
算 H(key)
↓
冲突？
↓
按探测规则找
↓
填入表然后：
成功 ASL：
从每个元素自己的 Hash 起点重新找一次。
失败 ASL：
从每个可能起点走到第一个真正空位置。
九十六、最容易混淆的概念
| 易混点 | 正确结论 |
|---|---|
| 有序链表能否高效折半？ | 不能 |
| 折半查找需要什么？ | 有序 + 随机访问 |
| BST一定 ？ | 不一定，最坏 |
| AVL中所有叶结点高度差是否 ≤1？ | 不要求 |
| 红黑树是不是AVL？ | 不是 |
| 红黑树查找一定比AVL快？ | 不是 |
| B树的阶 是什么？ | 最大子树数 |
| B树 个关键字有几棵子树？ | |
| B+树 个关键字有几棵子树？ | |
| B+树数据在哪里？ | 叶结点 |
| B+树内结点命中能否结束？ | 不能，要到叶结点 |
| Hash 是否完全没有比较？ | 不是，冲突后仍需比较 |
| 开放定址能否直接删除？ | 不能 |
| 拉链法装填因子能否大于1？ | 能 |
| Hash一定 ？ | 平均情况下才接近 |
九十七、最后给你一个“第7章主线”
如果把这一章压缩成一句话：
查找效率取决于你能利用多少已有结构信息。
顺序查找：
不知道任何东西
→ 一个一个找折半查找：
知道有序
→ 每次砍掉一半BST：
把有序关系变成树
→ 动态插删更方便AVL：
防止 BST 长歪
→ 强制高度 O(log n)红黑树：
稍微放松平衡
→ 换取更低的更新代价B/B+树：
一次结点访问看很多 key
→ 大幅降低磁盘树高Hash：
直接建立 key→地址映射
→ 平均接近 O(1)九十八、按考研优先级复习
如果你准备408，建议第7章按这个顺序掌握：
第一梯队，必须做到会手算：
折半查找判定树与成功/失败 ASL BST 查找、插入、删除与合法查找路径 AVL 四种旋转 B 树定义、阶数、高度、插入、删除 Hash 构造、线性/平方探测、拉链法、成功/失败 ASL
第二梯队，要理解并会选择题：
分块查找 AVL 最少结点递推 红黑树五条性质及 AVL 对比 B树和 B+树区别 装填因子和哈希性能
第三梯队，第一轮可以降低投入：
红黑树复杂删除调整 B+树具体插入删除实现 较冷门散列函数细节
这与资料本身标出的复习重点基本一致：折半查找、树形查找、B树、散列查找构成本章主干，而红黑树删除和 B+ 树深入操作的优先级明显更低。
如果只记住第 7 章最重要的四句话，就是：
折半查找：画判定树。 AVL：找最低失衡点，看 LL/RR/LR/RL。 B树：插入满了就分裂，删除少了就借或合并。 Hash：先完整构造表，再按真实探测过程算 ASL。