这是本节的多页打印视图。点击此处打印.

查找

本章在选择题中考察，重点理解折半查找的思想以及散列表查找的冲突处理方法。

1: 数组查找
2: 树形查找
3: 散列表查找

# 查找

## 基本概念

## 顺序查找法

## 分块查找法

## 折半查找法

## 树形查找

- 二叉搜索树
- 平衡二叉树
- 红黑树

## B树和B+树的基本概念

## 散列表

## 字符串匹配模式

## 查找算法的分析和应用

1 - 数组查找

重点掌握折半查找的思想，需要能够手写相关代码。

顺序查找

适用于无序和有序线性表
从线性表的一端开始，逐个检查每个元素，直到找到所需的元素或检查完所有元素为止。

FUNCTION SequentialSearch(A[0...n-1], value):
    FOR i = 0 TO n-1 DO
        IF A[i] == value THEN
            RETURN i    // index of the found value
        END IF
    END FOR
    RETURN -1   // value not found
END FUNCTION

时间复杂度为$O(n)$

折半查找

只能应用于有序列表
它涉及将列表分成两半，并确定所需元素可能在哪一半中，然后对所选的那一半重复此过程。

FUNCTION BinarySearch(A[0...n-1], value):
    low = 0
    high = n-1
    WHILE low <= high DO
        mid = (low + high) / 2
        IF A[mid] == value THEN
            RETURN mid  // index of the found value
        ELSE IF A[mid] < value THEN
            low = mid + 1
        ELSE
            high = mid - 1
        END IF
    END WHILE
    RETURN -1  // value not found
END FUNCTION

时间复杂度为$O(log_2{n})$

分块查找

线性表的分块查找通常应用于一种特定的情境：线性表（例如数组）被分为多个大小相等（或者最后一个块可能较小）的块，并且块内的元素是无序的，但是块与块之间是有序的。也就是说，每个块内的最大（或最小）元素小于下一个块的任意元素。

常用的分块查找策略如下：

先对块索引进行顺序或二分查找以确定所需元素可能所在的块。
然后在确定的块中进行顺序查找。

2 - 树形查找

掌握 B 树和 B+ 树的定义和相关操作，可能在选择题中考察。

基于 BST 的查找

BST, AVL, 红黑树定义

使用 BST、AVL 或红黑树来存储数据，查询方式如下：

从根节点开始。
如果查询的值等于当前节点的值，返回当前节点。
如果查询的值小于当前节点的值，向左子树查询。
如果查询的值大于当前节点的值，向右子树查询。
如果到达空节点，则查询失败，返回 NULL。

树类型	平均情况时间复杂度	最坏情况时间复杂度
BST	$O(log_2{n})$	$O(n)$
AVL	$O(log_2{n})$	$O(log_2{n})$
红黑树	$O(log_2{n})$	$O(log_2{n})$

对于 BST，如果树是极度不平衡的（例如，成为链状结构），查询的最坏时间复杂度为 O(n)。

B 树

B 树，也叫做多路平衡查找树。是一种自平衡的树形数据结构，它广泛应用于数据库和文件系统中，用于高效地存储和检索大量有序数据。

特性

B 树具备以下两个主要特点：

多路搜索树：B 树是一种多路搜索树，意味着每个节点可以拥有多个子节点，而不仅仅是两个（如二叉搜索树）。
- 阶（Order）：B 树的阶定义了每个节点可以拥有的最大子节点数。
平衡性：B 树通过保持所有叶子节点在同一层，确保了树的平衡，从而保证了搜索效率。

一颗 $m$ 阶 B 树，满足如下特性：

树中每个结点最多有 $m$ 棵子树，最多有 $m-1$ 个关键字。
若根节点不是叶子结点，至少有两个子树
除了根节点外的所有非叶结点最少有 $\lceil m / 2 \rceil$ 棵子树，即最少有 $\lceil m/2 \rceil - 1$ 个关键字。

注意

对于 3 阶 B 树，阶数 $m = 3$，$\text{最小键数} = \lceil m/2 \rceil - 1 = 2 - 1 = 1$

3 阶 B 树的非根节点（包括叶子节点和内部节点）最少有 1 个关键字。

对于 5 阶 B 树，阶数 $m = 5$，$\text{最小键数} = \lceil m/2 \rceil - 1 = 3 - 1 = 2$

5 阶 B 树的非根节点（包括叶子节点和内部节点）最少有 2 个关键字。

B 树结点结构如下：

其中

$n$ 为结点中关键字的个数
$K_i (i = 1,2,\cdots,n)$ 为接点中存储的关键字，且满足 $K_1 \lt K_2 \lt \cdots \lt K_n$
$P_i (i = 0,1,\cdots,n)$ 为指向子树根结点的指针，且指针 $P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$，$P_i$ 所指子树中所有结点的关键字均大于 $K_i$

以上图中的 5 阶 B 树为例，说明 B 树的性质：

结点中的孩子个数等于结点中关键字的个数加 1。
除根节点外所有非叶子结点最少有 $\lceil m / 2 \rceil = \lceil 5 / 2 \rceil = 3$ 棵子树（2 个关键字），最多有 5 颗子树（4 个关键字）。
结点中关键字从左到右递增有序，关键字左侧指针所指子树的所有关键字均小于该关键字，右侧正直镇所指子树的所有关键字均大于该关键字。

提示

关于 B 树的查找、插入、删除操作，可以借助 B 树交互演示来帮助自己理解。

查找

B 树查找与普通二叉查找树相似，但在每个节点上，需要进行多次比较。

从根节点开始：
- 检查当前节点的键列表，键按升序排列。
- 比较目标键 $k$ 与节点中的键 $k_i$：
  - 如果 $k = k_i$，找到目标键，返回对应的值（若存储 KV 对）。
  - 如果 $k < k_1$（第一个键），选择最左子节点。
  - 如果 $k_i < k < k_{i+1}$，选择 $k_i$ 和 $k_{i+1}$ 之间的子节点。
  - 如果 $k > k_n$（最后一个键），选择最右子节点。
递归向下：
- 根据比较结果，进入选定的子节点。
- 重复步骤 1，直到到达叶节点或找到目标键。
处理结果：
- 在节点中找到键：返回对应的值（或指针）。
- 到达叶节点仍未找到：键不存在，返回空或失败标志。

注意：B 树允许键出现在内部节点，因此查找可能在内部节点结束，而无需到达叶节点。

插入

B 树的插入过程如下所示：

查找关键字位置：
- 从根结点开始，比较键值与节点中的键，选择合适的子节点继续递归向下，直到找到合适的叶节点（插入点）。
- B 树的所有插入操作 都在叶节点进行。
插入关键字：
- 将新键插入到叶节点的正确位置（保持键的有序性）。
- 如果插入后叶节点的键数量不超过最大限制（$m-1$），插入完成，过程结束。
- 如果插入后键数量超过 $m-1$（即节点溢出），需要进行分裂。
节点分裂：
- 假设节点有 $m$ 个键（超限），将其分裂为两个新节点：
  - 取中间键（第 $\lceil m/2 \rceil$ 个键）作为分隔键。
  - 分隔键上移到父节点。
  - 原节点分裂为两个新节点，分别包含中间键之前的键和之后的键。
- 每个新节点的键数量约为 $\lceil m/2 \rceil - 1$（满足 B 树的最小键数要求）。
- 子节点指针也相应分配到两个新节点。

更新父节点
- 将中间键插入到父节点中（保持有序）。
- 如果父节点插入后也溢出，对父节点重复分裂操作（步骤 3）。
- 分裂 可能递归向上传播，直到某个节点不再溢出或创建新的根节点。
  - 如果根结点分裂的话，则树的层数会增加一层。

下图展示了一个三阶 B 树的多次插入过程：

删除

B 树的删除过程如下所示：

查找关键字：首先查找要删除的关键字 $k$ 。
- 叶子节点中的关键字：
  - 如果键 $k$ 在叶子节点，且节点键数大于$\lceil m/2 \rceil -1$（最小键数），直接删除 $k$。
  - 如果节点键数等于 $\lceil m/2 \rceil - 1$，删除后会导致键数不足，需进行修复（步骤 2）。
- 内部节点中的关键字：
  - 找到 $k$ 的前驱或后继键（通常是左子树的最大键或右子树的最小键，位于叶子节点）。用前驱/后继键替换 $k$，然后在叶子节点中删除该前驱/后继键。
  - 如果替换后叶子节点键数不足，需修复（步骤 2）。
节点键数不足的修复：当删除键后，节点键数少于 $\lceil m/2 \rceil - 1$，需要调整以恢复 B 树性质：
- 借键：如果左/右兄弟节点有多余键，借一个
  - 从父节点取一个键到当前节点。
  - 从兄弟节点取一个键到父节点，相应调整子树指针。
- 合并：如果兄弟节点也没有多余键：
  - 将当前节点与一个兄弟节点合并。
  - 从父节点取一个键作为合并节点的中间键。
  - 更新父节点的键和指针。
  - 如果父节点键数不足，递归对父节点应用修复。
递归处理
- 删除操作可能引发多层节点调整，需递归处理父节点的键数不足问题，直到满足 B 树性质或到达根节点。

特殊情况：删除操作可能引发多层节点调整，需递归处理父节点的键数不足问题，直到满足 B 树性质或到达根节点。

下面以 3 阶 B 树为例说明一下删除的多种情况：

提示

B 树删除过程细节过多，这里建议还是和学习平衡二叉树时采用相同方法，通过实际例子建立直觉即可。

B+ 树

在实际应用中，B 树和 B+ 树通常存储的是键值对（Key-Value），例如在数据库索引或文件系统中，键用于定位记录，值可以是数据本身或指向数据的指针。在上文关于 B 树的说明中，为了突出算法逻辑，我们将 B 树中的元素表示为单个键，省略值的部分。

实际上存储有 KV 对的 B 树的结构如下图所示：

B+ 树是 B 树的一种扩展。在 B+ 树中，只有叶子节点存储数据，而内部节点只存储键。所有的数据记录都存储在叶子节点中，并且叶子节点通过指针连接形成一个有序链表，如下图所示：

特性

一颗 m 阶 B+ 树满足如下条件：

每个分支结点最多有 m 颗子树
结点的子树个数和关键字个数相同
所有的值都出现在叶子节点，内部节点只包含键不包含实际的数据。
叶子节点通过指针相互连接，这为范围查询提供了高效性。
由于内部节点不存储数据，因此每个内部节点可以存储更多的键，从而增加树的扇出，减少树的高度。

操作

B+ 树的操作考察不多，了解与 B 树相应操作的不同之处即可：

查找：
- B 树：所有节点（包括内部节点）存储 KV 对，查找可能在内部节点结束。
- B+ 树：只有叶节点存储 KV 对，查找必须到达叶节点。
插入：
- B 树：所有节点存储 KV 对，分裂时中间键值对整体上移。
- B+ 树：只有叶节点存储 KV 对，分裂时中间键复制到父节点（仅键，不带值），叶节点保留所有键。
删除：
- B 树：内部节点存储 KV 对，删除内部节点键需用后继/前驱替换，可能复杂。
- B+ 树：删除只发生在叶节点，内部节点键仅需调整（复制叶节点键），操作更简单。

B 和 B+ 树对比

特性	B 树	B+ 树
数据存储位置	关键字和数据存在于内部和叶子节点	所有数据都存储在叶子节点，内部节点只保存关键值和子节点的指针
叶子节点结构	叶子节点与内部节点类似，保存关键字和数据	所有叶子节点通过指针链接成链表
分支因子	由于同时保存数据和关键字，可能较小	通常较大，因为内部节点只保存关键字和指针
稳定性	关键字位置可能会频繁变动	数据位置相对稳定
应用场景	适用于小至中等规模的数据存储系统	更常见于大型数据库系统和文件系统
查找效率	在内部节点找到关键字后，查找即完成	查找必须遍历到叶子节点，但由于通常高度较低，效率也很高

3 - 散列表查找

需熟练掌握散列表的冲突处理方法，对于其他知识点了解即可，可能在选择题中考察。

散列表

散列表（hash table），也叫哈希表，是一种常用的数据结构，提供了快速的数据存储和检索操作。它使用一个数组（通常称为桶或槽）来存储数据。为了将数据存储到散列表中，数据项首先与一个键关联，然后使用一个散列函数将该键转换为数组的索引。这样，通过该键可以快速找到相应的数据项。

散列表的关键性能指标是其装载因子，通常表示为 λ。装载因子是散列表中当前存储的元素数量与散列表的容量之比。随着装载因子的增加，散列冲突的可能性也会增加，这可能会降低散列表的性能。

散列函数

散列函数（Hash Function）是一种函数，它接受一个输入（或“键”）并返回一个固定大小的数字序列，通常用作数组的索引。其主要目的是均匀地分布键到数组中，以便在可能的范围内平均分配值，从而最大限度地减少冲突。

一个好的散列函数应具有以下特性：

均匀分布：无论输入数据的分布如何，散列函数都应该确保输出均匀分布在其范围内，以减少冲突。
计算速度：散列函数应该快速计算，这样就不会成为整个哈希过程的瓶颈。
确定性：对于同一输入，散列函数应始终产生相同的输出。
最小冲突：尽管冲突是不可避免的，但好的散列函数应该使它们降到最低。

同义词

在哈希表中，同义词（synonym）指的是多个不同的键（key）通过哈希函数计算后，映射到 同一个哈希表位置（即相同的哈希值或索引）。这通常会导致冲突，因为哈希表的一个槽位（bucket）只能存储一个键值对。

例如：
- 假设哈希函数是 h(key) = key % 10，键 15 和 25 都会映射到索引 5（因为 15 % 10 = 5 和 25 % 10 = 5）。
- 在这种情况下，15 和 25 就是同义词，因为它们在哈希表中竞争同一个位置。

同理，非同义词（non-synonym）指的是通过哈希函数计算后，映射到不同哈希表位置（即不同哈希值或索引）的键（key）。这些键不会竞争同一个槽位，因此不会引发冲突。

非同义词

例如：

假设哈希函数是 h(key) = key % 10：
- 键 15 映射到索引 5（因为 15 % 10 = 5）。
- 键 17 映射到索引 7（因为 17 % 10 = 7）。
在这种情况下，15 和 17 是非同义词，因为它们被哈希函数分配到不同的位置。

查找方式

散列表的查找算法如下：

哈希函数映射：通过哈希函数 h(key) 将键映射到哈希表的索引位置。
访问槽位：根据索引访问哈希表中的对应槽位。
冲突处理：如果发生冲突，通过探测方法计算下一个可能位置，直到找到匹配的键、遇到空槽或遍历完全部位置。
返回结果：找到匹配键则返回对应值，未找到则返回空。

假设数组长度为 n，哈希表查找的最好情况下时间复杂度为 O(1)，但随着冲突次数的增多最坏会恶化到 O(n)。

冲突处理方法

开放定址法

开放定址法（Open Addressing）使用单个数组来存储所有的键值对。当发生冲突时，根据某种系统的方法在散列表中寻找另一个空槽，将键值对存储在那里。

常用的开放定址策略有：线性探测、平方探测和双散列，具体如下：

线性探测法

原理：当发生冲突时，线性探测法会查找下一个可用的槽位（通常是下一个连续的位置），直到找到一个空槽位为止。
操作：
- 插入：当要插入一个新元素并遇到冲突时，它会向前移动到下一个槽位，直到找到一个空槽位。
- 查找：查找时也是一样的，如果在预期的槽位中没有找到元素，它会继续向前移动，直到找到该元素或遇到一个空槽位为止。
- 删除：删除稍微复杂一些，因为直接删除一个元素可能会中断查找其他元素的连续性。通常的做法是用一个特殊的标记替换被删除的元素，表明该槽位已被删除但仍可能在查找时被访问。

平方探测法

原理：与线性探测法相似，但它不是每次冲突后移动到下一个连续的槽位，而是移动到 $1^2$ 、$-1^1$、$2^2$ 、$-2^2$、$3^2$、 $-3^2…$ 位置直到找到一个空槽位。
操作：
- 插入：遇到冲突时，首先尝试移动 $1$ 的平方（ $1^2=1$ ）个位置，然后 $2$ 的平方（ $2^2=4$ ）个位置，接着 $3$ 的平方（ $3^2=9$ ）个位置，以此类推，直到找到一个空槽位。
- 查找：与插入操作类似，也按照平方的序列移动。
- 删除：和线性探测法类似，可以使用特殊标记表示槽位已被删除。

双散列法

原理：双散列法使用两个独立的散列函数：一个是常规的散列函数 $\text{Hash}_1$，另一个是用于冲突解决的散列函数 $\text{Hash}_2$。
操作：
- 插入：当发生冲突时，首先使用第一个散列函数得到基本的索引位置，如果该位置已被占用，则使用第二个散列函数得到一个步长，按这个步长查找下一个槽位，直到找到一个空槽位。
- 查找：与插入相似，首先使用第一个散列函数，如果没找到，则使用第二个散列函数得到的步长继续查找。
- 删除：和上述方法类似，使用特殊标记表示槽位已被删除。

计算公式为

$$H_i = (\text{Hash}_1{(key)} + i \times \text{Hash}_2{(key)}) \mod n$$

其中 $i$ 为冲突次数，初始为 0；$n$ 为哈希表的长度。

拉链法

拉链法（Seperate Chaining）使用数组与链表相结合的方式。散列表的每个槽位都包含一个链表（或其他数据结构，如平衡树）。当发生冲突时，键值对被添加到相应槽位的链表中。

操作：
- 查找：通过散列函数找到对应的索引位置，在该索引的链表中顺序查找键。
- 插入：通过散列函数找到对应的索引位置。若该键在链表中已存在，更新其值；否则，在链表中添加新的键值对。
- 删除：通过散列函数找到对应的索引位置。在链表中查找并删除对应的键值对，若未找到则无操作。

平均查找长度

查找失败

在考题中常常需要计算散列表查找失败时的平均查找长度，这里举一个实例说明。

假设哈希表如下图所示，哈希表的长度为 11，哈希函数为H(key) = key % 7, 采用线性探测法检测冲突。

假如根据哈希函数计算出的初始查询位置为 0，查询失败时根据线性探测法一直向后探测，查找到位置 8 发现该位置为空得出查找失败，查询次数为 9，其他位置可以以此类推计算出来。

当查找一个新的 key 时，初始查询位置根据哈希函数计算可能在 0 到 6 之间，对于每个位置，查询失败时，需要查找的长度如下表所示：

查找失败的平均查找长度为 (9 + 8 + 7 + 6 + 5 + 4 + 3) / 7 = 6。

查找成功

查找成功时的平均查找长度如何计算呢？

只有存储在散列表中的元素才能被成功查找，对于这些元素，查找成功的长度分为两种情况：

使用散列函数 H(key) 查找到某个位置，该位置存储的元素就是 key，查找次数为 1
对于上述情况，该位置存储的元素不是 key，则向下一个位置探测，直到找到元素 key，探测次数为 N，则查找次数为 1 + N

将散列表中的所有元素的查找次数求和，然后处以元素个数，即可得到查找成功时的平均查找长度。

装填因子

装填因子（load factor）是一个衡量散列表“满”的程度的指标，其中装填因子 = 散列表中已存储的项数 / 散列表的总大小。

例如，如果一个容量为 100 的散列表中已经有 70 项，那么装填因子为 0.7。

装填因子的值影响散列表的性能：

当装填因子太小，意味着散列表中有很多空位，这可能导致内存浪费。
当装填因子太大，冲突的概率会增加，从而降低查找、插入和删除的速度。

因此，常常在装填因子达到某个阈值时进行散列表扩容，例如当装填因子大于 0.7 或 0.75。

扩容

扩容（Rehashing）是增加散列表容量以容纳更多元素并降低装载因子的过程。以下是扩容的主要步骤：

创建一个 更大容量 的新散列表，通常采用指数倍增长策略（如容量翻倍）。
遍历旧散列表中的所有元素，使用 新的哈希函数（或调整后的哈希函数）将它们重新插入到新散列表中。
释放旧散列表的内存。

扩容会消耗一定时间，尤其当散列表元素较多时开销较大。然而，由于扩容操作不频繁，其时间成本被分摊到每次插入操作中，使得插入的平摊时间复杂度仍为 O(1)。

对于使用开放定址法的哈希表，扩容的过程如下图所示：

对于使用拉链法的哈希表，扩容前后的哈希表如下图所示：