查找

查找，即在数据集合中寻找一个特定的元素。

用于查找的数据集合称为 查找表 ，它由同一类型的数据元素构成。

数据元素中用于唯一标识的属性称为 关键字 ，基于关键字的查找结果应该是唯一的。

对于一个查找表，如果仅用来查找元素，则称为 静态查找表 ；如果查找过程中同时插入或删除元素，称为 动态查找表 。

在查找运算中，需要比对关键字的次数称为 查找长度 。

所有查找过程中进行关键字比对的次数的平均值，称为 平均查找长度 ，公式为 $ASL = \sum_{i=1}^n P_i C_i$ ，其中：

• $P_i$ 为查找第 $i$ 个元素的概率；
• $C_i$ 为第 $i$ 个元素的查找长度。

可以用 查找判定树 辅助分析平均查找长度。

顺序查找

使用顺序表存储数据，从头到尾依次遍历，直到找到目标元素。

时间复杂度为 $O(n)$ ，平均查找长度为 $\frac{n+1}{2}$ 。

折半查找

又称为 二分查找 ，要求表内数据元素必须有序。

算法步骤如下：

0. 需要一个有序表 s 和两个指针 low 和 high ，分别指向表头和表尾。
1. 令 mid = (low + high) / 2 ，将 s[mid] 与目标元素比较：
   • 若相等，则查找成功；
   • 若 s[mid] > key ，令 high = mid - 1 ，重复步骤 1 ；
   • 若 s[mid] < key ，令 low = mid + 1 ，重复步骤 1 。

时间复杂度为 $O(\log_2 n)$ 。

查找判定树

折半查找的查找判定树构建方法如下：

1. 拎出表中中间（向下取整）的元素，作为根节点，也是分界点；
2. 根据分界点，将表分为两部分，分别构建左右子树，并递归步骤 1 和 2 ；
3. 在所有叶子节点上补上两个结点，表示查找失败所在的数值区间。

上述方法所构建的查找判定树的特性：

• 满足平衡二叉树和二叉排序树的定义；
• 对于每个结点，其右子树的结点数最多比左子树多 1 个；
• 树高为 $\lfloor \log_2 n \rfloor + 1$（不含失败结点）。
• 若有 $n$ 个元素，则会有 $n + 1$ 个失败结点。

分块查找

在一个顺序表中，分组存放数据。同时建立一个索引表，记录每一组的索引开始的位置以及最大关键字。

如果为动态查找表，则可以用链式存储。

算法步骤如下：

1. 在索引表中查找目标元素所在的组；
2. 在该组中顺序查找目标元素。

如长度为 $n$ 的顺序表被分为 $m$ 组，每组 $b$ 个，若使用顺序查找方式查找索引表，则：

1. 索引查找的平均查找长度为 $(m + 1) / 2$ ，块内查找的平均查找长度为 $(b + 1) / 2$ ；
2. 总平均查找长度为两者相加：$(m + b) / 2 + 1$ ；
3. 当 $m = \sqrt{n}$ 时，此时每块为 $\sqrt{n}$ 个元素，总的平均查找长度最小，为 $\sqrt{n} + 1$ 。

如果用折半查找索引表，则 $ASL = \lceil \log_2 {m + 1} \rceil + (b + 1) / 2$ 。

二叉排序树

又称 二叉查找树 Binary Search Tree ，简称 BST 。

二叉排序树是一棵具有如下性质的二叉树：

• 左子树上所有结点的关键字均小于根结点的关键字；
• 右子树上所有结点的关键字均大于根结点的关键字；
• 左右子树也分别为二叉排序树。

对二叉排序树进行中序遍历，得到的序列是递增的。

结点的删除

删除结点时，需要考虑三种情况：

1. 被删除结点为叶子结点，直接删除即可；
2. 被删除结点只有左子树或右子树，将其子树提升即可；
3. 被删除结点既有左子树又有右子树：
   1. 找到右子树中的最小结点，将其替换到被删除结点的位置；
   2. 递归删除原来的最小结点。

也可以找左子树中的最大结点进行替代删除。

平衡二叉树

又称 AVL 树 ，是一种特殊的二叉排序树。

平衡二叉树要求每个结点的左右子树的高度差的绝对值不超过 1 。

结点的平衡因子 = 左子树高度 - 右子树高度。

假设 $n_h$ 为高度为 $h$ 的平衡二叉树的最少结点数，有 $n_h = n_{h-1} + n_{h-2} + 1$ ，其中 $n_0 = 1$ ，$n_1 = 2$ 。

含有 $n$ 个结点的平衡二叉树的最大深度为 $O(\log_2 n)$ ，平均查找长度为 $O(\log_2 n)$ 。

左旋右旋

当二叉树不平衡时，可以通过左旋右旋的操作进行平衡，图示如下：

   [A]        [B]           [A]          [B]
   / \        / \           / \          / \
 [B] AR  -> BL  [A]        AL [B]  ->  [A] BR
 / \            / \           / \      / \
BL BR          BR AR         BL BR    AL BL

插入结点

插入结点 E 时，如果破坏了平衡二叉树的平衡性，则需要进行旋转操作：

• 从 E 出发，向上查找第一个平衡因子大于 1 的结点 A（最小不平衡子树）；
• 若 E 在 A 的左子树的左子树上，则进行右旋；
• 若 E 在 A 的右子树的右子树上，则进行左旋；
• 若 E 在 A 的左子树的右子树上，则先对左子树进行左旋，再对不平衡结点进行右旋；
• 若 E 在 A 的右子树的左子树上，则先对右子树进行右旋，再对不平衡结点进行左旋。

删除结点

1. 采用二叉排序树的删除方法删除结点 E 。
2. 从 E 开始，向上查找第一个平衡因子大于 1 的结点 A（最小不平衡子树）。
3. 与插入结点类似，对 A 进行旋转操作（观察 A 的较高的子树及其左右子树）。
4. 重复步骤 2 和 3 ，直到根结点。

红黑树

先前的笔记：红黑树（上） 、红黑树（中）。

在普通的平衡二叉树中，面对插入和删除操作，需要进行频繁的旋转操作，效率较低。而红黑树则是精简这一操作的一种二叉排序树。

定义及性质

红黑树是一种特殊的二叉排序树，具有如下性质：

1. 每个结点可以是红色或黑色；
2. 根结点是黑色的；
3. 叶子结点（空结点）是黑色的；
4. 红结点的两个子结点都是黑色的；
5. 从根结点出发，任一路径上的黑色结点数相同。

黑高：从结点 x 出发，到达一个叶子结点的任意一条路径上的黑色结点个数。

根据定义，红黑树有如下性质：

• 根据定义 4 和 5 ，红黑树的最长路径不会超过最短路径的两倍。
• 红黑树的高度不超过 $2 \log_2 (n + 1)$ 。

若红黑树高度 h ，则根结点黑高至少为 $\lfloor h / 2 \rfloor$ ，此时非空结点数至少为 $2^{\lfloor h / 2 \rfloor} - 1$ 。

插入结点

将插入结点 N 染为红色，然后进行下列分类讨论：

• 若 N 为根结点，则直接染为黑色；
• 若 N 的父结点 P 为黑色，则不需要进行调整；
• 若 N 的父结点 P 为红色，则：
  • 若 N 的叔结点 U 为红色，则将 P 和 U 染为黑色，将 N 的爷爷结点 G 染为红色，然后将 G 当作新插入的结点向上递归调整；
  • 若 N 的叔结点 U 为黑色，且 P 为 G 的左子树时，则：
    1. 若 N 为 P 的右子树，将 P 左旋，此时变为下面一个情况；
    2. 若 N 为 P 的左子树，将 P 染为黑色，G 染为红色，将 G 右旋。
  • 若 N 的叔结点 U 为黑色，且 P 为 G 的右子树时同理。

删除结点

删除操作比较复杂，知识点有如下：

• 删除结点的时间复杂度为 $O(\log_2 n)$ ；
• 处理方式与二叉排序树类似；
• 删除结点后，需要进行调整，包括变色、旋转等操作，使再次满足红黑树的性质。

B 树

B 树，又称 多路平衡查找树 。M 阶 B 树 代表每个结点最多有 M 个子树。

B 树可视为一般化的二叉查找树。比如一个 M 阶 B 树的结点定义如下：

struct BTreeNode {
    int num;    // 结点中关键字的个数
    int key[M - 1]; // 关键字数组
    BTreeNode *child[M];   // 子树指针数组
};

一般将失败结点作为叶子结点，而叶子结点的父结点称为终端结点。

为了保证查找效率，对于一个 M 阶 B 树，规定：

• 若根结点不是叶子结点，则至少有两棵子树；
• 任何非叶结点（除根结点）至少有 $\lceil M / 2\rceil$ 个子树，即 $\lceil M / 2 \rceil - 1$ 个关键字；
• 任何一个结点，其所有子树的高度都要相同。

含 n 个关键字的 M 阶 B 树的最小高度为 $\log_M n$ ，最大高度为 $log_{\lceil M / 2 \rceil} \frac{n + 1}{2} + 1$ 。

插入元素

对于一个 M 阶 B 树，每个结点（除根结点）的关键字个数应当在 $\lceil M / 2 \rceil - 1$ 和 $M - 1$ 之间。

插入元素的步骤如下：

1. 从根结点开始，找到插入位置（该位置应当在最底层）插入。
2. 若插入后结点的关键字数量超过 $M - 1$ ，则进行结点分裂操作：
   1. 将该结点的关键字分为两部分，中间的关键字上移。
   2. 将左右两部分分别作为两个新结点的关键字。
   3. 将中间的关键字插入到父结点中。
   4. 对父结点进行步骤 2 的递归操作，直到不需要分裂。

删除元素

对于一个 M 阶 B 树，删除元素的步骤如下：

• 若要删除元素的位置为非终端结点，则选取其前驱或后继结点替代删除；
• 若要删除元素的位置为终端结点：
  • 若结点的关键字数量大于 $\lceil M / 2 \rceil - 1$ ，则直接删除；
  • 若其兄弟结点的关键字数量大于 $\lceil M / 2 \rceil - 1$ ，则从兄弟结点借一个关键字作为父结点，再将原父结点的关键字下移至该结点；
  • 若其兄弟结点的关键字数量等于 $\lceil M / 2 \rceil - 1$ ，则将其与兄弟结点合并，再从父结点中删除一个关键字，并对父结点递归调整。

B+ 树

B+ 树是 B 树的一种变体。一棵 M 阶 B+ 树的定义如下：

1. 每个结点最多有 M 个关键字，每个关键字对应一个子树。
2. 非叶子结点的每个关键字代表其子树中的最大关键字。
3. 只有叶子结点存储元素，且每个叶子结点都有指向下一个叶子结点的指针。
4. 除根结点外，每个结点至少有 $\lceil M / 2 \rceil$ 棵子树。
5. 若根结点不是叶子结点，则至少有两棵子树。