408数据结构-查找

1. 基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程。

查找表：用于查找的数据集合，由同一类型的数据元素（或记录）组成。可以修改的查找表为动态查找表，反之为静态查找表。

关键字：数据元素中唯一标识该元素的某个值。

平均查找长度：一次查找的长度是指需要比较的关键字次数。平均查找长度称为 ASL： $\sum_{i=1}^nP_iC_i$。$P_i$ 为查找第 $i$ 个元素的概率，$C_i$ 为找到第 $i$ 个元素需要的比较次数。

2. 基于线性表

2.1 顺序查找

顺序查找又称为线性查找，对于顺序表和链表适用。链表只能进行顺序查找。

从头一个个去找。

假设每个元素被查找到的概率都是一样的，对于有 $n$ 个元素的表，$P_i = \frac{1}{n}$。从头到尾一个一个去找，那么 $C_i = i$。

$$ASL_{\text{成功}} = \sum_{i=1}^n P_i\cdot C_i = \frac{1}{n}\sum_{i=1}^n i = \frac{n+1}{2}$$

查找不成功时，无论不存在的那个关键字是什么，需要比较的次数都是 $n+1$，因此有：

$$ASL_{\text{失败}} = n + 1$$

可以对顺序查找进行一个优化：将被查找的元素从小到大排好序，然后如果当前结点已经比要查找的关键字大了，说明永远找不到了，就结束查找。

我们可以画出一个判定树：

判定树中用方形结点表示失败结点。

判定树有利于我们求 $ASL_{\text{成功}}$ 和 $ASL_{\text{失败}}$。求 $ASL_{\text{成功}}$ 时，考虑圆形结点，一个圆形结点的查找长度为从初始结点到目标结点经过的结点数量，在查找概率相等的情况下，$P_i = \frac{1}{\text{圆形结点数量}}$。求 $ASL_{\text{失败}}$ 时，考虑方形结点，一个方形结点的查找长度为从初始节点到目标方形结点所连的圆形结点，经过的结点数量，在查找概率相等的情况下，$P_i = \frac{1}{\text{方形结点数量}}$。

使用上面这个优化，$ASL_{\text{成功}}$ 不变，仍为 $\frac{n+1}{2}$。$ASL_{\text{失败}}$ 为 $\frac{\sum_{i=1}^n i + n}{n+1} = \frac{n}{2} + \frac{n}{n+1}$，变得更小了。

平均查找长度分为综合考虑和分开考虑。对于一个有 $n$ 个元素的查找集合，每个元素的查找概率为 $p_i$。不在此集合中的元素分布在由这 $n$ 个元素的间隔构成的 $n+1$ 个子集合内，每个子集合的查找概率为 $q_j$，假设如果所有元素的查找概率相同：

• 如果综合考虑，即 $\sum_{i=1}^np_i + \sum_{j=0}^n q_j = 1$，则有 $p_i = q_j = \frac{1}{2n+1}$
• 如果分开考虑，即 $\sum_{i=1}^n p_i = 1, \sum_{j=0}^n q_j = 1$，则有 $p_i = \frac{1}{n},q_j = \frac{1}{n+1}$

在题目中大多情况下，默认时分开考虑的。不过还是要注意仔细阅读题目要求。

2.2 折半查找

折半查找又称二分查找，仅适用于有序的顺序表。

其判定树是这样的：

上面这个判定树中，在等概率情况下，$ASL_{\text{成功}} = \frac{1\times 1 + 2\times 2 + 3\times 4 + 4\times 4}{11} = 3$，$ASL_{\text{失败}} = \frac{3\times 4 + 4\times 8}{12} = \frac{11}{3}$。

对于一个表长为 $n$ 的有序表进行折半查找，其判定树的高度为 $\left \lceil \log_2(n+1) \right \rceil$。

查找一个存在的元素，最多比较次数也为 $\left \lceil \log_2(n+1) \right \rceil$。

查找一个不存在的元素，如果 $n = 2^k - 1$（满二叉树），那么最多比较次数和最少比较次数为 $\left \lceil \log_2(n+1) \right \rceil$。如果 $n \neq 2^k - 1$，那么最多比较次数为 $\left \lceil \log_2(n+1) \right \rceil$，最少比较次数为 $\left \lceil \log_2(n+1) \right \rceil - 1$。

2.3 分块查找

将查找表分成若干子块，块内元素可以无序，块间必须是有序的。可以建一个索引表：

分块查找的平均查找长度由索引查找和块内查找两部分组成。如果索引查找和块内查找均采用顺序查找，且将数据平均分成 $b$ 个块，每个块内有 $s$ 个元素，那么：

$$ASL = L_{索引查找} + L_{块内查找} = \frac{b+1}{2} + \frac{s+1}{2} = \frac{s^2+2s+n}{2s}$$

令 $s = \sqrt{n}$ 可以使得 ASL 最小。

3. 基于树形

3.1 BST

BST 即二叉排序树。

BST 可以是一颗空树。

BST 要求左子树严格小于当前结点，右子树严格大于当前结点，这就意味着 BST 是不能有相同关键字的点。

插入时，会遍历这个 BST，找到一个合适的位置，插入成叶子结点。

删除时：

• 如果被删除的结点是叶子结点，则会直接删除。
• 如果被删除的结点仅有左儿子或者右儿子，则会直接将左儿子/右儿子替换掉被删除结点。
• 如果被删除的结点左右儿子都有，那么可以有两种删法：
  • 将被删除结点的直接后继替代掉被删除结点，然后递归地删除直接后继。
  • 用直接前驱替代。

BST 的最好情况的平均查找长度是 $O(\log_2n)$，最坏情况下平均查找长度为 $O(n)$。

3.2 AVL

AVL 即平衡二叉树。

平衡二叉树：任意结点的左右子树的高度差的绝对值不能超过 $1$。

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

插入和删除操作类似 BST，但是有可能操作之后不再保持平衡了，需要通过旋转操作来使得树重新维持平衡。

对于插入操作，从插入结点向上寻找第一个平衡因子绝对值大于 $1$ 的祖先结点，然后根据插入结点是在不平衡结点的左右孩子的左右子树来确定旋转方式：

• 插入结点在不平衡结点的左孩子的左子树中，进行 LL 旋转

• 插入结点在不平衡结点的右孩子的右子树中，进行 RR 旋转

• 插入结点在不平衡结点的左孩子的右子树中，进行 LR 旋转

• 插入结点在不平衡结点的右孩子的左子树中，进行 RL 旋转：

对于删除操作，当我们将结点删除之后，我们从删除结点的位置向上查找第一个不平衡的结点。然后考虑这个不平衡结点、不平衡结点中高度最高的子节点、高度最高的子节点的高度最高的子节点，这三者的位置关系，进行 LL，LR，RR，RL 旋转。

在 AVL 上的查找长度最多为树的深度。假设 $n_h$ 表示深度为 $h$ 的平衡二叉树中含有的最少节点数。显然，有 $n_0, n_1=1,n_2=2$，同时有：$n_h = n_{h-2} + n_{h-1} + 1$，如图：

3.3 红黑树

3.3.1 性质

• 性质一：每个节点都是红色或黑色
• 性质二：根节点是黑色的
• 性质三：叶节点（虚构的外部节点，也叫做 NULL 节点）是黑色的
• 性质四：不存在两个相邻的红色节点，红色节点连出去的点一定是黑色的
• 性质五：对于每个节点，从该节点到任意一个叶节点的简单路径上，所含黑色节点的数量是相同的

黑高：从某结点出发，到达一个叶结点的任意一个简单路径上的黑结点总数称为该结点的黑高（不包含起始结点）。

红黑树中每个结点（包括红色和黑色）称为内部结点，NULL 结点称为外部结点。

• 结论0：NULL 节点的数量有 $n+1$ 个。

• 结论1：从根到叶结点的最长路径不大于最短路径的 $2$ 倍。

  • 最短路径一定是全是黑色结点的路径。最长路径一定是黑白相间的路径。
  • 这就使得左右子树之间的高度最多相差一倍，保证了一定的平衡性。

• 结论2：有 $n$ 个内部结点的红黑树的高度 $h \le 2\log_2(n+1)$。

  • 根据结论一可知，从根到叶子结点的任何一条简单路径上都至少有一半是黑节点，因此树的黑高 $bh \ge \frac{h}{2}$。又有 $n\ge 2^{\frac{h}{2}}-1$ ，于是就得到了该结论。

3.3.2 插入

新插入的点为红色。

• （情况一）插入结点是根节点，那么直接变黑
• 考虑插入结0点的父节点的兄弟结点颜色（即插入结点的叔叔结点）
  • （情况二）叔叔节点为红色：叔叔节点和父亲节点变黑，爷爷节点变红。爷爷节点变红之后可能又和上面的红色节点冲突了，那么又需要将爷爷节点视为当前插入的节点，然后继续考虑这里的情况一、情况二、情况三。
  • （情况三）叔叔节点为黑色：此时需要考虑当前节点，当前节点的父节点，当前节点的爷爷节点，三者的位置关系：LL（右旋再变色），RR（左旋再变色），LR（先左旋，转为 LL 情况，再右旋变色），RL（先右旋，转为 RR 情况，再左旋变色）

3.3.3 删除

像 BST 那样删除。最后真正要删除的节点一定是仅有左子节点或者仅有有子节点或者本身就是叶子节点。

如果没有叶子节点，那么必然是这两种情况：

• （情况1）像上图一样，只有左孩子或者是右孩子，那么可以直接用左孩子/有孩子替代掉当前节点，然后将左孩子/有孩子变黑。
• 没有孩子，是叶子节点，那么又根据被删除的叶子节点的颜色分成两种情况：
  • （情况2）红色：那么直接删除就好了。
  • （情况3）黑色，那么将其删除之后，性质五就无法满足了。我们可以视为这个黑色节点删除之后变为一个双黑节点。双黑节点本身违反了性质一，因此我们需要想办法解决掉这个双黑节点。解决时又需要讨论其兄弟节点的颜色情况：
    • （情况3.1）兄弟节点是黑色，此时又需要讨论兄弟节点的子节点的颜色：
      • （情况3.1.1）兄弟节点的子节点至少有一个是红孩子，那么此时根据其兄弟节点的子节点（r），兄弟节点（s），兄弟节点的父节点（p）三者的关系，分成四种类型：LL（值得注意的是，如果兄弟节点有两个红色的子节点，那么也视为LL），LR，RR，RL。
        • LL 和 RR 类型处理时，让 r 颜色变为 s，s 颜色变为 p，p颜色变为黑色
        • LR 和 RL 类型处理时，只需要让 r 变 p，p 变黑
        • 更新完颜色之后再根据三者位置关系进行相应的旋转操作。最后双黑变单黑。
      • （情况3.1.2）兄弟节点的颜色都是黑色，那么兄弟节点变红色，让父节点变成双黑节点
        • 让父节点变成双黑节点时，如果父节点原来是红色节点或是根节点，那么就会直接变为黑色节点
        • 如果父节点原来是黑色节点，且不是根节点，那么父节点就变成了真的双黑节点。此时仍需要根据这里的各种情况，来把这个新的双黑节点处理掉
    • （情况3.2）兄弟节点是红色，此时父节点必然是黑色节点。先将兄弟节点变成黑色，父节点变成红色，然后再朝双黑节点所在的方向旋转。随后还需要根据这里讲的各种情况继续处理双黑节点。

3.4 B 树

3.4.1 性质

一颗 $m$ 阶 B 树可以为空树。

满足如下特性：

• 所有结点的平衡因子均为 $0$
• 树中每个结点最多有 $m$ 棵子树，最多有 $m-1$ 个关键字
• 如果根结点不是叶结点，那么根节点至少有 $2$ 棵子树，至少有 $1$ 个关键字
• 除根节点以外的所有非叶结点至少有 $\left\lceil \frac{m}{2} \right\rceil$ 棵子树，至少有 $\left\lceil \frac{m}{2} \right\rceil - 1$ 个关键字
• 所有的叶结点都出现在同一层次上，并且不带信息，仅是表示一种失败结点（这些结点实际上并不存在，指向这些结点的指针为空）（在大多数教材上，叶结点和这里的定义相同。但是很多 408 真题认为叶结点是 B 树的终端节点）
  • B 树叶节点对应查找失败的情况。对有 $n$ 个关键字的查找集合进行查找，失败可能性有 $n+1$ 种，因此叶节点有 $n+1$ 个。
• 结点中的关键字从左到右递增有序，关键字两侧均有指向子树的指针，相当于关键字把查询区间分成了多个部分

所有非叶结点的结构如下：

$n$ 为当前结点存储的关键字数量。$K_1\dots K_n$ 表示关键字，$P_0\dots P_n$ 表示指向子树的指针。

B 树的高度不包含最后一层的叶子结点（有些书中认为 B 树的高度叶包含最后一层）。对于一颗包含 $n$ 个关键字，高度为 $h$，阶数为 $m$ 的 B 树，当每个结点的关键字个数达到最多时，B 树的高度最小，关键字个数最少的时候，B 树高度最高，高度的范围满足：

$$\log_m(n+1) \le h \le log_{\left \lceil \frac{m}{2} \right \rceil}(\frac{n+1}{2}) + 1$$

B 树常存在磁盘上，每次走到一个结点，需要将其从磁盘读到内存中然后进行查找（顺序查找或者是折半查找）。因此读取磁盘的次数就是目标结点在 B 树上的层数。

3.4.2 插入

首先就像 B 树的查找算法那样，找到要插入的关键字需要插入的结点位置。关键字一定会是插入到最底层的非叶结点上。

每个非根结点的关键字个数范围为 $\left[\left\lceil \frac{m}{2} \right\rceil - 1, m - 1\right]$。如果插入结点后，关键字的个数小于 $m$，则可以直接插入。反之则需要将结点分裂：在 $\left\lceil \frac{m}{2} \right\rceil$ 这个位置将关键字分成两部分，左部分和右部分作为被分裂结点的父亲结点的子树，中间结点提升到被分裂结点的父亲结点上：

示例，将一组关键字 $\{20, 30, 50, 52, 60, 68, 70\}$ 依次插入一棵 $3$ 阶 B 树的过程：

3.4.3 删除

如果被删除的关键字不在终端结点中，那么就类似 BST 那样，找到被删除关键字的前驱或是后继，将其替换，然后删掉原来的前驱和后继。这样就可以统一转换为删除在终端结点中的关键字。

如果删除关键字后，其所在的终端结点剩余的关键字个数仍然是 $\ge \left\lceil \frac{m}{2} \right\rceil - 1$，那么可以直接删去。

否则，就需要讨论：

• 如果其左兄弟或是右兄弟的关键字数量 $\ge \left\lceil \frac{m}{2} \right\rceil$，说明可以从兄弟结点借一个关键字过来。可以通过父亲节点将关键字传递过来。
• 如果兄弟结点不够借的话，那么就需要将当前结点，当前结点的兄弟结点，当前结点和兄弟结点之间在父亲结点中间的关键字，这三者合并成一个子结点。
  • 有可能父节点的关键字被拿去合并之后，父节点的关键字数量又不对了。如果父节点是根节点，那么关键字数量降为 $0$ 之后可以直接把空的根节点删掉，将合并出来的新结点作为新的根节点。
  • 如果父节点不是根节点，那么这个父节点又要和他自己的兄弟结点之间进行调整或者合并。

3.5 B+ 树

大体上和 B 树差不多，但是有如下的区别：

• B+ 树每个结点的关键字数量和子树数量是相同的。对于非根的内部结点，关键字个数/子树个数的范围为 $\left[\left\lceil \frac{m}{2} \right\rceil, m\right]$
• B+ 树的叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中
• 所有的非叶结点仅起到索引作用，并不会存储非叶结点中关键字所对应的记录的存储地址，这使得在 B+ 树中每次查找都需要一直查到叶子结点
• 非叶结点的关键字为其指向的子树内的最大关键字
• 用一个指针指向关键字最小的叶子结点。所有的叶子结点之间又连成了一个链表，因此 B+ 树可以进行两种查找运算：在树上查找或是从最小关键字开始顺序查找。

4. 散列表

散列函数/哈希函数：一个把查找表中的关键字映射成该关键字对应的地址的函数。这里的“地址”可以是数组下标，索引或者是内存地址。

散列函数可能会把多个关键字映射到同一个地址，这种情况为冲突，发生冲突的关键字称为同义词。

散列表/哈希表：根据关键字直接进行访问的数据结构。

理想情况下，对散列表进行查找的时间复杂度为 $O(1)$。

4.1 散列函数

散列函数的定义域必须包含全部的关键字。

• 直接定址法：取关键字的某个线性函数值为散列地址。散列函数为 $H(key) = key$ 或是 $H(key) = a\times key + b$。
  • 适用于关键字分布基本连续的情况。
  • 优点：计算方法简单，没有冲突
  • 缺点：如果关键字分布不连续，空位较多，容易造成存储空间的浪费
• 除留余数法：假设散列表的表长为 $n$，取一个不大于 $n$ 且接近于 $n$ 的质数 $p$，散列函数为 $H(key) = key \space \% \space p$。
  • 最简单，最常用的方法
  • 关键是选择好 $p$
• 数字分析法：设关键字是 $r$ 进制数，而 $r$ 个数码在各位上出现的频率不一定相同。可能在某些位上数码的分布均匀一些，有些位上分布不均匀。此时选取数码分布均匀的若干位作为散列地址。
  • 适用于已经知道关键字集合
  • 如果更换了关键字则需要重新构造散列函数
• 平方取中法：取关键字的平方值的中间几位作为散列地址。这种方法得到的散列地址和关键字的每位都有关系，散列地址的分布较为均匀。
  • 适用于关键字每位取值都不够均匀，或者均小于散列地址所需位数

4.2 处理冲突

用 $H_i$ 表示处理冲突中第 $i$ 次探测得到的散列地址。初始时计算得到的散列地址为 $H_0$，如果发生冲突，则需要继续得到 $H_1$，若 $H_1$ 仍冲突则需要继续得到 $H_2$。

• 开放定址法：表中的空闲地址可以存储其同义词，也可以存储非同义词。$H_i = (H(key) + d_i) \space \% \space m$，其中 $d_i$ 为增量序列。

  使用开放定址法时，不能随便物理删除表中已有元素，否则会截断其他同义词元素的查找（因为会使得找到空地址误认为不存在）。删除元素需要打一个标记，做逻辑删除。

  开放定址法可能会出现堆积/聚集问题，即可能将第 $i$ 个散列地址的同义词存入 $i+1$ 个散列地址，这样本应该存入 $i+1$ 的元素存到了 $i+2$ 上......这样一直堆积下去。

  根据 $d_i$ 取法的不同，又分成如下种类：

  • 线性探测法/线性探测再散列法：$d_i = 1,2,\cdots, m - 1$。
    • 线性探测法容易产生堆积问题
  • 平方探测法/二次探测法：$d_i = 1^2,-1^2, 2^2, -2^2,\cdots, k^2, -k^2$，其中 $k\le \frac{m}{2}$，$m$ 为散列表长度，且 $m$ 必须是一个可以表示成 $4k+3$ 的素数。（虽说一些题目并没有满足这一条件）（先正后负）
    • 可以避免出现堆积问题
    • 不能探测到散列表上的所有单元，但至少能探测到一半单元
  • 双散列法：$d_i = i \times Hash_2(key)$，即需要使用两个散列函数，第一个散列函数发生冲突时，用第二个散列函数计算关键字地址的增量。
  • 伪随机序列法：$d_i=\text{伪随机数序列}$

发生聚集的原因是解决冲突的方法选择不当，并非是散列函数选择不当。

• 拉链法/链接法/链地址法：把所有同义词存储到一个线性表中。拉链法适用于经常进行插入和删除的情况。

  拉链法删除元素的时候可以直接物理删除。

4.3 散列查找

需要注意求查找失败的平均查找长度：

• ASL 的分子是哈希函数可能的取值，而并非散列表的表长

• 查找位置是删除标记时还要继续往后找

平均查找长度和三个东西直接相关：（1）装填因子，（2）散列函数，（3）处理冲突的方法。不直接依赖于表中已有表项的个数和表长。

装填因子：记为 $\alpha$，定义一个表的装满程度：

$$\alpha = \frac{\text{表中记录数 } n}{\text{散列表长度 } m}$$

5. 错题

• A：还需要数据的存储结构是顺序存储
• C：每个元素查找概率不相同的情况下，折半查找的ASL可能大于顺序查找

折半查找的算法不一定都是 $\left \lfloor\frac{l+r}{2}\right \rfloor$，也可以是 $\left \lceil\frac{l+r}{2}\right \rceil$。对于前者，左子树小于等于右子树（最多差1），对于后者，左子树大于等于右子树（最多差1）。

字符串之间的比较就是按字典序。

使用折半搜索的话 ASL 是固定的。

使用顺序查找可以将高概率元素前移来降低 ASL。

还可以使用二叉排序树，通过变化一下树形来降低 ASL。

对于Ⅱ、Ⅲ：

• B 树一个索引结点大小应该适应操作系统一次磁盘读写的单位大小
• B 树的非叶结点还需要存储节点内关键字对应记录的存储地址

• C：树可以顺序存储也可以链式存储
• D：使用链地址法解决冲突时，采用的是顺序存储与链式存储结合的方式

• Ⅱ：不一定相邻，因为可能是由于非同义词之间的冲突导致需要再进行探测

4）能当作散列函数且是一个好的散列函数