查找的基本概念

• 查找：在一个数据集合中找出满足某种条件的数据元素。
• 查找表：用于查找的数据集合，由同一类型的数据元素构成。
  • 静态查找表：查找表执行插入或删除操作时，查找表的结构不发生变化。
  • 动态查找表：查找表执行插入或删除操作时，查找表的结构发生变化，为保持较高的查找效率，需要动态调整查找表的结构。
• 关键码：可唯一标识数据元素的数据项。

查找的性能分析

$$ASL_{\text{成功}} = \sum_{i=0}^{n-1} p_i \cdot c_i$$

顺序查找

不设监视哨： $$ASL_{\text{成功}} = \frac{n+1}{2}$$ $$ASL_{\text{不成功}} = n$$ 设置监视哨 $n$： $$ASL_{\text{成功}} = \frac{n+1}{2}$$ $$ASL_{\text{不成功}} = n+1$$

有序顺序表的顺序查找

$$ASL_{\text{成功}} = \frac{n+1}{2}$$ $$ASL_{\text{不成功}} = \frac{1}{n+1} \left(\sum_{i=0}^{n - 1}(i+1) + n\right) = \frac{n}{2} + \frac{n}{n+1}$$

折半查找

使用折半查找进行的查找次数为 $\lceil \log_2 (n+1) \rceil$。 即为 $n$ 个结点的完全二叉树的深度。

二叉查找树

二叉查找树又称二叉排序树，是一棵空树或者具有以下性质的二叉树：

• 每个节点都有一个关键码，所有节点的关键码互不相同。
• 若左子树不空，则左子树上所有节点的关键码均小于根节点的关键码。
• 若右子树不空，则右子树上所有节点的关键码均大于根节点的关键码。
• 左右子树也分别为二叉查找树。

对于二叉查找树 $T$，其中序遍历序列是一个递增序列。

二叉查找树的查找

二叉查找树的插入

二叉查找树的删除

1. 有一棵子树为空，则将双亲结点链接到非空子树上。
2. 两棵子树都不为空，找到右子树的最小关键码结点（即右子树的最左结点），或者左子树的最大关键码结点（即左子树的最右结点）替换被删除结点。

AVL 树

AVL 树是一种自平衡二叉查找树，任意结点的左右子树的高度差不超过 1。

平衡因子：结点的左子树的高度减去右子树的高度。

• RR 型：右子树的右子树的深度更大导致的不平衡，需要左单旋转，即将右子树的根结点作为根结点，原根结点作为右子树的左子，原右子树的左子树作为原根结点的右子树。
• LL 型：左子树的左子树的深度更大导致的不平衡，需要右单旋转，即将左子树的根结点作为根结点，原根结点作为左子树的右子树，原左子树的右子树作为原根结点的左子树。
• LR 型：左子树的右子树的深度更大导致的不平衡，需要先左后右旋转，即先对左子树进行左旋转，再对根结点进行右旋转。
• RL 型：右子树的左子树的深度更大导致的不平衡，需要先右后左旋转，即先对右子树进行右旋转，再对根结点进行左旋转。

AVL 树的插入

按照二叉查找树的插入方法插入结点，然后从插入结点到根结点的路径上，检查每个结点的平衡因子，若不平衡，则进行旋转操作。

AVL 树的删除

按照二叉查找树的删除方法删除结点（先采用中序前驱然后再采用中序后继），然后从删除结点到根结点的路径上，检查每个结点的平衡因子，若不平衡，则进行旋转操作。

B 树

索引顺序表

当数据量比较大的时候可以多开辟一个索引表，存储某个数据元素的地址。

1. 稠密索引：一个索引项对应数据表中一个元素。当元素在外存中按加入顺序存放而不是按关键码值有序存放时必须采用稠密索引，这时的索引结构叫做索引非顺序结构。

2. 稀疏索引：当元素在外存中有序存放时，可以把所有 $n$ 个元素分为 $b$ 个子表（块）存放，一个索引项对应数据表中一组元素（子表）。第i个索引项是第i个子表的索引项，$i=0,1,\cdots,n-1$。这种索引结构叫做索引顺序结构。

稠密索引：

稀疏索引：

分块查找

分块查找是一种索引顺序表的查找方法，将数据表分为若干块，每一块中的元素可以是无序的，但是块之间是有序的。 要求 $ID[i - 1].max _- key < ID[i].min _- key$。

多级索引与 m 叉查找树

树中每一个分支结点表示一个索引块，每个索引项给出各子树结点的最大关键码值和结点的地址。

B 树

B 树（也称 B-树）是一种高度平衡的 m 叉查找树，每个结点最多有 $m$ 个子女，最少有 $\lceil m/2 \rceil$ 个子女，根节点最少有 $2$ 个子女。 结点的关键码个数为 $n-1$，关键码按照递增顺序排列。 每个关键码的左子树中的所有关键码小于该关键码，右子树中的所有关键码大于该关键码。 最后一层结点称为叶子结点，其余结点称为内部结点。 查找失败时到达的结点称作失败结点，所有的失败结点都是空结点。

B 树的查找

顺序查找或折半查找结点的关键码，若找到则返回，否则若处于两个关键码之间，则进入对应的子树继续查找。

B 树的插入

插入需要插入到叶子结点，若插入后关键码个数超过 $m-1$，则需要进行分裂操作，将中间关键码（第 $\lceil m/2 \rceil$ 个）上移，左右两部分分别作为两个新结点。

B 树的删除

类似于二叉树的删除，需要用中序前驱或者中序后继替换被删除结点，然后删除中序前驱或者中序后继。 中序前驱或者中序后继一定是叶子结点。

若删除后关键码个数小于 $\lceil m/2 \rceil - 1$，则需要进行合并操作，将两个结点合并为一个结点：

1. 若兄弟结点关键码个数大于 $\lceil m/2 \rceil - 1$，则从兄弟结点借一个关键码。

• 先将二者父节点的关键码下移至当前结点，再将兄弟结点的关键码上移至父节点。

2. 否则将当前结点与兄弟结点合并，二者的父节点关键码下移至合并后的结点。

B+ 树

由于 B 树顺序遍历索引时需要中序遍历整个树，因此开发了 B+ 树。
B+ 树是 B 树的一种变形，其内部结点不存储数据，只存储索引，叶子结点存储数据。
用分块索引的方式，每一层的索引块中存储的是下一层的叶子结点的最大关键码值。

与 B 树 不同的是，要求节点内存储的关键码个数为 $n$，而不是 $n-1$，因此每个节点内的关键码直接对应数据块。
在 B+ 树中，叶子结点之间通过指针相连，形成一个有序链表。

散列表

$$Address = hash(key)$$

散列函数

直接定址法

$$hash(key) = a \cdot key + b$$
会造成较多空间的浪费，在不压缩的情况下，不会产生冲突。

除留余数法

$$hash(key) = key \mod p$$ $p$ 是一个不大于散列表长度的质数。

数字分析法

均匀度： $$\lambda_k = \sum_{i=0}^{r}(a_i^k - n / r)^2$$ 选择 $\lambda_k$ 最小的几位作为散列地址。

显然，数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位需要重新分析，寻找分布均匀的若干位作为散列地址。

平方取中法

取平方后的中间几位作为散列地址。

折叠法

先将关键码分割成位数相等的几部分，然后将这几部分叠加，取叠加后的结果的低 $r$ 位作为散列地址。

• 移位法：最右端对齐相加。
• 分界法：交替反序，最右端对齐相加。

解决冲突的开地址法

开地址法又称闭散列法，指的是当新元素与表中已有元素冲突时，可以将新元素插入到表中的其他位置。但无论怎样都只能在表内找下一个空闲位置。

线性探测法

向后探测直到找到空闲位置。 $$H_i = (H_0 + i) \mod m$$ $m$ 是散列表长度，当采用 除留余数法， $m$ 不为取的质数而为散列表长度。

线性探查方法容易产生“堆积（又称为聚集）”的问题，即不同探查序列的关键码占据了可利用的空闲地址，使得为寻找某一关键码不但需要经历同义词的探查序列，还要经历其他非同义词元素的探查序列，导致查找效率降低。

二次探测法

$$H_i = (H_0 \pm i^2) \mod m$$ $m$ 是散列表长度，它应该是一个值为 $4k+3$ 的素数。

双散列法

$$H_i = (hash(key) + i \cdot hash_-random(key)) \mod m$$ 其中 $hash_-random(key)$ 是一个与关键码 $key$ 相关的伪随机数， $gcd(hash_-random(key), m) = 1$。

$hash_-ramdom$ 的取法很多，当 $m$ 为素数时，可以取 $$hash_-ramdon(key) = \begin{cases} key \mod (m - 1) + 1 \newline\lfloor key / m \rfloor \mod (m - 2) + 1 \newline\cdots \end{cases}$$

解决冲突的链地址法

将 $hash(key)$ 相同的元素存储在同一个链表中。

散列表的性能分析

$$\alpha = \frac{\text{表中已装有的元素个数} n }{\text{表中预设的最大记录数} m}$$

$\alpha$ 称为装填因子，它反映了散列表中元素的密度。

链地址法优于开地址法，除留余数法优于其他散列函数。