B 树、散列表与字符串模式匹配

本节导读

接着上一节，本节讲查找一章剩下的内容：B 树及其基本操作、B+ 树的基本概念、散列表、字符串模式匹配，最后把各种查找方法放在一起比较，对应大纲的「查找算法的分析及应用」。

学完你应该能画出 B 树插入后的分裂过程，能按给定的散列函数和冲突处理方法构造散列表并算出成功、失败的 ASL，能手算 KMP 的 next 数组。

B 树

m 阶 B 树（B 树也叫多路平衡查找树）满足：

• 每个结点至多 m 棵子树、m − 1 个关键字；
• 根结点若不是终端结点，至少有 2 棵子树；
• 除根以外的非叶结点至少有 $\lceil m/2 \rceil$⌈m/2⌉ 棵子树，即至少 $\lceil m/2 \rceil - 1$⌈m/2⌉−1 个关键字；
• 结点内关键字递增，第 i 个关键字左边子树里的关键字都比它小、右边的都比它大；
• 所有叶结点（查找失败时到达的位置，实际不存在）都在同一层。最下面一层带关键字的结点叫终端结点。

含 n 个关键字的 m 阶 B 树，高度 h（不计叶结点那一层）满足

$$\log_m(n+1) \le h \le \log_{\lceil m/2 \rceil}\frac{n+1}{2} + 1$$logm​(n+1)≤h≤log⌈m/2⌉​2n+1​+1

插入：先查找到应插入的终端结点，把关键字插进去；若关键字个数超过 m − 1，就从中间位置 $\lceil m/2 \rceil$⌈m/2⌉ 处分裂，中间的关键字上移到父结点，左右两部分成为两个结点；父结点因此超出时继续分裂，根分裂会使树长高一层。

删除：被删关键字不在终端结点时，用它的直接前驱或后继（一定在终端结点里）替代，转化为删除终端结点中的关键字。删除后关键字个数不少于 $\lceil m/2 \rceil - 1$⌈m/2⌉−1 就结束；少了，先看相邻的兄弟能否借出一个（经父结点转一下），不能借就与兄弟及父结点中夹在中间的那个关键字合并，父结点可能因此继续合并，根被合并空时树变矮一层。

B+ 树

B+ 树是为数据库和文件系统的索引设计的变形（按常用教材的定义）：

比较项	B 树	B+ 树
关键字与子树	n 个关键字的结点有 n + 1 棵子树	n 个关键字的结点有 n 棵子树
关键字出现在哪里	每个关键字只出现一次，各层结点都可能有	全部关键字都出现在叶结点中，非叶结点里的是索引（子树中的最大或最小关键字）
记录的地址	各层结点都可存	只在叶结点中存
查找	可能在非叶结点就找到	每次都要走到叶结点
顺序访问	要中序遍历整棵树	叶结点用指针链成有序链表，可以从最小关键字顺序查找

所以 B+ 树既能从根开始随机查找，也能沿叶结点链做顺序查找和范围查找。

散列表

散列表用散列函数 H(key) 直接算出存储地址。常用的散列函数是除留余数法 H(key) = key mod p，p 一般取不大于表长的最大质数；还有直接定址法、数字分析法、平方取中法等。不同的关键字映射到同一地址叫冲突，处理冲突的方法：

方法	做法	特点
线性探测	依次探查 H + 1、H + 2、…（模表长）	简单，但容易产生堆积（聚集），同义词与非同义词互相挤占
平方探测	依次探查 H + 1²、H − 1²、H + 2²、H − 2²、…	减少堆积，但不能探查到表中所有单元
双散列	用第二个散列函数算出步长	分布更均匀
拉链法	同一地址的关键字链成一个单链表	没有堆积；删除方便；适合经常插入删除

开放定址法（前三种）删除元素时不能真的删掉，只能做删除标记，否则会截断别的元素的探查路径。

散列表的平均查找长度不直接取决于元素个数 n，而取决于装填因子 $\alpha = \dfrac{n}{m}$α=mn​（m 为表长）：α 越大，冲突越多，ASL 越大。查找失败的 ASL 按每个可能的散列地址分别算「比较到空单元为止」的次数再平均；与空单元的那次比较算不算，各教材口径不同，本课计 1 次，题目会写明。

字符串模式匹配

在主串（长 n）中找模式串（长 m）出现的位置。简单匹配算法失配时主串指针回退，最坏 $O(nm)$O(nm)。KMP 算法失配时主串指针不回退，模式串按 next 数组右移，时间复杂度 $O(n + m)$O(n+m)。

next 数组（位序从 1 起，本课约定 next[1] = 0）：next[j] 等于模式串前 j − 1 个字符中「最长的相等前后缀」的长度加 1；没有相等的前后缀时为 1。模式串第 j 个字符与主串失配时，下一步用模式串第 next[j] 个字符与主串的同一个字符比较；next[j] = 0 时主串和模式串都后移一位。例如模式串 abaabc 的 next 为 0、1、1、2、2、3。

next 还可以改进为 nextval：若第 j 个字符与第 next[j] 个字符相同，那次比较注定失配，就再往前跳一次。

查找算法的分析及应用

方法	存储要求	查找的时间	适合
顺序查找	顺序表或链表，可无序	$O(n)$O(n)	小表、无序表、链表
折半查找	有序顺序表	$O(\log_2 n)$O(log2​n)	很少插入删除的静态表
分块查找	块间有序	约 $\sqrt{n}$n​ 量级	既要较快查找又要较方便插入
平衡树、红黑树	链式	$O(\log_2 n)$O(log2​n)	内存中的动态查找表
B 树、B+ 树	外存中的大结点	磁盘访问次数约等于树高	文件、数据库索引；B+ 树还支持范围查询
散列表	数组加散列函数	平均接近 $O(1)$O(1)	按关键字等值查找，不支持有序输出

易错提醒

• ❌ m 阶 B 树的每个非根结点至少有 $\lceil m/2 \rceil$⌈m/2⌉ 个关键字。✅ 至少 $\lceil m/2 \rceil$⌈m/2⌉ 棵子树，即至少 $\lceil m/2 \rceil - 1$⌈m/2⌉−1 个关键字。因为关键字数比子树数少 1。

• ❌ B+ 树中查找一个关键字，可能在非叶结点就结束。✅ B+ 树非叶结点里的只是索引，查找总要走到叶结点。因为记录的地址只存在叶结点里。

• ❌ 散列表的平均查找长度随元素个数 n 增大而线性增长。✅ 它取决于装填因子 α。因为同样存 1000 个元素，表长足够大时冲突仍然很少。

• ❌ 线性探测法的散列表可以直接把要删除的元素置空。✅ 只能做删除标记。因为置空会让后面经过这个单元探查的元素「查找失败」。

• ❌ KMP 算法失配时主串指针也要回退。✅ 主串指针不回退，只移动模式串。因为已匹配部分的信息都记在 next 数组里了。

例题精讲

例题 1（B 树的插入）

依次把 10、20、30、40、50、60 插入一棵空的 3 阶 B 树，画出每次分裂后的结果。

答题要点示范：3 阶 B 树每个结点至多 2 个关键字。插入 30 时结点 [10 20 30] 超出，中间的 20 上移成为新根，左右为 [10]、[30]。插入 40 得 [30 40]；插入 50 时 [30 40 50] 超出，40 上移，根变为 [20 40]，下面三个结点 [10]、[30]、[50]。插入 60 得 [50 60]，不用分裂。最终根 [20 40]，终端结点 [10]、[30]、[50 60]，高度 2。

例题 2（散列表）

散列表地址 0 至 10，H(key) = key mod 11，线性探测处理冲突。依次插入 25、37、14、48、59、3、70、22，求等概率下查找成功的 ASL。

答题要点示范：25 放 3 号，37 放 4 号；14 算出 3，冲突，探查 4、5，放 5 号（比较 3 次）；48 算出 4，放 6 号（3 次）；59 算出 4，放 7 号（4 次）；3 算出 3，放 8 号（6 次）；70 算出 4，放 9 号（6 次）；22 放 0 号。

关键字	25	37	14	48	59	3	70	22
比较次数	1	1	3	3	4	6	6	1

$\mathrm{ASL}_{\text{成功}} = \dfrac{25}{8}$ASL成功​=825​。

点评：3 号到 9 号连成一片，就是线性探测的堆积：同义词和非同义词都在这一段里争位置，越往后插入比较次数越多。

例题 3（KMP）

求模式串 abaabc 的 next 数组。

答题要点示范：j = 1 时为 0，j = 2 时为 1；j = 3 时看「ab」，没有相等前后缀，为 1；j = 4 看「aba」，最长相等前后缀「a」长 1，为 2；j = 5 看「abaa」，为 2；j = 6 看「abaab」，最长相等前后缀「ab」长 2，为 3。next 为 0、1、1、2、2、3。

本节小结

• m 阶 B 树：非根结点关键字数在 $\lceil m/2 \rceil - 1$⌈m/2⌉−1 到 m − 1 之间；插入超了就从中间分裂上移，删除少了先借后合并。
• B+ 树：关键字全在叶结点、叶结点成链，非叶结点只作索引；支持随机查找和顺序、范围查找。
• 散列表：除留余数法加冲突处理；线性探测有堆积，拉链法没有；ASL 取决于装填因子；开放定址删除只做标记。
• KMP：主串不回退，next[j] 是前 j − 1 个字符最长相等前后缀长度加 1，复杂度 $O(n + m)$O(n+m)。