第六章查找 · 速览

数据结构目录阅读详版下载 Markdown

查找基本概念与静态查找

概念

静态查找表：数据相对稳定、鲜有变化；最便利存储为顺序存储。动态查找表：频繁插入删除，一般用链式存储。
静态查找细分：顺序、折半、插值、分块。

顺序查找

哨兵法：把待查值 x 存入 0 号哨兵位，从 n 下标向前扫到 0；返回下标 m>0 成功、m=0 失败。好处：省去每步越界判断，以一个空间换时间。
性能：失败比较 $n+1$ 次；等概率成功平均 $(n+1)/2$ 次；时间复杂度 $O(n)$ （无序表亦适用）。

折半（二分）查找

前提：顺序存储且有序。每次比中间元素，小走前半、大走后半，区间空则失败。
代码约定：下标从 1 起，low=1、high=size，成功返回 mid、失败返回 0。
性能：成功最少 1 次，最坏成功/失败比较次数均为 $\log_2 n$ 量级（具体次数需取整，最坏成功比较常写作 $\lfloor\log_2 n\rfloor+1$ ）；时间复杂度 $O(\log_2 n)$ 。

插值查找

思想：按值与端点距离估算位置 $mid = low + (high-low)\cdot\dfrac{x-a[low]}{a[high]-a[low]}$ 。
条件：数据有序且分布均匀；理想时间复杂度 $O(1)$ 。分母 $a[high]=a[low]$ 时无法计算需中止。
注意：位置计算很复杂、一次计算比多次数据访问更耗时时，该方法不占优势。

分块查找

定义：大表分若干块，块内可无序、块间必须有序；建索引表存各块最大关键字（升序）。
查找：先在索引表（折半或顺序）定位块，再块内顺序查找。适合数据量大、动态变化（增删只需调整所在块）。
性能：慢于折半，但远快于顺序查找。

二叉查找树（BST）

定义

对每个结点：其左子树上所有结点都比它小、右子树上所有结点都比它大（假设无相等元素）。
易错：仅"左孩子小、右孩子大"不够，须整棵子树与祖先满足大小关系。

查找

小往左、大往右、相等命中、到空失败（递归/非递归均可）。
性能：比较次数最多为树高，故复杂度＝树高；不平衡时退化为单链表 $O(N)$ ，故非对数级别。等概率形态假设下平均约 $1.38\log n$ 。

插入

小于根入左子树、大于根入右子树、相等则不插入重复键，递归到空位新建结点；递归函数形参为指针的非常量引用 BinaryNode*&（引用不能省，用于关联父子）。
性能：本质是查找，复杂度＝树高。

删除（保持仍为 BST）

情况1（叶子）：直接删，父子链置空。
情况2（唯一孩子）：用该孩子顶替。
情况3（两个孩子）：取替身——左子树最大结点（左孩一路向右）或右子树最小结点（右孩一路向左），用替身值替换待删值，再转为删除替身（替身最多一个孩子，归约为情况1/2）。
性能：叶/单孩子删除＝树高量级；双孩子需找替身再下删，最多树高两倍。

问题引出

BST 三种操作复杂度均为树高；退化为单支树时高＝结点数，三操作皆 $O(n)$ ，故需平衡操作。

平衡二叉树（AVL）

定义

平衡因子 BF＝左子树高−右子树高；AVL 要求每结点 $BF\in\{-1,0,1\}$ ，目标是限制树高、查找接近 $O(\log n)$ 。
平衡 ≠ 最矮，但已接近最矮。结点比普通 BST 多一个 height 字段。
查找：与 BST 完全相同（小左、大右、相等命中）。

插入失衡与旋转

新结点 BF=0，自下而上传导：来自左子树父 BF+1、来自右子树父 BF−1。父 BF 变 0 则子树高不变、传导停止；变非 0 继续向上，直到出现 ±2、变 0 或到根。
冲突结点：向上传导中第一个 BF 超出 $\{-1,0,1\}$ 的结点；在其附近调整至平衡。
四种失衡类型（按冲突结点→子→孙方向判定）：

类型	插入方向	处理
LL	左孩子的左子树	右单旋（口诀：右旋插到右子之左）
RR	右孩子的右子树	左单旋（左旋插入左子之右）
LR	左孩子的右子树	先对左孩 RR 左旋，再对冲突结点 LL 右旋
RL	右孩子的左子树	先对右孩 LL 右旋，再对冲突结点 RR 左旋

单旋：LL 取左孩为新根、原根挂为右孩、左孩原右子树改挂原根左侧；RR 对称。旋转后冲突结点与新根 BF 均归 0。LR/RL 双旋后位于顶部的是"孙子结点"。
旋转代码要点：先更新原根 height，再用更新后的原根 height 算新根 height。
插入总结：递归插入子树，若子树高未变即完成；否则按 X 与各键值选单/双旋（以原结点为根），旋转后高度＝插入前，操作结束（插入最多调整一处）。

删除

先按 BST 删除，再沿到根路径向上回溯调整；删除不"幸运"——子树调整后高度不保证不变，可能连串调整。递归删除函数返回布尔值：true＝子树高不变停止，false＝继续向上。
删除发生在 P 左子树（左矮一层）的五种情况：

情况	P 原 BF	处理	是否继续向上
1	0	不调整（BF 变 −1）	高度不变，停
2	+1	不调整（BF 变 0）	高度变矮，继续
3	−1→−2，右孩左子树矮	RR 旋转	高度变矮，继续
4	−1→−2，右孩右子树矮	RL 旋转	高度变矮，继续
5	−1→−2，右孩左右等高	RR 或 RL（RR 简单）	高度不变，停

易错：旋转修复局部失衡后子树仍可能变矮，必须继续向上检查直到某结点高度不变或到根。
adjust(t, subTree)：subTree=1 删在右子树、0 删在左子树；返回 true 高度不变可停、false 继续。
局限：平衡要求高（高度差≤1），插入删除易打破、引发调整，删除调整可能连串。

外部查找与 B 树

外部查找背景

数据量大、存外存无法全入内存；建索引文件（关键字+数据地址，按关键字序存）加速。外存以文件为单位、以数据块为单位与内存交换，整块读入缓冲区。
设计外存算法重点：减少磁盘访问次数。磁带顺序存取；磁盘顺序＋随机存取（术语：磁道/扇区/柱面）。外部查找索引结构：B 树、B+ 树。

B 树定义（m 阶）

增加分叉降低树高（M 叉查找树最佳高度 $\log_M N$ ），把磁盘访问降到小常数。B 树是平衡的 M 叉查找树。
m 阶 B 树为空或满足：①根或是叶、或至少 2 个至多 m 个儿子；②除根与叶外每结点儿子数 $\lceil m/2\rceil\le s\le m$ ；③有 s 个儿子的非叶结点含 $n=s-1$ 个关键字（子树数＝关键字数+1），结点形如 $(n,A_0,(K_1,R_1),A_1,\ldots,(K_n,R_n),A_n)$ ；④所有叶子在同一层、不带信息（空、指针为空）。
关键字 $K_1<\cdots<K_n$ 有序； $A_i$ 为子树地址、 $R_j$ 为关键字对应记录的硬盘地址。一个磁盘块作为一个 B 树结点。
查找：从根逐层下行，结点内按关键字区间选子树指针；每下一层即一次磁盘 IO，必须到达对应位置或落到空叶 F 才判成败。

插入

总在最底层非叶结点；查找定位后按序插入。结点关键字数 ≤ m−1 即结束；已等于 m−1（插入后超员）须分裂。
分裂：超员结点一分为二（前半、后半），居中关键字上移到父结点（父增一关键字一子树）；父若超员递归分裂、沿路径向上传播。复杂度约 2×树高。
易错：5 阶 B 树每结点最多 m−1=4 个关键字，插第 5 个才分裂；上移的是排序后居中的关键字；目标结点未满则不分裂。

删除

删内部关键字：用替身（右子树最左＝后继，或左子树最右＝前驱）覆盖，转为删最底层替身。
删最底层后：仍满足下限即结束；低于下限按先借后合并——左/右兄弟有富余则经父结点中转借（父分隔关键字下移、兄弟端点关键字上移）；左右兄弟都为下限则合并（父分隔关键字下移并入合并结点，父关键字数减一）。
合并致父减一，失衡可逐层向上传播；传到根且根被掏空则整树高度减一（最坏）。

M 的选择

一个磁盘块作一结点（块容量 max 字节、每键 key 字节）： $(M-1)\times key$ + M 个分支地址 + $(M-1)$ 个记录地址 $< max$ ，由此定 M。

B+ 树

定义

动机：B 树可随机查找但按序遍历全部记录是灾难；B+ 树兼顾随机查找与顺序访问（索引顺序文件）。
M 阶 B+ 树性质：①数据记录只存于叶子，非叶结点至多 $M-1$ 个键引导查找（键 i＝子树 i+1 的最小值）；②根或是叶、或有 2~~M 个儿子；③除根外非叶结点儿子数 $\lceil M/2\rceil$~~ $M$ （防退化）；④所有叶在同一层、每叶有 $\lceil L/2\rceil$ ~ $L$ 个数据项；⑤所有叶连成单链表。
查找：从根按区间下行至叶子；必须到达叶子才能判成败（数据地址只在叶子）。

L 与 M 的选择

块 8192 字节、键 32 字节、分支 4 字节：非叶结点需 $36M-32\le 8192$ ，得 $M=228$ 。每记录 256 字节则一块存 $8192/256=32$ 条， $L=32$ ，每叶 16~32 条。通常 $L$ 远小于 $M$ 。

插入与删除

插入：定位叶子。叶不满直接插；叶满则分裂为两个半满叶并更新父；父满则继续分裂，最坏分裂到根（故根允许仅两孩子）。
删除：叶元素降至最小值以下时——邻居有富余则领养（借），邻居也最少则合并（父失一子），向上过滤到根；根只剩一子则删根、其子为新根（唯一使 B+ 树变矮的情况）。

性能与比较

$N$ 记录最坏 $2N/L$ 个叶、深度 $\log_{\lceil M/2\rceil}(2N/L)$ ；一般 3~4 层即够。查找至多约 5 次读磁盘，插删多一次写，分裂/归并至多再加 4 次写（罕见、可均摊忽略）。
B 树 vs B+ 树：B 树关键字与地址可分布在任何结点，查找可停于任一层、时间 ≤ 树高；B+ 树全部在叶子，查找必到叶、时间一定＝树高。两者插删最差均为树高的 2 倍。
B+ 便于按序遍历：头指针指首叶，各叶尾指针链向右邻叶成单链表，顺链即可顺序遍历。

哈希查找

基本概念

散列法：不按大小比较，直接由关键字 KEY 经函数算出存储位置；理想/平均情况下查找可达 $O(1)$ ，最坏情况会受冲突和装填因子影响而退化；不支持有序操作。
直接以关键字作下标在大值域/字符串关键字时不可行：需用散列函数把大数映射为小下标，把字符串解释为整数。

哈希函数

哈希函数 $H$ 以关键字算存储位置，值域 $0\sim m-1$ （m 为表规模）；选择标准：计算快、地址均匀（冲突少）。
五种常用哈希函数：

方法	形式/做法	要点
直接地址法	$H(key)=key$ 或 $a\cdot key+b$	线性变换压缩表空间
除留余数法	$H(key)=key\bmod p$ （+c）	p 为 ≤m 的素数；最常用，避免浪费单元
数字分析法	取数字分布均匀的位组成地址	丢弃各关键字恒同的位
平方取中法	关键字平方取中间各位	适合各位均匀但值域大；中间位与每位相关
折叠法	按定长分组相加、舍进位	适合关键字很长

除留余数法选素数 p 的理由：若 key 全奇、p 偶则结果全奇浪费一半；若 key 全为 5 的倍数、p=95 则只占 1/5 单元。

冲突与解决

冲突（碰撞）：哈希函数一般多对一，两个以上关键字映射到同一单元即冲突。
闭散列表：用表内空余单元，含线性探测、二次探测、再次散列。开散列表：冲突结点链到表外线性表（链地址法）。

闭散列（线性探测）

线性探测：冲突时探测下一单元直到空。迟删除：删除只做标记不真清空（否则清空单元会中断后续探测链使元素查不到）。
状态：0 空 empty、1 活动 active、2 已删 deleted。insert 找 state≠1 的单元（空或迟删都可重用）；remove 沿链遇 state=0 即止，找到只置 2；find 遇 0 返回 NULL，state=2 单元跳过不中断链。

二次探测

地址序列为 $(k+1^2)\bmod m, (k+2^2)\bmod m, (k+3^2)\bmod m,\ldots$ （m 为表长）。定理：表长为素数且至少一半为空时新元素总能插入、且不会探测同一单元两次；可不用昂贵乘除实现。

再次散列（双散列）

用两个散列函数：hash1 算起始地址、hash2 算步长；第 i 次冲突增量 $f(i)=i\times hash2(x)$ 。建议 $hash2(x)=R-(x\bmod R)$ （R 为小于表长的素数）。探测序列 $hash1(x), (hash1+hash2)\bmod M, (hash1+2hash2)\bmod M,\ldots$ 。

开散列（链地址法）

同一散列地址的元素链成一条单链表（同义链）；数组每元素是指向对应链首的指针，采用不带头结点单链表。
insert 头插法（ $O(1)$ ）；析构须释放数组及各链全部结点；remove 因不带头结点需对首结点特殊处理；find 沿对应链顺序比较。

易错（闭散列线性探测计数）

探测到表尾须回绕到 0；比较次数含初始地址那一次在内的每次位置检查。

本章小结

静态查找（少增删，顺序存储）：无序用顺序查找 $O(n)$ ，有序用折半查找 $O(\log_2 n)$ 。
动态查找（频繁增删）：用 BST，平衡时 $O(\log_2 n)$ ；AVL 通过平衡约束控制树高。
外存：B 树/B+ 树为大文件建索引。B 树关键字分布在非叶结点、每关键字仅出现一次、叶为空；B+ 树所有关键字及地址都在叶子、规模更小且支持按序遍历，建索引更常用。
哈希：摆脱关键字比较，靠函数直接映射地址；理想一对一难找，通常有冲突，常用解决法为线性探测、二次探测、链地址法。