大纲对照
- 一查找的基本概念→ 01
- 二顺序查找法→ 01
- 三分块查找法→ 01
- 四折半查找法→ 01
- 五树形查找二叉搜索树、平衡二叉树、红黑树→ 02–04
- 六B 树及其基本操作、B+ 树的基本概念→ 05
- 七散列(Hash)表→ 06
- 八字符串模式匹配→ 07
- 九查找算法的分析及应用→ 各节 ASL + 08
红黑树的删除调整 · 插值查找 / 斐波那契查找。
基本概念、顺序、折半与分块查找
一、基本概念
- 静态查找只查不改(顺序、折半、分块);动态查找查找过程中还要插入删除(BST、AVL、B 树、散列)。
- ASL 成功:等概率时 = 所有元素比较次数之和 / n。ASL 失败:= 所有“失败位置”比较次数之和 / 失败位置数。
二、顺序查找
三、折半查找(二分)
11 个元素的有序表折半查找,求 ASL 成功与 ASL 失败。
ASL 成功 = (1×1 + 2×2 + 4×3 + 4×4) / 11 = 33 / 11 = 3。
失败结点共 12 个:第 3 层有 4 个空位(比较 3 次),第 4 层下有 8 个(比较 4 次)。ASL 失败 = (4×3 + 8×4) / 12 = 11/3。
层数 1、2、3、4 的结点分别有 1、2、4、4 个,正好对应 ASL 成功 = 33 / 11 = 3 里的各项。
- 失败时的比较次数 = 失败结点的父结点所在层数(方形结点本身不比较)。
- “哪个不可能是折半查找的比较序列”:检查序列能否构成判定树上的一条路径——每一步之后的数必须都落在同一侧区间里。
四、分块查找(索引顺序查找)
插值查找、斐波那契查找
折半查找的变种:插值查找按 key 的大小比例估计 mid,适合分布均匀的数据;斐波那契查找用斐波那契数分割区间。大纲未列。
二叉搜索树(BST)
插入与删除
- 插入:查找失败的位置就是插入位置,新结点一定是叶子。
- 删除三种情况:
- 叶子 → 直接删。
- 只有一棵子树 → 让子树顶替它的位置。
- 有两棵子树 → 用它的中序直接后继(右子树最小,即右子树最左下)或直接前驱顶替,再删掉那个后继/前驱(它最多一个孩子,转为情况 1 或 2)。
- 删除一个结点再插回去,树不一定恢复原样(删的是叶子才会恢复)。
- 同一组关键字插入顺序不同,BST 形态不同;有序插入会退化成单链表,查找 O(n)——所以需要平衡。
依次插入 45 24 53 45 12 24 90(重复的不插),求 ASL 成功。
平衡二叉树(AVL)
| 类型 | 新结点插在失衡结点 A 的… | 调整 |
|---|---|---|
| LL | 左孩子的左子树 | A 的左孩子 B 右旋上来当根 |
| RR | 右孩子的右子树 | A 的右孩子 B 左旋上来当根 |
| LR | 左孩子的右子树 | 先左旋再右旋:让 A 的左孩子的右孩子 C 两次上升成为根 |
| RL | 右孩子的左子树 | 先右旋再左旋:C 两次上升成为根 |
依次插入 16 3 7 11 9 26 18 14 15 构造 AVL 树,求最终根结点。
插 11、9:9 插在 11 的左边,16 失衡(LL)→ 11 右旋上来 → 7(3, 11(9, 16))。
插 26:7 失衡(RR,26 在 7 的右孩子 11 的右子树)→ 11 左旋为根 → 11(7(3, 9), 16(26))。
插 18:16 失衡(RL)→ 18 上升 → 11(7(3,9), 18(16, 26))。
插 14、15:14 挂在 16 左;15 挂在 14 右 → 16 失衡(LR)→ 15 上升 → 18 的左子树变为 15(14, 16)。
最终根为 11。
- 判断失衡类型看的是“新结点相对于失衡结点”的位置,而不是相对于它父亲。
- AVL 删除后可能需要从下往上多次旋转(插入最多调整一次)。
- 问“含 n 个结点的 AVL 树最大高度”:反查上面那串数。如 12 个结点最高为 5。
红黑树
插入:新结点一律染红
- 按 BST 插入,新结点为红色(染红不会破坏“黑路同”)。若是根,染黑结束。
- 父亲是黑的 → 结束。
- 父亲是红的(出现红红),看叔叔:
- 叔叔是黑的:按 LL/RR/LR/RL 旋转(同 AVL),然后旋转后的新根染黑、它的两个孩子染红。结束。
- 叔叔是红的:父亲和叔叔染黑,爷爷染红,然后把爷爷当成新插入的结点继续向上检查。
| 对比 | AVL | 红黑树 |
|---|---|---|
| 平衡程度 | 严格(高度差 ≤ 1) | 宽松(最长 ≤ 2 倍最短) |
| 查找 | 略快 | O(log n) |
| 插入/删除旋转 | 多 | 少(插入最多 2 次旋转) |
| 适合 | 查多改少 | 频繁插删(如 C++ map、Java TreeMap) |
红黑树的删除
删除黑结点会破坏“黑路同”,需要按兄弟的颜色和兄弟孩子的颜色分 4 类情况处理(“双黑”调整)。教材标注为了解,大纲考查重在性质与插入。
B 树与 B+ 树
一、m 阶 B 树的规定
3 阶 B 树,高度为 3(不含叶子层),最少、最多有几个关键字?
最少:根 1 个关键字、2 个孩子;其余每结点 ⌈3/2⌉ − 1 = 1 个关键字、2 个孩子 → 结点 1 + 2 + 4 = 7 → 7 个。
二、插入:满了就“分裂”
- 插入位置一定在最底层的非叶结点(终端结点)。
- 插入后关键字数 ≤ m − 1 → 结束。
- 否则(达到 m 个)从中间位置 ⌈m/2⌉ 处分裂:左边留在原结点,右边成为新结点,中间关键字上升到父结点。父结点也满了就继续分裂;根分裂会让树长高 1 层。
三、删除:不够了就“借”或“合并”
- 删的不在终端结点 → 用直接前驱或后继(一定在终端结点)替换,转为删终端结点。
- 删后关键字数 ≥ ⌈m/2⌉ − 1 → 结束。
- 不够了:兄弟够借(兄弟关键字数 > ⌈m/2⌉ − 1)→ 父结点中间的关键字下来,兄弟的一个关键字上去(“父下兄上”);兄弟不够借 → 与兄弟及父结点中间的那个关键字合并,父结点少一个关键字,可能继续向上合并;根被合并空了,树矮 1 层。
四、B+ 树(只要求基本概念)
| 对比 | B 树 | B+ 树 |
|---|---|---|
| 关键字与孩子 | n 个关键字 n + 1 棵子树 | n 个关键字 n 棵子树 |
| 数据(记录指针)放哪 | 所有结点都可能放 | 只在叶子;非叶结点只做索引 |
| 关键字是否重复出现 | 不重复 | 非叶结点中的关键字在叶子中都会再出现 |
| 查找 | 可能在非叶结点就结束 | 一定走到叶子(路径长度相同) |
| 顺序查找 | 不支持 | 叶子用指针链起来,支持顺序 / 范围查找 |
散列(Hash)表
一、散列函数
- 除留余数法(最常用):H(key) = key % p,p 取不大于表长 m 的最大质数。
- 直接定址法 H(key) = a·key + b(不冲突,但可能浪费空间)、数字分析法、平方取中法。
二、处理冲突
| 方法 | 做法 | 注意 |
|---|---|---|
| 线性探测 | H, H+1, H+2, …(mod 表长) | 容易产生聚集(堆积),大大增加 ASL |
| 平方探测 | H, H+1², H−1², H+2², H−2², … | 表长需为 4k + 3 的质数才能探遍;减少聚集 |
| 双散列 | H + i·H₂(key) | 第二个散列函数决定步长 |
| 拉链法 | 同一地址的元素串成一条链表 | 没有聚集;可直接删除;α 可以大于 1 |
- 开放定址法中不能物理删除元素(会截断探测序列),只能做删除标记。
- 散列表的 ASL 取决于装填因子 α = n / m,而不是 n;α 越大冲突越多。
- “聚集”是因为线性探测让不同地址的同义词串在一起;它影响的是 ASL,不影响能否找到。
关键字 19 14 23 01 68 20 84 27 55 11 10 79,H(key) = key % 13,表长 16(地址 0–15),线性探测。求 ASL 成功与失败。
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 14 | 01 | 68 | 27 | 55 | 19 | 20 | 84 | 79 | 23 | 11 | 10 | ||
| 比较次数 | 1 | 2 | 1 | 4 | 3 | 1 | 1 | 3 | 9 | 1 | 1 | 3 |
ASL 失败:H 只能算出 0–12 这 13 个起点。从地址 0 出发比较 1 次(遇到空);从 1 出发要比到 13 号空位,共 13 次;从 2 出发 12 次……从 12 出发 2 次。合计 1 + (13 + 12 + … + 2) = 91 → 91 / 13 = 7。
注意:失败的分母是散列函数可能的取值个数(这里是 13,不是表长 16);“与空位置比较算不算一次”按教材约定算一次,题目另有说明时从之。
拉链法 ASL 成功 = (6×1 + 4×2 + 1×3 + 1×4) / 12 = 21/12 = 1.75,比线性探测的 2.5 小。
字符串模式匹配(KMP)
- 含义:在 P 的第 j 位失配时,让 P 的第 next[j] 位对准主串当前字符继续比;next[j] = 0 表示主串指针后移一位、P 从头比。
- nextval 优化:若 P[j] == P[next[j]],跳过去必然再次失配,于是 nextval[j] = nextval[next[j]];否则 nextval[j] = next[j]。
- 有的教材下标从 0 开始,next 整体减 1(next[0] = −1)。做题先看题目给的约定。
- 更详细的推导和练习见 DS 04 串。
自测与考前速览
| 方法 | 要求 | 平均时间 | 适用 |
|---|---|---|---|
| 顺序查找 | 无 | O(n) | 小表、链表 |
| 折半查找 | 有序 + 顺序存储 | O(log n) | 静态有序表 |
| 分块查找 | 块间有序 | O(√n) | 动态变化不大的表 |
| AVL / 红黑树 | BST | O(log n) | 内存中的动态表 |
| B / B+ 树 | 多路平衡 | O(log n),I/O 少 | 磁盘中的索引 |
| 散列表 | 散列函数 | 理想 O(1) | 按关键字精确查找;不支持范围查找 |
1. 折半查找 n = 1000 时,最多比较几次?
⌈log2(1001)⌉ = 10 次。
2. 为什么折半查找不能用在链表上?
需要随机访问中间元素,链表只能顺序访问。
3. 5 阶 B 树中,非根非叶结点的关键字个数范围?
⌈5/2⌉ − 1 = 2 到 4。
4. 高度为 5 的 AVL 树最少有多少个结点?
12。
5. 红黑树插入新结点为什么染红?
染红不改变任何路径上的黑结点数(不破坏“黑路同”),最多只会出现“红红”冲突,修正代价更小。
6. 散列表的 ASL 与什么有关?
装填因子 α、散列函数、冲突处理方法;与表中元素个数 n 本身无直接关系。
7. 开放定址法为什么不能直接删除元素?
直接删除会把探测序列截断,导致后面的同义词查不到;只能做逻辑删除标记。
折半判定树高 ⌈log2(n+1)⌉,失败看父结点层数。
BST 删双子树结点用中序前驱/后继顶替。
AVL:LL/RR 转一次,LR/RL 孙子上位。
B 树满 m 分裂、少于 ⌈m/2⌉−1 借或并。
散列 ASL 看 α,失败分母是 H 的取值数。
① B+ 树 n 个关键字 n 棵子树。
② B 树叶结点 = 失败结点,n + 1 个。
③ 红黑树插入看叔叔:黑转、红变色上推。
④ 线性探测会聚集,拉链法不会。
⑤ KMP 的 next 下标约定先看清。