07 查找
查找 = 在数据集合里找满足条件的数据。衡量它的尺子是 ASL（平均查找长度）——找一趟平均要比几次。本章一条主线：怎么让每次比较"丢掉"更多无效数据——折半丢一半、BST 按大小分家、B 树一层丢一批、散列直接一步到位。
一、ASL：查找的度量衡
\[ASL = \sum_{i=1}^{n} p_i \cdot c_i \quad (p_i 查第 i 个的概率, \ c_i 比较次数)\]
- 通常等概率 p = 1/n
- ASL 成功 / ASL 失败两个口径，408 大题两个都要求算
二、顺序与折半查找
顺序查找：O(n)，毫无门槛
ASL 成功 = (n+1)/2。对链表也适用（顺序存储非必需）。优化：有序表顺序查找失败时可以提前终止——失败 ASL 会降。
折半查找：O(log n)，只吃有序顺序表
low=1, high=n
while low <= high:
mid = (low + high) / 2 # 向下取整
if key == a[mid]: 找到
elif key < a[mid]: high = mid − 1
else: low = mid + 1
手算例题：有序表 {7, 14, 18, 21, 23, 29, 31, 35, 38, 42, 46}（11 个），找 42：
- mid=6 → a[6]=29 < 42 → low=7
- mid=9 → a[9]=38 < 42 → low=10
- mid=10 → a[10]=42 ✅ 3 次比较
判定树（408 大题）：把每次 mid 画成树——
- 判定树是平衡的 BST 形状：n 个元素，树高 = ⌈log₂(n+1)⌉
- ASL 成功 = 各层结点 × 层号之和 ÷ n。11 个结点的判定树：第 1 层 1 个、第 2 层 2 个、第 3 层 4 个、第 4 层 4 个 ASL = (1×1 + 2×2 + 3×4 + 4×4) / 11 = 33/11 = 3 ✅
- ASL 失败 = 到达 n+1 个失败结点（外部结点）的平均深度
- ⚠️ 折半查找必须顺序存储（要随机访问 mid）——链表不能折半
三、二叉排序树（BST）与平衡的执念（AVL）
BST：左小右大
- 定义：左子树所有结点 < 根 < 右子树所有结点（递归成立）
- 中序遍历得升序序列——判 BST 的标准手段
- 查找/插入 O(h)；删除三情形：叶子直接删；单孩子连上去；双孩子用"中序前驱（左子树最右）或中序后继（右子树最左）"顶替再删那个顶替者
- ⚠️ 致命伤：有序输入插入 → 退化成单斜树，O(n)——n=1000 时查找从 ~10 次变 1000 次
AVL：旋转的艺术
任何结点左右子树高度差 |bf| ≤ 1 的 BST。插入破坏平衡 → 找离插入点最近的失衡结点，四招旋转：
| 情形 | 判断（LL/LR/RL/RR） | 处理 |
|---|---|---|
| LL | 插在左孩子的左子树 | 右单旋 |
| RR | 插在右孩子的右子树 | 左单旋 |
| LR | 插在左孩子的右子树 | 先左旋左孩子，再右旋自己 |
| RL | 插在右孩子的左子树 | 先右旋右孩子，再左旋自己 |
💡 记忆：平衡因子符号连写就是操作名（LL=右旋、LR=左右双旋…）。旋转后子树高度恢复插入前，不需要向上继续调整（这是 AVL 插入的性质；删除则可能向上传播）。
- 手算：依次插入 {50, 30, 70, 20, 40, 35}——插 35 后 50 的 bf=2 且路径 50→30→40 是 LR → 对 50 先左旋 30 再右旋 50，40 升为子树根
- 复杂度：O(log n) 有保证；代价是插入删除的旋转开销——AVL 适合查多改少，改多场景 B 树更省
四、B 树与 B+ 树：磁盘时代的王者
为什么需要 B 树：红黑/AVL 二叉分叉，树高 log₂n——在磁盘上就是 log₂n 次 I/O；磁盘一次 I/O ≈ 0.1ms，太贵。把树的"一结点多孩子"对准"磁盘一块多数据"，层高压到 3~4 层。
B 树（多路平衡查找树，m 阶）
- 每结点最多 m 棵子树、m−1 个关键字；根结点至少 2 棵子树；非根非叶至少 ⌈m/2⌉ 棵子树
- 所有叶子在同一层（绝对平衡）；结点内关键字有序，多路分支
- 查找：结点内（顺序/折半）+ 沿途下坠，最多比 h 次 × 结点内比较
B+ 树（数据库索引的标准答案）
| 维度 | B 树 | B+ 树 |
|---|---|---|
| 数据存放 | 所有结点都存关键字和数据 | 只有叶子存数据，内部结点只放索引 |
| 叶子结点 | 不相连 | 链表串起来 → 范围查询/顺序遍历起飞 |
| 查找稳定性 | 可能到根（时快时慢） | 必到叶子（每次代价一致） |
| 单结点容纳 | 少（存了数据） | 多（只有键）→ 树更矮 → I/O 更少 |
| 典型应用 | 文件系统（NTFS） | MySQL InnoDB |
💡 InnoDB 默认树高 3 层可扛 ~2000 万行——每层一个页（16KB），3 次 I/O 定位任意一行。
五、散列（Hash）：一步直达的极致
基本盘
- 散列函数 Hash(key) → 存储地址：理想 O(1)，冲突（不同 key 映射同址）不可避免——鸽巢原理（key 域 > 表长时必冲突）
- 常用构造法：
- 除留余数：
H(key) = key % p，p 取 ≤ 表长的最大素数（408 铁律） - 直接定址 H(k)=k 或 a·k+b（无冲突但要 key 分布知道）
- 平方取中、折叠（了解）
- 除留余数：
冲突处理两家族
开放定址法（冲突了就在表内另找位置，物理删除是禁忌——要打删除标记）：
| 方法 | 探测序列 | 问题 |
|---|---|---|
| 线性探测 | d, d+1, d+2, …（模 m） | 堆积（聚集）：连续占用越滚越长 |
| 平方探测 | d, d+1², d−1², d+2², … | 缓解堆积；m 必须是 4k+3 型素数才能探遍全表 |
| 双散列 | d + i×H₂(key) | 最好；多算一个散列函数 |
拉链法（链地址法）：同址的挂链表——无堆积、删随便，但指针开销；装填因子 α = 元素数/表长，α 越大 ASL 越大。
ASL 计算（408 大题必考套路）
手算例题：H(key)=key%7，散列表长 7，线性探测，依次插入 {15, 22, 29, 36}：
- 15%7=1 → 放 1 号；22%7=1 冲突 → 探 2 号；29%7=1 冲突 → 探 2、3 号；36%7=1 → 探 2、3、4 号
- 表：
[_, 15, 22, 29, 36, _, _] - ASL 成功 = (1+2+3+4)/4 = 2.5
- ASL 失败：散列到 0 号要探 5 次（0→1→2→3→4→5 空停？注意失败判定要探到空位为止；0 号散列的 key 候选 7,14,21… 从 0 号开始探到 5 号空 = 5 次）——逐散列地址统计到下一个空位的距离再平均：0 号 5 次、1 号 4 次、2 号 3 次、3 号 2 次、4 号 1 次、5 号 1 次、6 号 1 次 → (5+4+3+2+1+1+1)/7 = 17/7 ≈ 2.43
⚠️ 失败 ASL 的分母是散列函数的取值个数 p（不是表长，也不算装填元素数）——最阴的坑，务必看清题目统计口径。
六、各结构查找全家福
| 结构 | 平均 | 最坏 | 备注 |
|---|---|---|---|
| 顺序 | O(n) | O(n) | 无序可用、链表可用 |
| 折半 | O(log n) | O(log n) | 要有序 + 顺序存储 |
| BST | O(log n) | O(n)（退化） | 动态、实现简单 |
| AVL | O(log n) | O(log n) | 旋转维护平衡 |
| B/B+ 树 | O(log n) 树高极低 | O(log n) | 磁盘/数据库 |
| 散列 | O(1) | O(n) | 无序、不支持范围查询 |
七、盲点自测
- 折半查找为什么不能链表？（mid 需要随机访问）
- 11 个元素折半查找判定树第 4 层几个结点？（4 个）
- BST 删除双孩子结点用什么顶替？（中序前驱/后继）
- AVL 插入 LR 型怎么旋？（先左旋左孩子再右旋失衡点）
- B+ 树为什么比 B 树更受数据库欢迎？（叶子链表利于范围查询、内结点纯索引更矮、查找代价稳定）
- 除留余数法的 p 怎么选？（≤ 表长的最大素数）
- 线性探测为什么不许物理删除？（会截断探测链，后面的同义词找不到——打标记软删除）
- 失败 ASL 的分母是谁？（散列函数地址空间大小 p）
八、动手玩
# 线性探测散列表：把本文例题跑一遍
def insert_hash(table, key):
m = len(table)
d = key % 7
while table[d] is not None: # 冲突则线性探测
d = (d + 1) % m
table[d] = key
def asl_success(table, keys):
m, total = len(table), 0
for k in keys:
d, cnt = k % 7, 1
while table[d] != k:
d, cnt = (d + 1) % m, cnt + 1
total += cnt
return total / len(keys)
t = [None] * 7
for k in (15, 22, 29, 36):
insert_hash(t, k)
print(t) # [None, 15, 22, 29, 36, None, None]
print(asl_success(t, [15, 22, 29, 36])) # 2.5，与手算一致
参考资料
- 王道《数据结构考研复习指导》第 7 章
- 《MySQL 是怎样运行的》——B+ 树在 InnoDB 里的落地细节（儿童版数据库内核书，极佳）
- 09-磁盘与固态硬盘——为什么磁盘时代树要"矮胖"：I/O 代价模型
- 刷题理模型——哈希题单（两数之和、字母异位词分组）
💬 评论