欢迎各位道友来到$408$大题系列的第七章——查找。查找这一章的关键是“平均查找长度”和“数据结构怎么组织”：顺序表、有序表、树、散列表，各有各的查法，也各有各的代价。先把每种查找的适用场景，$\mathrm{ASL}$（$\text{Average Search Length}$，平均查找长度）和时间、空间复杂度等性质算清楚，再上大题。因为和二叉树一样，查找的各种性质也是小题们特别喜欢出的点，稍有不慎你就掉坑里了。

查找

查找的基本概念

查找本身的概念我就不用多说了，考试不会考这么弱智的东西。查找的结果一般分成两种：

查找成功：在数据集合中找到满足条件的数据元素。
查找失败：在数据集合中没有找到满足条件的数据元素。

查找表：用于查找的数据集合，就是你在什么地方找。对于一个查找表，除了查找元素之外，可能还涉及到插入和删除操作。

静态查找表：一个不需要动态修改的查找表，即不允许插入数据和删除数据。

关键字：数据元素中唯一标识该元素的某个数据项的值，即你要找的东西的标准。

平均查找长度：查找过程中，一次查找的长度就是指这次查找中关键字的比较次数；平均查找长度则是在所有查找过程中关键字比较次数的加权平均值：

$$ \mathrm{ASL}=\sum_{i=1}^{n}P_iC_i $$

其中，$n$是查找表的长度，$P_i$是查找第$i$个数据元素的概率（考试一般题设条件都是等概率查找，即$P_i=\frac{1}{n}$），$C_i$是找到第$i$个数据元素所需进行的比较次数。$\mathrm{ASL}$是衡量查找算法效率的核心指标，一般直接关联时间复杂度。

顺序查找

顺序查找（又称线性查找），适用于顺序表和链表：对于顺序表，可通过迭代器去遍历访问，对于链表，就是获取$next$指针了。

查找思想如下：

从线性表的一端开始，逐个查找元素的关键字是否满足给定条件。
如果查找到的某个元素的关键字满足条件，则查找成功，返回该元素在线性表中的位置。
如果都翻到表尾了还没找到符合条件的元素，那就是查找失败，按照要求返回一个失败的值（一般是$-1$或者其他负数）。

下面是它的算法实现（反正$408$没要求数组必须用静态的，我就用$vector$来写了）。

#include <vector>
using namespace std;

int SearchSeq(const vector<int>& arr, int target)
{
	for (int i = 0; i < arr.size(); ++i)
	{
		if (arr[i] == target)
		{
			return (i); // 返回找到的位置
		}
	}
	return -1; // 没找到目标元素，返回-1
}

对于含$n$个元素的表，若给定关键字和其中第$i$个元素相等，需要进行$n-i+1$次关键词比较，即$C_i=n-i+1$，查找的平均查找长度为：

$$ \mathrm{ASL}_{\text{成功}}=\sum_{i=1}^{n}P_i(n-i+1) $$

当每个元素查找的概率相等，即$P_i=\frac{1}{n}$，此时有

$$ \mathrm{ASL}_{\text{成功}}=\sum_{i=1}^{n}P_i(n-i+1)=\frac{n+1}{2} $$

查找不成功时，显然有

$$ \mathrm{ASL}_{\text{失败}}=n+1 $$

综上所述，顺序查找的缺点就是：当$n$比较大时，平均查找长度较大，效率较低。平均来说，时间复杂度是$O(n)$。优点是对存储结构不设要求，顺序存储也行，链式存储也行。但是链式存储的线性表进行查找只能用顺序查找。

此外，如果线性表有序的话，就不用查找到表的末尾就可以判定查找成功或失败了。具体实现思路也挺简单的，就是改一个判断条件。代码我就不写了（其实就是我想偷懒）。有序线性表做顺序查找时，查找成功时的平均查找长度和一般顺序查找相同；但查找失败时，一旦当前元素已经大于目标值就可以提前停下，所以失败时的平均查找长度会小一些。

折半查找

折半查找（也叫二分查找），基本思想如下：

将定值$key$和表中中间位置的元素进行比较，若相等，则查找成功，返回该元素的位置。
若不相等，则待查找元素只能位于表的前半部分或后半部分，随后在缩小的范围内重复上述过程，直到找出该元素或者查找失败为止。
折半查找只能在有序表中进行。

循环版代码如下（这里我们假设$vector$内元素已经排好序）：

#include <vector>
using namespace std;

int BinarySearch(const vector<int>& nums, int target)
{
	int low = 0, high = nums.size() - 1, mid = 0;		// 序列左边界，右边界，和中间位置
	while (low <= high)
	{
		mid = (low + high) / 2;	// 计算中间位置
		if (nums[mid] == target)
		{
			return mid;	// 找到目标值，返回索引
		}
		else if (nums[mid] < target)
		{
			low = mid + 1;	// 目标值在右半部分
		}
		else
		{
			high = mid - 1;	// 目标值在左半部分
		}
	}

	return -1;	// 查找失败
}

递归版代码如下：

#include <vector>
using namespace std;

int BinarySearch(const vector<int>& nums, int low, int high, int target)
{
	if (low > high)
	{
		return -1;	// 查找失败
	}

	int mid = (low + high) / 2;	// 确定中间位置
	if (target == nums[mid])
	{
		return mid;		// 找到目标值，返回索引
	}
	else if (target < nums[mid])
	{
		return BinarySearch(nums, low, mid - 1, target);	// 在左半部分继续查找
	}
	else
	{
		return BinarySearch(nums, mid + 1, high, target);	// 在右半部分继续查找
	}
}

然后关于每次划分中间位置取整的问题，按道理来说是要么都向上取整，要么都向下取整。但大家放心，我们的$C++$様在你写代码的时候，就在你定义的$int$类型里把底层的类型转换规则统一写好了，所以这就不是我们该操心的事儿了，$C++$様に栄光あれ！（赞美$C++$大人！）

折半查找的过程可以用一个二叉判定树描述。树中圆形节点表示表中存在的记录，节点值就是关键字；方形节点是叶子，表示查找失败的区间。红色加粗路径表示本次查找的比较过程。

以有序表$7,10,13,16,19,29,32,33,37,41,43$为例，这棵判定树按$mid = \lfloor (low + high) / 2 \rfloor$构造，根节点是$29$，左子树对应有序表的前半段，右子树对应后半段。下面两张图是同一棵二叉搜索树，分别标出查找$11$和$32$的路径。

图$1$：查找$11$的判定树

路径：$29 \to 13 \to 7 \to 10$，$10$的右孩子为空，查找失败；共比较$4$次。

图$2$：查找$32$的判定树

路径：$29 \to 37 \to 32$，查找成功；共比较$3$次。

查找成功时的查找长度就是从根节点到目的节点的路径上节点数；查找失败的查找长度是从根节点到对应失败阶段的父节点的路径上的节点数。

显然，若有序表有$n$个元素，则对应的判定树有$n$个圆形节点和$n + 1$个方形叶节点，显然，该判定树一定是平衡二叉树。

在等概率查找下，查找成功的平均查找长度为：

$$ \mathrm{ASL}_{\text{成功}} = \frac{1}{n}\sum_{i = 1}^{n}l_i = \frac{1}{n}(1 \times 1 + 2 \times 2 + \cdots + h \times 2^{h - 1}) = \frac{n + 1}{n}\log_2(n + 1) - 1 \approx \log_2(n + 1) - 1. $$

其中$h$是树的高度，$l_i$是第$i$个成功结点所在的层数。

查找失败时，比较次数就是从根节点走到对应失败区间父节点的路径上的结点数。设第$j$个失败区间对应的方形叶结点在第$h_j$层（根为第$1$层），如果只数关键字比较、不把最后判空算进去，那么这次失败的比较次数是$h_j - 1$。因此

$$ \mathrm{ASL}_{\text{失败}} = \frac{1}{n + 1}\sum_{j = 1}^{n + 1}(h_j - 1). $$

如果教材把最后和空指针比较也算一次，就把$h_j - 1$换成$h_j$。

当$n = 2^h - 1$，也就是判定树是满二叉树时，所有失败结点都在第$h + 1$层，所以

$$ \mathrm{ASL}_{\text{失败}} = h = \log_2(n + 1). $$

一般$n$的精确式子可以写成：令

$$ h = \lfloor\log_2 n\rfloor + 1,\qquad k = n - (2^{h - 1} - 1), $$

其中$k$是最后一层的成功结点数，则

$$ \mathrm{ASL}_{\text{失败}} = \frac{(h - 1)(2^{h - 1} - k) + h \cdot 2k}{n + 1}. $$

例如$n = 11$时，$h = 4$，$k = 4$。失败结点有$4$个在第$4$层、$8$个在第$5$层，比较次数分别是$3$和$4$，所以

$$ \mathrm{ASL}_{\text{失败}} = \frac{4 \times 3 + 8 \times 4}{12} = \frac{44}{12} = \frac{11}{3} \approx 3.67. $$

当元素个数是$n$时，判定树高度

$$ h = \lceil\log_2(n + 1)\rceil = \lfloor\log_2 n\rfloor + 1. $$

因此，折半查找有：

$$ \text{最坏情况下比较次数} = \text{最多比较次数} = \text{判定树高度} = \lceil\log_2(n + 1)\rceil. $$

注意，有些资料写成$\lceil\log_2 n\rceil$，那只在$n = 2^k - 1$这种满二叉树情形下成立；一般$n$要用$\lceil\log_2(n + 1)\rceil$，否则会少算一次。比如$n = 4$时最多比较$3$次，而$\lceil\log_2 4\rceil = 2$。所以折半查找的时间复杂度是$O(\log_2 n)$。

分块查找

分块查找（也称索引查找），基本思想如下：将查找表分成若干块，块内元素可以无序，但块间必须有序，即任意前一块的最大关键字小于后一块的最小关键字（或者反过来）。同时，建立一个索引表，其中每个元素包含对应块的最大关键字和该块的起始地址，且索引表按最大关键字有序排列。

具体过程分成两步：

在索引表中确定待查记录所在块（可采用顺序查找或折半查找来实现）。
在目标块内进行顺序查找。

例如，关键码集合为$\lbrace 88,24,72,61,21,6,32,11,8,31,22,83,78,54 \rbrace$，可按关键码值$24,54,78,88$划分成$4$个块，并建立相应的索引表。

为体现“块内可以无序”，块内关键字保持原序列中的相对顺序；查找表按块连续存放，每个块对应一段连续下标。对应的索引表和查找表如下（下标从$1$开始）。

索引表

块号	最大关键字	起始地址
$1$	$24$	$1$
$2$	$54$	$7$
$3$	$78$	$10$
$4$	$88$	$13$

查找表

下标	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$
关键字	$24$	$21$	$6$	$11$	$8$	$22$	$32$	$31$	$54$	$72$	$61$	$78$	$88$	$83$
所属块	$1$	$1$	$1$	$1$	$1$	$1$	$2$	$2$	$2$	$3$	$3$	$3$	$4$	$4$

从表中可以看出，索引表按最大关键字递增；第$i$块的最大关键字小于第$i+1$块的最小关键字。查找时先用索引表定位块，再在块内顺序查找。

例如查找$32$：由$24 < 32 \le 54$定位到第$2$块，起始地址为$7$，再在块内顺序查找。

分块查找的平均查找长度等于索引查找的平均查找长度加上块内查找的平均查找长度。设索引查找和块内查找的平均查找长度分别是$L_I$和$L_S$，则分块查找的平均查找长度是

$$ \mathrm{ASL} = L_I + L_S $$

如果将长度为$n$的查找表均匀地分成$b$块，每块包含$s$个记录，即$n=bs$，并假设扫描索引表和扫描查找块都用顺序查找，且查找每一个元素的概率均等。则平均查找长度为：

$$ \mathrm{ASL} = L_I + L_S \\ = \frac{b + 1}{2} + \frac{s + 1}{2} \\ = \frac{s^2 + 2s + n}{2s} $$

所以，当块大小$s$取最优值$\sqrt{n}$时，平均查找长度最小，为$\sqrt{n}+1$。

树形查找

二叉排序树（$BST$）

二叉排序树（也叫二叉搜索树），要么是一棵空树，要么是一棵具有以下性质的二叉树：

若左子树非空，则左子树上所有节点的关键字均小于根节点的关键字。
若右子树非空，则右子树上所有节点的关键字均大于根节点的关键字。
左右子树也分别是二叉排序树。

所以，对二叉排序树进行中序遍历可以得到一个递增序列。

二叉排序树的查找

二叉搜索树的查找，就是从根节点开始，逐层向下比较并选择左/右子树的过程。若二叉排序树非空，就先将给定关键字和根节点的关键字比较；若相等，则查找成功；若不等，且给定关键字小于根节点的关键字，就在根节点的左子树上查找；否则在根节点的右子树上查找。这一过程天然适配递归。

鉴于所有递归代码都能转化成循环结构，所以我们还是老规矩：一个递归版本，一个循环版本。

递归代码如下：

int BSTSearch(BiTree T, int key)
{
	if (T == nullptr)
	{
		return -1;                  // 没找到key，返回-1表示key不存在
	}
	if (key == T->data)
	{
		return T->data;             // 找到
	}
	else if (key < T->data)
	{
		return BSTSearch(T->lchild, key);
	}
	else
	{
		return BSTSearch(T->rchild, key);
	}
}

循环代码如下：

int BSTSearch(BiTree T, int key)
{
	while (T != nullptr && key != T->data)
	{
		if (key < T->data)
		{
			T = T->lchild;
		}
		else
		{
			T = T->rchild;
		}
	}
	if (T == nullptr)
	{
		return -1;		// 未找到关键字，返回-1
	}
	if (key == T->data)
	{
		return T->data;	// 找到关键字，返回关键字
	}
}

二叉排序树的插入

二叉排序树是一种动态查找表，会随着插入和删除操作而变化。

小玄：你这不是说了句废话吗？

哎行吧行吧，我重新说一遍，就是随着查找的进行，二叉排序树基于被查找的序列而构建：当查找失败，即树中不存在关键字等于给定值的节点时，才执行插入操作。

插入过程如下：若原二叉排序树为空，则将新节点作为根节点直接插入；否则从根节点开始比较，若关键字$k$小于当前节点的关键字，则在左子树中继续查找并插入；若$k$大于当前节点的关键字，则在右子树中继续查找并插入。插入完成后，新插入的节点一定是叶节点。

因此，我们可以把上面的二叉排序树查找代码改动几下，让它变成二叉排序树的插入代码：

递归代码如下：

int BSTInsert(BiTree& T, int key)
{
	if (T == nullptr)
	{
		T = new BiTNode;
		T->data = key;
		T->lchild = nullptr;
		T->rchild = nullptr;
		return 1;                   // 插入成功
	}

	if (key == T->data)
	{
		return 0;                   // 已存在，不插入
	}
	else if (key < T->data)
	{
		return BSTInsert(T->lchild, key);
	}
	else
	{
		return BSTInsert(T->rchild, key);
	}
}

循环代码如下：

int BSTInsert(BiTree* T, int key)
{
	if (*T == nullptr)                  // 空树，新结点作为根
	{
		*T = new BiTNode;
		(*T)->data = key;
		(*T)->lchild = (*T)->rchild = nullptr;
		return 1;
	}

	BiTNode* p = *T;
	while (true)
	{
		if (key == p->data)
		{
			return 0;                   // 已存在
		}
		else if (key < p->data)
		{
			if (p->lchild == nullptr)   // 左槽位为空，直接挂上
			{
				p->lchild = new BiTNode;
				p->lchild->data = key;
				p->lchild->lchild = p->lchild->rchild = nullptr;
				return 1;
			}
			p = p->lchild;
		}
		else
		{
			if (p->rchild == nullptr)   // 右槽位为空，直接挂上
			{
				p->rchild = new BiTNode;
				p->rchild->data = key;
				p->rchild->lchild = p->rchild->rchild = nullptr;
				return 1;
			}
			p = p->rchild;
		}
	}
}

大家都能看出来，循环代码比递归代码要长许多，也麻烦许多。所以考试的时候一般都是用递归来写插入。

剩下的就是从零开始构造一棵二叉排序树了，规则前面已经讲过；写代码时就是遍历一个线性表，每遍历一个元素就调用一次二叉搜索树插入算法。

二叉排序树的删除

删除树的节点什么的最麻烦了啊啊啊啊啊啊。・ﾟ(ﾉД`)ﾟ・。

什么？你问我哪里麻烦了？下面是二叉排序树删除节点的思路：

若被删节点$z$是叶节点，直接删除即可。
若节点$z$只有一棵非空子树（左子树或右子树），则将其唯一的子树上移，作为$z$的父节点的新子树，替代$z$的位置。
若节点$z$有两棵子树，则可用$z$的直接后继或直接前驱（分别是中序遍历的下一个或上一个节点）来替代$z$；替换完成后，再从树中删除该直接后继或直接前驱。因为$z$的直接后继或直接前驱肯定最多只有一个子树（这是中序序列的性质），这样就转化成了第$1$种或第$2$种情况。

二叉排序树的查找效率

在二叉搜索树中查找，效率主要取决于树的高度。因为查找过程是沿着根节点到叶节点的一条路径走的，最长也就是树高。在左右子树高度之差不超过$1$，也就是平衡二叉树的条件下，平均查找长度为$O(\log_2 n)$。最坏情况下，构造二叉搜索树的序列一开始就是有序的，此时得到的二叉搜索树会退化成一条链，平均查找长度退化为$\frac{n+1}{2}$。

二分查找和二叉排序树

从查找过程来看，这俩其实很像，就平均时间复杂度而言，他俩也大差不差。但是考试最恶心的地方就在于总有那么几道简答题问你概念什么的又这又那的，所以它们的区别也有考的概率。如下：

二分查找所对应的判定树是唯一的，而通过相同关键字集合可能生成不同的二叉排序树，取决于关键字的插入顺序。
二叉排序树无需移动节点，只需要修改指针就能完成插入和删除操作，平均时间复杂度是$O(\log_2 n)$；而二分查找的对象是有序顺序表，插入或删除元素时会移动大量元素，时间复杂度是$O(n)$。

平衡二叉树（$AVL$树）

所谓平衡二叉树，就是任意节点的左右子树的高度之差的绝对值不超过$1$，这种树也叫$AVL$树。

定义$AVL$树中节点的平衡因子为该节点左右子树的高度差。既然要平衡，平衡因子的值只能取$\lbrace -1,0,1 \rbrace$。

平衡二叉树的插入操作

平衡二叉树维持平衡的基本思想如下：每次插入一个节点后，沿着查找路径向上检查各祖先节点是否因该操作失衡；若存在失衡节点，则定位到离插入节点最近的失衡节点，以该节点为根的子树就是最小不平衡子树。随后，在保持二叉排序树性质的前提下，通过旋转调整其结构，使其重新达到平衡。

调整的规律有以下四种：

$LL$平衡旋转（右单旋转）：由于节点$A$的左孩子$L$的左子树上插入了新节点，导致$A$的平衡因子由$1$变成$2$，从而失衡。此时做一次向右旋转：把$A$的左孩子$B$向右上旋转到$A$原来的位置上，将其拔高成根节点；将$A$向右下方旋转，成为$B$的新右孩子，而$B$原来的右孩子变成$A$的左孩子。
$RR$平衡旋转（左单旋转）：由于节点$A$的右孩子$R$的右子树上插入了新节点，导致$A$的平衡因子由$-1$变成$-2$，从而失衡。此时做一次向左旋转：把$A$的右孩子$B$向左上旋转到$A$原来的位置上，将其拔高成根节点；将$A$向左下方旋转，成为$B$的新左孩子，而$B$原来的左孩子变成$A$的右孩子。
$LR$平衡旋转（先左后右双旋转）：由于节点$A$的左孩子$L$的右子树上插入了新节点，导致$A$的平衡因子由$1$变成$2$，从而失衡。此时做两次旋转操作，先左旋再右旋：把$A$的左孩子$B$的右孩子$C$向左上旋转到$B$原来的位置上，再把$C$向右上旋转到$A$原来的位置上。这两步左旋和右旋的操作与左单旋转和右单旋转相同。
$RL$平衡旋转（先右后左双旋转）：由于节点$A$的右孩子$R$的左子树上插入了新节点，导致$A$的平衡因子由$-1$变成$-2$，从而失衡。此时做两次旋转操作，先右旋再左旋：把$A$的右孩子$B$的左孩子$C$向右上旋转到$B$原来的位置上，再把$C$向左上旋转到$A$原来的位置上。这两步右旋和左旋的操作与右单旋转和左单旋转相同。

平衡二叉树的删除操作

以删除节点$w$为例，删除步骤如下：

使用二叉排序树的方法删除节点$w$。
若导致不平衡，则从$w$开始向上回溯，找到第一个不平衡的节点$z$。设$y$是$z$的左右子树中较高的那棵子树的根节点，$x$是$y$的左右子树中较高的那棵子树的根节点。
对以$z$为根的子树进行平衡调整。其中$x$、$y$、$z$的相对位置有以下四种情况：
1. $y$是$z$的左孩子，$x$是$y$的左孩子，此时采用$LL$右单旋转。
2. $y$是$z$的左孩子，$x$是$y$的右孩子，此时采用$LR$先左后右双旋转。
3. $y$是$z$的右孩子，$x$是$y$的右孩子，此时采用$RR$左单旋转。
4. $y$是$z$的右孩子，$x$是$y$的左孩子，此时采用$RL$先右后左双旋转。

这些调整过程与插入操作相同，只不过插入时只需要对以$z$为根的子树进行一次平衡调整（因为调整完成后，对应位置节点的平衡因子不变）；而删除操作可能需要多次调整，若一次调整导致子树高度减$1$，则可能还需对$z$的祖先节点进行平衡调整（因为以失衡节点为根的子树在调整后可能变矮，导致祖先节点失衡），这种影响最后可能波及到根节点。

平衡二叉树的查找

在平衡二叉树上查找的过程与普通二叉排序树相同，因此关键字比较次数最多等于树的高度。由于平衡二叉树的高度为$O(\log_2 n)$，所以查找的时间复杂度为$O(\log_2 n)$。

红黑树

首先，贫道先给大家说一下为什么前人要搞出来红黑树这个东西：众所周知，$AVL$树对节点的平衡要求很高，所以在插入和删除节点之后，需要非常频繁地调整整棵树的拓扑结构，代价比较大。因此，红黑树在$AVL$树的平衡基础上，放宽了对左右子树高度差的严格要求，转而使用节点颜色来控制树高。

红黑树的性质如下：

每个节点是红色或黑色的。
根节点必须是黑色的。
叶节点，即虚构的外部节点、$NULL$节点，都是黑色的。
不存在两个相邻的红节点，即红节点的父节点和子节点肯定都是黑色的（好家伙，介不似嘛隔代遗传嘛）。
对每个节点，从该节点到任意一个叶节点的简单路径上，所含黑节点的数量相同。

为了便于理解红黑树，一般在原树的基础上引入$n+1$个外部叶节点，这些叶节点都是黑色的（即第$3$条性质），以保证每个内部节点的左右子树均非空。

从某个节点出发到任意一个叶节点的简单路径上（不含该节点本身），黑节点的总数称为该节点的黑高，记为$bh$；根节点的黑高称为红黑树的黑高。

对于红黑树，有以下结论：

从根到叶节点的最长路径不大于最短路径的两倍。
有$n$个内部节点的红黑树高度$h \leq 2\log_2(n+1)$，即在红黑树里查找，最长用时是在$AVL$树中查找的两倍，时间复杂度还是$O(\log_2 n)$。
新插入的节点初始应是红色，因为如果是黑色的话，插入必然会导致这条路径上的黑节点数量变化。

综上所述，红黑树采取“适度平衡”策略，允许从根到叶的最长路径达到最短路径的$2$倍，这就显著降低了插入、删除时结构调整的频率。因此，对于动态查找表，若查找操作远多于插入、删除，采用$AVL$树更佳（查找更快）；若插入、删除频繁，采用红黑树更合适（调整开销更小）。（$C++$的$map$和$set$，$Java$的$TreeMap$和$TreeSet$就是基于红黑树实现的）

红黑树的插入

插入过程和普通二叉排序树基本类似，不同之处在于：插入新节点之后可能会破坏红黑树的性质，因此需要对节点进行重新着色和旋转调整。

因为新插入的节点必须是红节点，所以可能会产生父子节点都是红节点的情况。此时需要进行局部调整。设新插入的节点为$z$，完整过程如下：

用二叉排序树的规则插入$z$，并把$z$染成红色。
若$z$是根节点，直接把$z$染黑，结束。
若$z$的父节点$z.p$是黑色，红黑性质没有被破坏，结束。
若$z$的父节点$z.p$是红色，则违反性质$4$。由性质$2$和性质$4$可知，$z$的爷节点$z.p.p$一定存在且为黑色。此时看叔节点$y$，也就是$z.p$的兄弟节点的颜色。下面先假设$z.p$是$z.p.p$的左孩子：
1. 情形$1$：叔节点$y$是黑色，且$z$是$z.p$的右孩子（$LR$型，先左旋再右旋）。 先对$z.p$左旋，让$z$上升取代$z.p$的位置，转化为情形$2$。此时原来的$z$成了新的$z.p$，原来的$z.p$成了新的$z$。
2. 情形$2$：叔节点$y$是黑色，且$z$是$z.p$的左孩子（$LL$型，右单旋）。 对$z.p.p$右旋，并把$z.p$染黑、$z.p.p$染红。
3. 情形$3$：叔节点$y$是红色。 不论$z$是左孩子还是右孩子，都把$z.p$和$y$染黑，把$z.p.p$染红。此时$z.p.p$可能和它的父节点形成红红相连，于是把$z.p.p$当作新的$z$，继续向上回溯。
若$z.p$是$z.p.p$的右孩子，上述$LL$、$LR$分别对应$RR$、$RL$，左右操作完全对称。
调整到以下任一情况即可停止：$z$成为根节点（染黑）；$z.p$是黑色；或者进入情形$1$、情形$2$并完成旋转。

红黑树的删除

（这节难度较大，也比较抽象；$408$里真考到红黑树删除的概率不高，但它是理解性质$4$、性质$5$的最好例子。）

红黑树的删除比插入更绕，最容易把人绕晕的地方是：“想删的节点”和“真正被摘掉的节点”不一定是同一个。

如果待删节点$z$有两个非空孩子，标准做法和前面二叉排序树的删除一样：先用它的中序直接前驱或中序直接后继替代$z$，再转为删除那个前驱或后继。教材通常拿中序直接后继举例，下面也以后继为例，把选中的后继记作$y$；如果改用前驱，左右对称，结论完全一样。

中序直接前驱：$z$左子树中的最大节点。它没有右孩子（否则右孩子更大，它就不是最大节点），至多只有一个左孩子。
中序直接后继：$z$右子树中的最小节点。它没有左孩子（否则左孩子更小，它就不是最小节点），至多只有一个右孩子。

这两个节点的关键字都紧挨着$z$：前驱是小于$z$的最大关键字，后继是大于$z$的最小关键字。用它们替代$z$，仍然满足“左子树$<$根$<$右子树”的二叉排序树性质，所以两种选法都对。具体选前驱还是后继，最终得到的树形可能不同，但都满足红黑树性质；实际实现时固定选一种即可。

“替代”到底是怎么替代？

教材里一句“用后继替代$z$”，说得云里雾里的。其实，这里的“替代”是让$y$的关键字占据$z$的位置，原来的$z$关键字从树中消失。$z$原来的左右子树不会跟着$z$走，而是留在原位，由占据这个位置的$y$接管；$y$原来的位置则由它的右孩子$x$（可能是$NIL$）顶替。$z$不会去接管$y$的孩子，也不会移动到别处；从关键字的角度看，原来的$z$已经被$y$取代了。

实现上有两种等价写法：

拷贝关键字：$z$节点不动，左右子树也不动；把$y$的关键字和数据复制到$z$里，然后删除$y$原来的节点。删除$y$时，用$y$的右孩子$x$顶替它。
节点移植：把$y$从原位置摘下来，放到$z$的位置，让$y$继承$z$的颜色，并接手$z$原来的左右子树；$y$原来的位置用$x$顶替；旧$z$节点丢弃。

如果按“节点移植”来理解，删除过程可以记成下面几步：

找到$z$的中序直接后继$y$。
记住$y$原来的颜色，后面判断要不要双黑修复。
把$y$从旧位置摘下来，用它的右孩子$x$（可能是$NIL$）补位。
把$y$放到$z$的位置，让$y$接手$z$的左右子树，继承$z$的颜色，旧$z$丢弃。
如果$y$原来是黑色，就从$x$开始双黑修复；如果$y$是红色，直接结束。

注意，第$3$步是把$y$从旧位置“摘下来”，不是把$y$节点销毁；节点移植时这个$y$还要继续放到$z$的位置。如果按“拷贝关键字”来理解，就没有“移动$y$节点”这一步：先把$y$的关键字复制到$z$里，再删除$y$原来的节点并用$x$补位；后面的修复规则完全一样。

两种写法得到的抽象树是一样的：$z$的位置保留$z$原来的颜色，真正被摘掉的是$y$原来的位置。若$y$原来是黑色，后续修复从$x$开始；若$y$是红色，则不需要修复。

例如，删除$z=50$，$y=60$是后继：

用$y$替换$z$后：

        60(y)
       /     \
     30       70
             /  \
           65    80

$30$仍然留在左边，$70$及其子树仍然留在右边；$y$原来在$70$的左边，现在由$x=65$顶替；原来的$z$从树中消失。

那为什么还要用$x$替换$y$？

因为$x$替换的是$y$原来的位置，不是$z$的位置。$y$被搬到$z$的位置后，它原来的父节点仍然需要有一个孩子；$y$是后继，没有左孩子，只有右孩子$x$（也可能没有右孩子，此时$x=NIL$），所以只能用$x$补上$y$原来的位置。否则$y$的旧父节点还指着已经搬走的$y$，树就断了。

用局部结构看最清楚：

$y$离开后：

      p
      |
      x

如果$x$是$NIL$，那就是：

      p
      |
     NIL

注意，$x$不一定是“黑色的$NIL$”：如果$y$有右孩子，$x$就是那个右孩子，通常是红色；只有$y$没有右孩子时，$x$才是$NIL$。拷贝关键字的写法也一样，虽然$y$的关键字被复制走了，但$y$原来的节点仍然要从旧位置删掉，所以还是得用$x$补位。

这一步是结构上的接替，不是颜色上的修复。如果$y$原来是黑色，$y$离开旧位置会让经过那里的路径少一个黑节点；把$x$接上去并没有补回这个黑节点。若$x$是红色，把$x$染黑正好补上；若$x$是$NIL$，它本来就是黑的，再涂黑也没用，才需要记“双黑节点”，通过旋转和变色向兄弟借黑。

如果$y$本来就是$z$的右孩子，移植时要注意不要写成$y.right = z.right$，因为此时$z.right$就是$y$自己。直接让$y$接手$z$的左子树，并保留$y$原来的右孩子$x$即可。

这样一来，删除操作就可以按“真正被摘掉的节点$y$有几个孩子”来分：

$y$有两个孩子：这种情况不会出现。无论选前驱还是后继，它都至多只有一个非空孩子。
$y$至多有一个孩子：用$y$的孩子$x$（可能是外部叶节点$NIL$，也就是前面说的$NULL$节点）顶替$y$的位置。接下来只看$y$原来的颜色和$x$的颜色。

于是有下面几种情况：

$y$是红色：直接删掉，黑高不变，结束。
$y$是黑色，$x$是红色：把$x$染黑，顶替上去，黑高恢复，结束。
$y$是黑色，$x$是$NIL$：这就是最难的黑叶子删除，需要“双黑”修复。

问题$1$：只有一个孩子时，被删节点为什么一定是黑色的？

这里说的“只有一个孩子”，是指只有一个非空孩子，另一个孩子是$NIL$。设真正被删的节点为$Y$，它唯一的非空孩子为$C$，另一个孩子为$NIL$。

先假设$Y$是红色。由性质$4$，红节点的孩子必须是黑色，所以$C$必须是黑色。看从$Y$出发到叶子的两条路径：

经过$C$的路径：$Y$（红）$\to C$（黑）$\to \cdots \to NIL$（黑），$Y$下面至少有$C$和$NIL$两个黑节点。
不经过$C$的路径：$Y$（红）$\to NIL$（黑），$Y$下面只有$NIL$一个黑节点。

两条路径的黑节点数量不相等，违反性质$5$。所以$Y$不可能是红色，只能是黑色。

问题$2$：为什么这个孩子$C$一定是红色的？

既然$Y$是黑色，假设$C$也是黑色。看两条路径：

经过$C$的路径：$Y$（黑）$\to C$（黑）$\to \cdots \to NIL$（黑），$Y$下面至少有$C$和$NIL$两个黑节点。
不经过$C$的路径：$Y$（黑）$\to NIL$（黑），$Y$下面只有$NIL$一个黑节点。

黑节点数量仍然不相等，违反性质$5$。所以$C$必须是红色。

而且$C$下面不能再有非空孩子：因为$C$是红色，由性质$4$，它的孩子必须都是黑色；如果$C$有一个非空孩子$D$，那么经过$D$的路径上会多出至少一个黑节点，和不经过$C$的那条路径又不相等。因此$C$只能是一个红色叶节点，它的两个孩子都是$NIL$。这也说明：真正被删的黑色节点，其顶替节点$x$只可能是红色孩子或$NIL$，不会是黑色非空节点。

这时删除$Y$就很简单：用$C$顶替$Y$，再把$C$染黑。从$Y$的父节点往下看，删除前这条路径贡献$1$个黑节点（$Y$），删除后贡献$1$个黑节点（染黑后的$C$）。两边一抵，黑高不变。所以这种情况根本不需要旋转。

问题$3$：黑叶子删掉后，为什么不能直接补一个黑色$NIL$？

这是红黑树删除最反直觉的地方。答案是不行，因为问题不是“这里缺了一个节点”，而是“这条路径少了一个黑节点”。

假设删掉一个黑色叶子$Y$，并用一个黑色$NIL$顶替它。删除前，经过$Y$的路径上有$Y$（黑）和底下的$NIL$（黑）两个黑节点；删除后，这个位置只剩顶替上来的$NIL$（黑）一个黑节点。而兄弟那边的路径黑节点数量没有变，仍然和原来一样。于是经过这个位置的路径比兄弟路径少了一个黑节点，性质$5$被破坏。

这时你会遇到一个尴尬的局面：

把顶替的$NIL$再涂黑？它本来就是黑的，涂了等于没涂，还是少一个黑。
把它涂红？首先违反“$NIL$必须是黑色”的规则，其次红色不贡献黑高，还是少一个黑。

黑色节点的总数不会凭空多出来，所以只能向兄弟分支“借”。教材里说的双黑节点，并不是真的存在第三种颜色，而是一个临时记账标记：表示“这个位置本来应该有一个黑节点，现在被删掉了，先记一笔欠账，后面通过旋转和变色从兄弟那里补回来”。

双黑修复的四种情形

设顶替上来的节点为$x$（它可能是$NIL$），$x$的兄弟为$w$，父节点为$p$。算法里把$NIL$也当作一个节点来看待，它有自己的父节点和兄弟，只是不存关键字。此时$x$的兄弟$w$一定存在，否则$p$的两条路径黑高不可能相等。下面以$x$是$p$的左孩子为例，$x$是右孩子时左右对称。

进入修复循环后，先看$x$：如果$x$是红色，直接把$x$染黑，双黑消除；如果$x$是根节点，直接去掉双黑标记；否则按下面四种情形处理。

情形$1$：$w$是红色。 由性质$4$，$p$必为黑色，$w$的两个孩子必为黑色。把$w$染黑、$p$染红，然后对$p$左旋。这样$x$的新兄弟变成了$w$的某个黑色孩子。注意：这一步并没有恢复黑高，它只是把“红兄弟”转换成“黑兄弟”，好让后面的情形$2$、$3$、$4$能够继续处理。
情形$2$：$w$是黑色，且$w$的两个孩子都是黑色。 把$w$染红。这样兄弟那边的黑高也减$1$，和$x$这边的欠账暂时对齐；然后把双黑标记上移到$p$，令$x = p$，继续向上处理。如果上移后$x$是红色，直接把$x$染黑即可；如果$x$是根节点，直接去掉双黑标记。
情形$3$：$w$是黑色，$w$的远孩子是黑色，近孩子是红色。 这里“近孩子”指靠近$x$的那一侧孩子，“远孩子”指远离$x$的那一侧孩子。把$w$染红、近孩子染黑，然后对$w$做一次旋转，把近孩子转到$w$原来的位置。若$x$是左孩子，就对$w$右旋；若$x$是右孩子，就对$w$左旋。这样$w$的远孩子就变成了红色，转化为情形$4$。
情形$4$：$w$是黑色，$w$的远孩子是红色。 把$w$染成$p$原来的颜色，把$p$染黑，把$w$的远孩子染黑，然后对$p$做一次旋转：若$x$是左孩子就对$p$左旋，若$x$是右孩子就对$p$右旋。这样欠的那个黑节点就从兄弟分支借过来了，双黑标记消除，修复结束。

实际判断时，先看兄弟$w$的颜色：$w$红就是情形$1$；$w$黑时再看两个侄子，远侄红直接进入情形$4$，远侄黑、近侄红是情形$3$，两个都黑是情形$2$。

这里要特别区分两个容易混淆的操作：情形$1$是把红兄弟染黑，目的是换成黑兄弟；情形$2$才是把黑兄弟染红，目的是让兄弟那边也少一个黑，把欠账上移。不要把两者混在一起。情形$3$也只是把“远孩子黑、近孩子红”转换成情形$4$，本身并不直接消除双黑。

四种情形的例子

下面所有图都假设$x$是$p$的左孩子，$x$是右孩子时完全镜像。记$w$靠近$x$的孩子为近侄$a$，远离$x$的孩子为远侄$b$；B表示黑色，R表示红色，BB表示双黑标记。图中只画决定情形的局部结构，省略的$NIL$都是黑色，省略的子树会补足相应黑高，不要拿图中的几层去硬数整棵树的黑高。

情形$1$：$w$是红色。

        p(B)
       /    \
    x(BB)   w(R)
            /   \
          a(B)  b(B)

$w$是红色，所以$p$必为黑色，$w$的两个孩子都必为黑色。把$w$染黑、$p$染红，对$p$左旋：

        w(B)
       /    \
    p(R)    b(B)
    /   \
 x(BB)  a(B)

$x$的新兄弟变成$a(B)$，是一个黑兄弟。此时双黑还在$x$上，只是从“红兄弟”转换成了“黑兄弟”，接下来按$a$的两个孩子颜色进入情形$2$、$3$或$4$。

情形$2$：$w$是黑色，两个侄子都是黑色。

        p(R)
       /    \
    x(BB)   w(B)
            /   \
          a(B)  b(B)

把$w$染红，双黑标记上移到$p$。这里$p$原来是红色，所以再把$p$染黑就结束：

        p(B)
       /    \
    x(B)    w(R)
            /   \
          a(B)  b(B)

$w$变红后，兄弟那边也少一个黑，和$x$这边的欠账对齐；$p$再染黑，正好补回欠的那个黑。若$p$原来是黑色，则把$p$当作新的$x$继续向上处理。

情形$3$：$w$是黑色，近侄$a$红、远侄$b$黑。

        p(B)
       /    \
    x(BB)   w(B)
            /   \
          a(R)  b(B)

把$w$染红、$a$染黑，对$w$右旋：

        p(B)
       /    \
    x(BB)   a(B)
               \
                w(R)
                  \
                  b(B)

现在$x$的新兄弟是$a(B)$，它的远侄是$w(R)$，变成了红色，于是转化为情形$4$。情形$3$本身不消除双黑，只是把“近侄红、远侄黑”调整成“远侄红”。

情形$4$：$w$是黑色，远侄$b$红。

        p(R)
       /    \
    x(BB)   w(B)
            /   \
          a(B)  b(R)

把$w$染成$p$原来的颜色，把$p$染黑，把$b$染黑，对$p$左旋：

        w(R)
       /    \
    p(B)    b(B)
    /   \
 x(B)  a(B)

$x$的双黑被吸收，变成普通黑色，修复结束。若$p$原来是黑色，则$w$继承黑色；若$p$原来是红色，则$w$继承红色，两边黑高都重新相等。

删除流程总结

把上面的过程压缩一下：

待删节点有两个孩子：转成删除它的中序直接前驱或直接后继，真正被删的节点至多只有一个孩子。
真正被删的节点是红色：直接删，结束。
真正被删的节点是黑色，孩子是红色：孩子染黑顶替，结束。
真正被删的节点是黑色，孩子是$NIL$：给$x$记双黑，按兄弟$w$的颜色和两个侄子的颜色进入情形$1$到情形$4$，直到双黑消除。

一句话总结：红色的$NIL$不存在，黑色的$NIL$本来就到处都是。删掉一个黑节点，不是“放个替代品在那里”就行，而是会让这条分支上的黑节点总数少一个。为了让黑高重新相等，必须通过旋转和变色，从兄弟分支那里“借”一个黑节点过来；双黑只是借之前的临时记账符号。

红黑树的删除修复最多沿树向上处理$O(\log n)$层，旋转次数至多为$3$次，所以删除的时间复杂度仍然是$O(\log n)$。

$B$树与$B^+$树

考研中，对$B$树的要求很高，不但要知道它的基本特点，还要会建立$B$树、插入关键字和删除关键字；而对于$B^+$树，仅要求掌握基本概念。所以贫道个人建议，刚刚看完红黑树的删除的各位小伙伴儿们休息一下，去吃个饭，喝个水，上个厕所，甚至说换一科学一下，换换脑子。之后再回来把这后面的东西看完。

$B$树

一棵$m$阶$B$树要么是空树，要么是满足以下特性的$m$叉树：

每个节点至多有$m$棵子树，即最多包含$m - 1$个关键字。因为节点内的关键字把取值范围分成了若干段，关键字之间才是指向子树的指针。
若$B$树非空，则根节点至少有$1$个关键字，即至少有$2$棵子树。
除根节点外，每个节点至少有$\lceil m/2 \rceil$棵子树，即至少有$\lceil m/2 \rceil - 1$个关键字。
所有终端节点都位于同一层；所有外部叶节点（$NIL$）也位于同一层，它们不存储实际数据，表示查找失败。
节点内的关键字从左到右严格递增；每个关键字两侧的子树，其关键字都落在父节点划分出的对应区间内。

每个节点的结构可以写成：

$P_0$	$K_1$	$P_1$	$K_2$	$P_2$	$\cdots$	$K_n$	$P_n$
子树$0$	关键字$1$	子树$1$	关键字$2$	子树$2$	$\cdots$	关键字$n$	子树$n$

其中$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$且小于$K_{i + 1}$（如果有的话）。

由此可以得到$B$树的基本性质：

任何节点的子树个数都等于该节点内关键字的个数加$1$。
若$B$树非空，根节点至少有$1$个关键字，因此至少有$2$棵子树。
除根节点外，每个节点至少包含$\lceil m/2 \rceil$棵子树、$\lceil m/2 \rceil - 1$个关键字，至多包含$m$棵子树、$m - 1$个关键字。
下层子树中的关键字都落在上层节点关键字划分出的对应区间内。
所有外部叶节点都在最外层，代表查找失败。

$B$树的查找

$B$树的查找和二叉排序树类似，只不过在向孩子走的时候要根据节点内的关键字做多路决策。查找包括两个基本操作：第一步，在$B$树中定位目标节点；第二步，在节点内查找关键字。因为$B$树通常存储在磁盘上，所以前一步在磁盘中进行，后一步在内存中进行。需要先把包含目标节点的磁盘块读入内存，再在内存中用顺序查找或折半查找定位关键字。CPU和内存之间的数据交换速度远快于内存和外存之间的数据交换速度，所以$B$树查找的时间主要耗费在磁盘访问上。磁盘访问次数，也就是目标节点在$B$树中的层数，是决定查找效率的关键因素。

$B$树的高度

这里采用王道教材的约定，不把外部叶节点算入$B$树的高度。硬要把它们算进去也只是多一层，不影响结论。

设$B$树包含$n$个关键字、高度为$h$、阶为$m$，且$n \ge 1$。

最小高度： 当每个节点包含的关键字数达到最大值时，$B$树高度最小。每个节点最多有$m$棵子树，即最多有$m - 1$个关键字，所以高度为$h$的$B$树最多能容纳

$$ n \le (m - 1)(1 + m + m^2 + \cdots + m^{h - 1}) = m^h - 1, $$

因此

$$ h \ge \log_m(n + 1). $$

最大高度： 当每个节点的关键字数达到最小值时，$B$树高度最大。根节点至少有$2$棵子树，除根节点外的每个节点都至少有$\lceil m/2 \rceil$棵子树（终端节点的子树就是外部叶节点），所以第$h + 1$层至少有

$$ 2\left(\left\lceil \frac{m}{2}\right\rceil\right)^{h - 1} $$

个外部叶节点。包含$n$个关键字的$B$树恰好有$n + 1$个外部叶节点，因此

$$ n + 1 \ge 2\left(\left\lceil \frac{m}{2}\right\rceil\right)^{h - 1}, $$

即

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

$B$树的插入

和二叉排序树不同，$B$树找到插入位置后，不能无条件地把关键字直接塞进终端节点，因为插入后可能超过关键字数量上限。

插入过程如下：

定位。 利用$B$树的查找算法，最后会落在一个外部叶节点上；实际插入的位置是这个外部叶节点的父节点，也就是最底层的终端节点。
直接插入。 每个非根节点必须满足$\lceil m/2 \rceil - 1 \le n \le m - 1$。如果插入后关键字总数不超过$m - 1$，直接插入即可。
分裂。 如果插入后关键字总数超过$m - 1$，就要分裂该节点。创建一个新节点，把插入后的关键字从中间位置，即第$\lceil m/2 \rceil$个关键字处分开：
- 左半部分留在原节点；
- 右半部分移入新节点；
- 中间的关键字升入父节点。

如果父节点接收这个关键字后也超过上限，就对父节点继续分裂。这个过程可能一直向上传递到根节点；如果根节点也被分裂，$B$树的高度加$1$。

$B$树的删除

$B$树的插入要考虑关键字数量上限，删除则要考虑关键字数量下限。设

$$ t = \left\lceil \frac{m}{2}\right\rceil, $$

则除根节点外，每个节点至少有$t - 1$个关键字、$t$棵子树，至多有$m - 1$个关键字、$m$棵子树。删除一个关键字后，如果某个节点的关键字数低于$t - 1$，就称为下溢。

删除分两步：先把“删除内部节点中的关键字”转化成“删除终端节点中的关键字”，再处理可能出现的下溢。

第一步：把删除位置移到终端节点。

如果被删关键字$k$在内部节点中，可以用它的前驱或后继代替它：

前驱$k^{\prime}$：$k$左侧子树中最右下方的关键字，也就是左子树中最大的关键字。
后继$k^{\prime}$：$k$右侧子树中最左下方的关键字，也就是右子树中最小的关键字。

用$k^{\prime}$覆盖$k$，然后转到$k^{\prime}$所在的终端节点中删除$k^{\prime}$。前驱和后继都与$k$相邻，替换后仍然满足关键字的大小关系；而且它们一定在终端节点中，所以问题一定可以转化为终端节点删除。前驱和后继任选其一即可，处理方式完全对称。

第二步：删除终端节点中的关键字，并处理下溢。

这里说的终端节点，是最底层真正存储关键字的节点，不是表示查找失败的外部叶节点$NIL$。

删除后分三种情况：

没有下溢。 如果节点删除后仍有至少$t - 1$个关键字，直接结束。
下溢，但相邻兄弟有多余关键字。 如果左兄弟或右兄弟至少有$t$个关键字，就向它借一个。借的时候不能直接把兄弟的关键字拿过来，必须经过父节点：
- 向右兄弟借：父节点中隔开这两个孩子的关键字下移到当前节点末尾，右兄弟的最小关键字上移到父节点原来的位置。如果当前节点是内部节点，还要把右兄弟的第一个孩子指针移到当前节点末尾。
- 向左兄弟借：父节点中隔开这两个孩子的关键字下移到当前节点开头，左兄弟的最大关键字上移到父节点原来的位置。如果当前节点是内部节点，还要把左兄弟的最后一个孩子指针移到当前节点开头。
借完后，当前节点和兄弟的关键字数都回到合法范围，父节点的关键字数不变。
下溢，且相邻兄弟都没有多余关键字。 如果左右兄弟都只有$t - 1$个关键字（或者只有一个相邻兄弟，且它也只有$t - 1$个关键字），就无法借，只能合并。按中序顺序把当前节点、父节点中隔开这两个孩子的关键字、以及一个相邻兄弟合并成一个节点：
- 父节点失去这个分隔关键字，同时少一棵子树；
- 如果当前节点和兄弟是内部节点，合并时还要把它们的子树指针按顺序接起来；
- 合并后的关键字数为$(t - 2) + 1 + (t - 1) = 2t - 2$，不超过$m - 1$，所以不会溢出。

合并会让父节点少一个关键字。如果父节点因此下溢，就对父节点重复上面的“借”或“合并”操作，直到不再下溢或者到达根节点。

根节点是特殊的：根节点允许只有$1$个关键字。如果根节点在合并后变成空节点，就删除这个根节点，让合并后的节点成为新的根，$B$树的高度减$1$。如果整棵树只有一个根节点，删除最后一个关键字后树就变成空树。

删除流程总结：

找到关键字$k$。
若$k$在内部节点中，用前驱或后继替换，转而删除终端节点中的前驱或后继。
从终端节点中删除该关键字。
若没有下溢，结束。
若下溢，先看相邻兄弟有没有多余关键字：有就借，没有就合并。
合并可能让父节点下溢，继续向上处理；根节点变空时删除根节点，树高减$1$。

一句话总结：插入是“溢出后分裂向上传”，删除是“下溢后合并向上传”；借关键字相当于在兄弟和父节点之间做一次旋转，不会改变父节点的关键字数，合并才会让父节点少一个关键字。

$B$树删除的磁盘访问次数与树高同阶，为$O(\log_m n)$；每个节点内最多移动$O(m)$个关键字。插入和删除的传播都最多沿树向上进行$O(\log_m n)$层。

下面用$m = 5$的$B$树举例。此时$t = 3$，每个非根节点至少有$2$个、至多有$4$个关键字；兄弟有$3$个或$4$个关键字时才能借，只有$2$个时只能合并。

例$1$：删除终端节点中的关键字，没有下溢。

[10 20 30]  --删除20-->  [10 30]

删除后还剩$2$个关键字，正好等于下限，不需要调整。

例$2$：删除内部节点中的关键字，用前驱替换。

          [20]
        /      \
   [5 10 15]  [25 30 35]

删除根节点中的$20$。$20$的前驱是左子树中最大的关键字$15$。用$15$代替$20$，再到左终端节点中删除$15$：

          [15]
        /      \
   [5 10]     [25 30 35]

左终端节点还剩$2$个关键字，没有下溢。也可以改用后继$25$，结果是对称的。

例$3$：下溢，向兄弟借关键字。

          [20 40]
        /    |    \
   [5 10] [25 30 35] [45 50]

删除$5$后，左孩子变成$[10]$，只有$1$个关键字，发生下溢。右兄弟$[25 30 35]$有$3$个关键字，可以借出一个。操作如下：

父节点的分隔关键字$20$下移到左孩子末尾，左孩子变成$[10 20]$；
右兄弟的最小关键字$25$上移到父节点，父节点变成$[25 40]$；
右兄弟变成$[30 35]$。

结果为：

          [25 40]
        /    |    \
   [10 20] [30 35] [45 50]

三个节点都至少有$2$个关键字，仍是合法的$B$树。如果删除的是右孩子，就向左兄弟借，操作完全镜像。

例$4$：下溢，合并；父节点继续下溢；根节点消失，树高降低。

                         [30]
                    /            \
          [10 20]                 [40 50]
        /    |    \              /    |    \
   [2 5] [12 15] [22 25]    [32 35] [42 45] [52 55]

删除$5$：

终端节点$[2 5]$变成$[2]$，发生下溢。右兄弟$[12 15]$只有$2$个关键字，不能借，只能合并。把$[2]$、父节点的分隔关键字$10$、右兄弟$[12 15]$合并成$[2 10 12 15]$。
左内部节点$[10 20]$失去$10$，变成$[20]$，也发生下溢。它的右兄弟$[40 50]$只有$2$个关键字，仍然不能借，只能合并。把$[20]$、根节点的分隔关键字$30$、右兄弟$[40 50]$合并成$[20 30 40 50]$。
根节点$[30]$失去$30$，变成空节点。删除根节点，让合并后的$[20 30 40 50]$成为新的根，树高减$1$。

删除后的树为：

新根：[20 30 40 50]
子节点从左到右：
[2 10 12 15]  [22 25]  [32 35]  [42 45]  [52 55]

新根有$4$个关键字、$5$棵子树，正好达到$m = 5$的上限；所有终端节点仍然在同一层，$B$树的合法性恢复。

这四个例子分别覆盖直接删除、内部关键字替换、借关键字和合并。其中例$4$把终端节点合并、父节点合并、根节点消失三种情况串在了一起。实际做题时，只要抓住“先看兄弟能不能借，不能借就合并，合并后继续看父节点”这条线，就不会乱。

$B^+$树

$B^+$树是$B$树的变体，可以看成“分支结点只负责索引、叶结点负责存全部数据”的$B$树。一棵$m$阶$B^+$树通常满足以下条件：

每个分支结点最多有$m$棵子树。
若根结点不是叶结点，则根结点至少有两棵子树；其他每个分支结点至少有$\lceil m/2\rceil$棵子树。
所有叶结点都在同一层。
叶结点包含全部关键字以及指向相应记录的指针；叶结点内的关键字按大小顺序排列，相邻叶结点按顺序链接起来。
分支结点只存索引，不存记录指针。按王道教材的约定，分支结点的关键字个数等于子树个数，每个关键字是其对应子树中关键字的最大值。

因此，$B^+$树中的关键字会在叶结点和分支结点中重复出现：叶结点里的是实际关键字和记录指针，分支结点里的是为了方便索引而复制上去的“最大关键字”。查找时，即使已经在分支结点中看到了目标关键字，也不能直接停下来，必须继续走到叶结点，才能拿到对应的记录。

不同教材对$B^+$树分支结点的“关键字—子树”对应关系写法可能略有差异，但核心不变：分支结点只做索引，所有关键字和记录指针都在叶结点，叶结点之间按顺序链接。

$m$阶$B$树和$m$阶$B^+$树的区别

比较项	$m$阶$B$树	$m$阶$B^+$树
数据存放位置	每个结点都可以存关键字和记录指针	只有叶结点存全部关键字和记录指针，分支结点只存索引
关键字与子树的关系	结点有$n$个关键字，则有$n + 1$棵子树	按王道约定，分支结点有$n$个关键字，则有$n$棵子树
关键字是否重复	每个关键字只出现一次	分支结点中的关键字是叶结点关键字的副本，同一个关键字可能重复出现
叶结点是否链接	不要求链接	所有叶结点按关键字顺序链接，支持范围查找和顺序遍历
查找成功的位置	可能在内部结点成功，也可能在叶结点成功	必须走到叶结点才能取得记录，分支结点命中不算查找结束
查找长度	不同关键字的比较次数可能不同	所有查找都走到叶结点，查找长度稳定，通常等于树高
范围查找	需要中序遍历或多次查找	先定位左边界所在叶结点，再沿叶结点链表顺序扫描，效率更高
结点容量与树高	内部结点还要存记录指针，扇出较小	内部结点只存索引，扇出更大，树通常更矮，磁盘访问次数更少

一句话概括：$B$树是“每个结点都可能带数据”的多路平衡查找树；$B^+$树是“分支只做索引、叶结点存全部数据并且互相链接”的变体。 前者更适合一般查找，后者更适合数据库索引和文件系统这种既要随机查找、又要范围扫描的场景。

散列表（$Hash$表）

散列表就是$Hash$表，也叫哈希表。别去$Linux$家串门的时候指着bash终端嗷嗷喊$hash$。

散列表基本概念

散列函数（也称哈希函数）：把关键字映射到存储地址的函数，即

$$ H(key) = addr. $$

散列函数可能会把两个或两个以上不同的关键字映射到同一个地址，这种现象称为冲突，这些关键字互称同义词。除了直接定址法这种一对一映射，冲突通常难以避免，所以设计散列表时必须同时设计冲突处理方法。

散列表（也称哈希表）：是一种根据关键字直接访问的数据结构，它建立了关键字到存储地址的直接映射。很多语言里的映射和集合类型底层都用到了哈希表，例如$C++$的std::unordered_map、std::unordered_set，$Java$的HashMap、HashSet，$Python$的dict、set，$Go$的map等。注意$C++$的std::map通常是红黑树实现的，不是哈希表；$Java$的Map只是接口，HashMap才是基于哈希表的实现。

在理想情况下，散列表查找的时间复杂度是$O(1)$；但冲突严重时，最坏可能退化到$O(n)$。所以“哈希表一定$O(1)$”是有前提的。

散列函数构造方法

设计散列函数时，一般要注意以下几点：

定义域必须包含全部关键字，计算出的地址必须落在散列表的地址范围内。
地址要尽可能均匀地分布在整个地址空间中，以减少冲突。
计算要尽量简单，能在较短时间内算出任意关键字对应的地址。

直接定址法

直接取关键字的某个线性函数值作为散列地址：

$$ H(key) = key \quad \text{或} \quad H(key) = a \cdot key + b. $$

其中$a$和$b$是常数。该方法设计简单，而且不会产生冲突，适用于关键字分布基本连续的情形；如果关键字分布稀疏、空位很多，就会浪费大量存储空间。

除留余数法

这是最常用的散列函数构造方法。设散列表长度为$m$，选取一个不超过$m$且尽可能接近$m$的质数$p$，令

$$ H(key) = key \bmod p. $$

选取$p$时，要尽量让不同关键字经过映射后近似等概率地落在各个地址上。$p$取质数，是为了减少关键字中公共因子造成的聚集。

数字分析法

设关键字是$r$进制数，各位数码的出现频率可能不同：某些数位分布均匀，另一些数位只出现少数几种数码。此时应选取分布较均匀的数位，用这些数位组合成散列地址。该方法适用于关键字集合已知且固定的情况；如果关键字集合发生变化，就要重新构造散列函数。

平方取中法

先求关键字的平方，再取平方值的中间几位作为散列地址。具体取多少位，根据散列表大小和关键字范围确定。由于平方运算和关键字的每一位都有关，所以散列地址的分布通常比较均匀。

折叠法

把关键字分割成位数相同的若干部分（最后一部分可以短一些），再把这些部分相加，取结果的低位作为散列地址。折叠法适合关键字位数很多、又不好直接分析数位分布的情况。

随机数法

取

$$ H(key) = \mathrm{random}(key) $$

作为散列地址。这里的$\mathrm{random}$是伪随机函数。随机数法适合关键字长度不等的情况，但构造和调试相对麻烦，实际考试中出现得不多。

冲突处理

开放定址法

开放定址法的思想是：散列表中的所有空闲地址对任意关键字开放，发生冲突时按某种探测序列寻找下一个空闲地址。探测序列通常写成

$$ H_i = (H(key) + d_i) \bmod m, \quad i = 1, 2, \cdots, k, $$

其中$m$是散列表长度，$d_i$是第$i$次探测的增量，$k \le m - 1$。常见的增量序列有以下四种：

线性探测法。 取$d_i = 1, 2, \cdots, m - 1$。发生冲突时顺序查看下一个单元，到表尾后回绕到表头。线性探测实现简单，但容易产生“聚集”（也称堆积）：原本映射到地址$i$的同义词占用了$i + 1$，本应放在$i + 1$的元素又被挤到$i + 2$，大量元素在相邻地址上连成一片，查找效率会明显下降。
平方探测法。 取$d_i = 1^2, -1^2, 2^2, -2^2, \cdots, k^2, -k^2$，其中$k \le m/2$。平方探测能缓解线性探测的聚集，但它不能保证探测到散列表的所有位置。为了尽量保证能找到一个空单元，通常要求表长$m$是形如$4k + 3$的质数。
双散列法。 取$d_i = i \cdot H_2(key)$，用第二个散列函数$H_2$计算增量。$H_2(key)$不能为$0$，并且通常要和$m$互质，否则探测序列可能提前循环。双散列能进一步减少聚集，但需要计算两个散列函数。
伪随机序列法。 用伪随机数生成增量序列$d_i$。它的探测顺序看起来是随机的，但本质上仍由确定的种子决定。

开放定址法有一个很重要的注意点：删除元素时不能直接把槽位置空。如果直接置空，后面本来通过探测链才能找到的元素就会被“截断”，查找会误判为失败。正确做法是给被删位置打一个删除标记（墓碑），查找时遇到删除标记继续往后探测，插入时可以复用这些标记位置。

另外，开放定址法的装填因子$\alpha$必须小于$1$，因为表中至少要留一个空单元，否则查找失败时可能永远探测不到空位置。

拉链法

拉链法把散列到同一地址的所有同义词组织成一个链表，散列表的每个槽位存放对应链表的头指针。查找、插入和删除都在相应的链表中进行。

拉链法的优点是删除简单，装填因子可以大于$1$；缺点是要额外存储指针，而且链表节点在内存中不连续，缓存友好性通常不如开放定址法。它特别适合需要频繁插入和删除的情况。

方法	优点	缺点
开放定址法	不需要额外指针，空间连续	容易聚集，删除要加标记，$\alpha < 1$
拉链法	删除方便，$\alpha$可以大于$1$	需要指针空间，节点分散

散列表的删除

拉链法：直接在对应链表中删除节点即可。
开放定址法：不能直接置空，要使用删除标记；否则会破坏后续元素的探测链。

查找效率

散列表的查找过程和构造过程基本一致：对于给定关键字$key$，先通过散列函数算出初始地址，再按照冲突处理方法依次探测；如果找到关键字，则查找成功；如果探测到空单元（开放定址法）或走到链表末尾（拉链法），则查找失败。

散列表的查找效率主要取决于三个因素：散列函数、冲突处理方法和装填因子。设散列表长度为$m$，表中记录数为$n$，装填因子定义为

$$ \alpha = \frac{n}{m}. $$

$\alpha$越大，表中越拥挤，冲突概率越高，平均查找长度越大；$\alpha$越小，冲突越少，但浪费的空间也越多。

在等概率查找成功的条件下，

$$ \mathrm{ASL}_{\text{成功}} = \frac{1}{n}\sum_{i = 1}^{n}C_i, $$

其中$C_i$是查找第$i$个记录所需的关键字比较次数。

查找失败时，不能只除以记录数，而要按散列函数可能得到的地址来平均：

$$ \mathrm{ASL}_{\text{失败}} = \frac{1}{m}\sum_{i = 0}^{m - 1}C_i', $$

其中$C_i’$是从地址$i$开始探测、直到确定查找失败所需的比较次数。

散列表的$\mathrm{ASL}$主要依赖于装填因子$\alpha$，而不直接依赖于$n$或$m$。这也是为什么散列表通常用$\alpha$来衡量“满不满”，而不是只看元素个数。

例：线性探测法的查找成功$\mathrm{ASL}$。 设散列表长度$m = 10$，散列函数$H(key) = key \bmod 10$，依次插入关键字$12, 22, 32, 42, 5, 15$。