数据结构第 8 章：查找——ASL、平衡树与哈希表
查找是整门课的收口：前面所有结构存在的意义，最后都落到"能不能更快地找到我要的东西"。这一章的评价指标只有一个——平均查找长度 ASL（查找过程中关键字比较次数的期望值）。所有算法之间的比较，都是在比 ASL。
一、ASL：唯一的评价标准
ASL = Σ(Pᵢ × Cᵢ)，Pᵢ 是查找第 i 个元素的概率（等概率时取 1/n），Cᵢ 是找到它需要的比较次数。
注意 ASL 分成功和不成功两种，题目问哪个要看清楚。不成功 ASL 是指查一个不存在的关键字要比较多少次。
二、线性表的三种查找
顺序查找：从头到尾逐个比。
- 成功 ASL = (n+1)/2，不成功 ASL = n（或 n+1，取决于是否带哨兵）
- 优点：对表的结构无任何要求，有序无序都行
- 优化：哨兵法（把待查值放在 0 号位，循环里就不用判越界，比较次数减少一半的判断）
二分（折半）查找：要求有序 + 顺序存储（链表不行，因为不能用下标直接取中点）。
- 判定树是一棵平衡二叉树，成功 ASL ≈ log₂(n+1) − 1，时间复杂度 O(log n)
- 比较次数的上界是 ⌈log₂(n+1)⌉
mid = (low + high) / 2的取整方向（向下/向上）会改变判定树形状，但 ASL 量级不变- ★ 二分查找的边界条件是最容易写错的地方：
while (low <= high)还是<，high = mid - 1还是mid，必须成套使用
分块（索引顺序）查找：把表分成若干块，块内无序、块间有序，另建索引表。
- 先二分（或顺序）查索引确定块，再块内顺序查
- 当块长取 √n、块数也为 √n 时，ASL ≈ √n + 1，达到最优
- 优点：插入删除比有序表容易（只需调整块内），是"静态/动态"之间的折中
三、二叉排序树（BST）
性质：左子树所有结点 < 根 < 右子树所有结点，且左右子树也是 BST。中序遍历得到升序序列——这是 BST 最重要的性质。
- 查找、插入的复杂度与树高有关：平均 O(log n)，最坏 O(n)（插入有序序列时退化成单支链表）
- 删除分三种情况： 1. 叶子：直接删 2. 只有一个孩子：用孩子顶替 3. 有两个孩子：用中序前驱（左子树最大）或中序后继（右子树最小） 替换值，再删那个结点
BST 的 ASL 取决于树的形态，所以"平均 O(log n)"是有条件的——这个缺陷直接催生了平衡树。
四、平衡二叉树（AVL）
定义：任意结点的平衡因子（左子树高 − 右子树高）绝对值不超过 1。
插入后失衡时，按失衡类型做旋转（四种，必须能画出来）：
| 类型 | 情形 | 操作 |
|---|---|---|
| LL | 在左孩子的左子树插入 | 一次右旋 |
| RR | 在右孩子的右子树插入 | 一次左旋 |
| LR | 在左孩子的右子树插入 | 先左旋（对左孩子）再右旋 |
| RL | 在右孩子的左子树插入 | 先右旋（对右孩子）再左旋 |
AVL 树的高度是 O(log n)，所以查找/插入/删除都是 O(log n) 保证。代价是每次插入删除可能要旋转维护平衡。
五、B 树、B+ 树与红黑树（知道各自解决什么问题）
B 树（多路平衡查找树，m 阶）：每个结点最多 m 个孩子、m−1 个关键字，除根外每个结点至少 ⌈m/2⌉ 个孩子；所有叶子在同一层。
- 目的是降低树高，减少磁盘 I/O 次数——一个结点正好装一个磁盘块，一次读盘能比较多个关键字
- 查找、插入、删除都是 O(log n)，但常数远小于二叉树在磁盘上的表现
B+ 树：只有叶子结点存数据（或指向数据的指针），非叶结点只做索引；叶子结点之间用链表相连。
- 两个优势：① 非叶结点不存数据 → 同样大小的块能装更多索引 → 树更矮；② 叶子成链 → 范围查询和顺序遍历极快
- 所以数据库索引（MySQL InnoDB）和文件系统用的是 B+ 树，不是 B 树
红黑树：一种近似平衡的二叉查找树，用颜色约束保证最长路径不超过最短路径的 2 倍。比 AVL 平衡度低、但插入删除旋转次数少，适合频繁修改的场景（Java 的 TreeMap、C++ 的 map 底层）。
六、哈希表（散列表）
思想：由关键字直接算出存储地址，理想情况下查找 O(1)。
构造哈希函数：除留余数法最常用（H(k) = k mod p，p 取小于表长的最大素数）；还有直接定址、数字分析、平方取中、折叠法。
处理冲突：
| 方法 | 做法 | 特点 |
|---|---|---|
| 开放定址·线性探测 | 冲突后顺序找下一个空位 | 简单，但会产生堆积（聚集），性能下降快 |
| 开放定址·二次探测 | 按 1², −1², 2², −2²… 跳 | 减少堆积，但可能探测不到所有位置 |
| 再散列 | 换一个哈希函数再算 | 计算开销大 |
| 链地址法（拉链） | 同地址的元素挂成链表 | 最常用，删除方便，不会堆积 |
装填因子 α = 表中元素数 / 表长。α 越大冲突越多，ASL 越大。哈希表的 ASL 只与 α 有关，与表长 n 无关——这是它和前面所有查找方法的根本区别。
- 开放定址法的 α 必须小于 1（表会满）；链地址法的 α 可以大于 1
- 查找成功的 ASL ≈ 1 + α/2（线性探测），链地址法约 1 + α/2 左右
- 哈希表不支持顺序遍历，也不支持范围查询——这是它相对 B+ 树的短板
七、整章的知识框架
| 查找方法 | 存储要求 | 平均 ASL | 能否动态插入删除 |
|---|---|---|---|
| 顺序查找 | 无 | (n+1)/2 | 能（但要移动） |
| 二分查找 | 有序 + 顺序存储 | ≈log₂n | 难（插入要移动） |
| 分块查找 | 块间有序 | ≈√n | 较容易 |
| 二叉排序树 | 链式 | O(log n)（平均） | 能 |
| 平衡二叉树 | 链式 | O(log n)（保证） | 能 |
| B+ 树 | 磁盘块 | O(log n) | 能（磁盘友好） |
| 哈希表 | 散列 | O(1)（平均） | 能，但不支持有序遍历 |
选型思路：静态数据用二分；动态数据用平衡树/B+ 树；只做等值查找且不在乎顺序用哈希；要范围查询必须用 B+ 树或有序结构。
易错点
- 二分查找的前提是"有序 + 顺序存储"，链表做不到（无法 O(1) 取中点）。题目给链表让你二分，答案是做不到。
- ASL 要区分成功与不成功两种情况，顺序查找成功是 (n+1)/2、不成功是 n（或 n+1，看是否带哨兵）。
- 二叉排序树"平均 O(log n)"是有条件的——插入有序序列会退化成单支链表，最坏 O(n)。
- 哈希表的 ASL 只与装填因子 α 有关，与表长 n 无关；这是它区别于前面所有查找方法的根本点。
- 开放定址法的 α 必须小于 1（否则表满无位可放），链地址法可以大于 1。
这一章在整门课里的位置
本章是整门课的收口：前面所有结构存在的意义，最后都落到"能不能更快找到"。折半查找依赖第 7 章的有序结果；二叉排序树、平衡树、B 树是第 5 章二叉树性质在查找场景的延伸；哈希表则跳出比较模型、直接用地址映射。往后看，这一章的内容直接对应考研 408 的查找大题与工程里的数据库索引选型——B+ 树为什么是数据库默认索引，答案就在这一章。
本篇是《数据结构与算法（93 讲）》第 8 章的知识点摘要。AVL 四种旋转和哈希冲突处理都有手绘推导，见 课程页；上一章 排序。整门课学完后，建议接着看 算法设计与分析（89 讲）。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 数据结构与算法（93讲） 93 讲