# 查找
## 基本概念
## 顺序查找法
## 分块查找法
## 折半查找法
## 树形查找
- 二叉搜索树
- 平衡二叉树
- 红黑树
## 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 - 树形查找
基于 BST 的查找
使用 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 树的最小键数要求)。
- 子节点指针也相应分配到两个新节点。
- 假设节点有 $m$ 个键(超限),将其分裂为两个新节点:
- 更新父节点
- 将中间键插入到父节点中(保持有序)。
- 如果父节点插入后也溢出,对父节点重复分裂操作(步骤 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)。
对于使用开放定址法的哈希表,扩容的过程如下图所示:
对于使用拉链法的哈希表,扩容前后的哈希表如下图所示: