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

查找

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

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树的阶，通常用 $m$ 表示。一颗 $m$ 阶B树，满足如下特性：

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

结点结构如下：

其中

$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$ ，直到找到一个关键字 $x$ 满足 $k \le x$ 或者已检查完所有关键字。
如果找到的关键字 $x$ 等于 $k$ ，则查找成功并返回该节点。
如果没找到关键字 $x$ 或者 $x$ 不等于 $k$ ，则根据 $x$ 的位置，进入对应的子节点继续查找。
重复上述步骤，直到找到关键字或达到叶子节点。

插入

查找关键字位置：首先在 $B$ 树中查找要插入的关键字位置，但停在最后的叶子节点上，而不是回退。
插入关键字：在找到的叶子节点中插入新关键字。
节点分裂：如果该叶子节点关键字数超过了最大值（通常表示为 $2t-1$ ，其中 $t$ 是树的最小度数），则需要分裂该节点： $- $ 把节点分成两部分。 $- $ 上升中间的关键字到父节点。 $- $ 分裂后的两部分成为新的子节点。
递归分裂：如果因为上升的关键字导致父节点也超过了最大关键字数，那么继续递归分裂。
新的根节点：如果根节点分裂，则其中间关键字上升为新的根节点。

删除

删除操作较为复杂，需要考虑多种情况。

查找关键字：首先查找要删除的关键字 $k$ 。
叶子节点中的关键字：如果关键字 $k$ 在叶子节点中，直接删除。
内部节点中的关键字： $- $ 如果 $k$ 的前驱关键字在叶子节点中，找到 $k$ 的前驱关键字，删除它，并在内部节点中用它替换 $k$ 。 $- $ 否则，使用类似的方法与 $k$ 的后继关键字。 $- $ 如果都不行，必须合并节点并递归地删除 $k$ 。
合并节点：如果一个节点在删除后少于 $t-1$ 个关键字，那么它就太小了，需要进行合并或关键字借用操作： $- $ 从兄弟节点借用一个关键字。 $- $ 如果无法借用，就和兄弟节点合并。
递归删除：合并操作可能需要递归到树的上一层。
更新根节点：如果根节点没有关键字，且只有一个子节点，那么那个子节点成为新的根节点。

B+树

B+树是B树的一种扩展。

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

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

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

3 - 散列表查找

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

散列表

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

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

散列函数

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

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

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

冲突处理方法

1. 开放定址法

开放定址法（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$ ）个位置，以此类推，直到找到一个空槽位。
- 查找：与插入操作类似，也按照平方的序列移动。
- 删除：和线性探测法类似，可以使用特殊标记表示槽位已被删除。

双散列法

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

计算公式为

$$H_i = (Hash_1{(key)} + i \times Hash_2{(key)}) \mod m$$

其中 $i$ 为冲突次数，初始为0。

2. 拉链法

拉链法（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。

扩容

扩容（Rehasing）是增加散列表的容量以容纳更多的项并降低装填因子的过程。扩容的主要步骤包括：

创建一个新的、更大的散列表。
遍历旧散列表中的每一项，并使用新的散列函数将它们插入到新的散列表中。
释放旧散列表的内存。

扩容会消耗时间，特别是当散列表中的项数很多时。但是，由于扩容不是经常发生，所以它的平均开销被分摊到了每一次的插入操作上，使得插入操作的平摊时间复杂度仍然为O(1)。

查找