树 (二)：2-3 查找树及红黑二叉查找树

写在前面

本文内容来源于红色的《算法》一书，由于个人理解水平有限，故部分内容可能会出现错误，还请包涵

2-3 查找树

我们已经知道在最坏的情况下，BST 的查找性能等同于链表。我们希望能够找到一种二分查找树，并能保证无论如何构造它，该树的运行时间都是对数级别的

理想情况下，我们希望一颗含有 N 个结点的树的树高为 lgN。但在动态插入中保证树的完美平衡代价太高，我们可以适当地放宽要求，于是 2-3 查找树应运而生

定义

一棵 2-3 查找树或为一颗空树，或由以下结点组成

2- 结点，含有一个键（及其对应的值）和两条链接，左链接指向的 2-3 树中的键都小于该结点，右链接指向的 2-3 树中的键都大于该结点
3- 结点，含有两个键（及其对应的值）和三条链接，左链接指向的 2-3 树中的键都小于该结点，中链接指向的 2-3 树中的键都位于该结点的两个键之间，右链接指向的 2-3 树中的键都大于该结点

查找

判断一个键是否在树中的基本流程：

将要查找的键与根结点中的键比较，若它与其中任意一个相等，查找命中
若小于根结点中的最小键，则在左子树中（递归地）进行查找
若大于根结点中的最大键，则在右子树中（递归地）进行查找
若位于根结点中的最小键和最大键之间，则在中子树中（递归地）进行查找

向 2- 结点中插入新键

可以和 BST 一样先进行一次未命中的查找，然后把新结点挂在树的底部，但是这样会破坏树的完美平衡性

故如果未命中的查找结束于一个 2- 结点，则只需要将这个 2- 结点转换为一个 3- 结点，然后将插入的键保存在其中即可

向一颗只含有一个 3- 结点的树中插入新键

由于这棵树中只含有一个 3- 结点，唯一的结点中已经没有可插入新键的空间了。为了将新键插入，可以将 3- 结点暂时地转换为 4- 结点，则该 4- 结点含有 3 个键和 4 个链接。

很容易地可以将 4- 结点转换为由 3 个 2- 结点组成的 2-3 树，其中一个根结点含有中键，一个结点含有 3 个键中的最小者（与根结点的左链接相连），一个结点含有 3 个键中的最大者（与根结点的右链接相连）

这棵树既是一颗含有 3 个结点的二叉查找树，又是一棵完美平衡的 2-3 树

插入前树的高度为 0，插入后树的高度为 1。这种情况说明了 2-3 树的生长过程

向一个父结点为 2- 结点的 3- 结点中插入新键

同刚才的情况一致，先构建一个临时的 4- 结点，然后将其分解

但此时我们不会为中键创建一个新的结点，而是将其移动到原来的父节点中，生成一个 3- 结点

而这个临时 4- 结点中最小的键转换为新的 3- 根结点的中子树，而 4- 结点中最大的键仍旧为根结点的右子树

向一个父结点为 3- 结点的 3- 结点中插入新键

依旧是构造一个临时的 4- 结点并分解它，将它的中键插入它的父结点中。此时 4- 结点由原来的插入结点上浮至其父结点

若父结点的父结点为 2- 结点，则问题转换为向一个父结点为 2- 结点的 3- 结点中插入新键

若父结点的父结点也为 3- 结点，则父节点的中键也插入至其父结点中，造成的结果就是这个临时的 4- 结点一层层地往上浮，直至碰见一个 2- 父结点或 3- 根结点

分解根结点

分解根结点的情况和向一颗只含有一个 3- 结点的树中插入新键的情况是类似的，根结点都是变成了一个临时的 4- 结点。于是将临时的 4- 根结点分解成 3 个 2- 结点，使树的高度加一即可

总结

和标准的二叉查找树由上向下生长不同，2-3 树的生长是由下向上的

在一棵大小为 N 的 2-3 树中，查找和插入操作访问的结点必然不超过 lgN 个

2-3 树具有很好的平衡性，即使按照升序插入新结点，树的高度也不会超过 lgN

红黑二叉查找树

红黑二叉查找树用简单的数据结构来表达并实现了上述的 2-3 查找树

替换 3- 结点

红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由 2- 结点组成）和一些额外的信息（替换 3- 结点）来表示 2-3 树

红黑二叉查找树中的链接分为两种类型：

红链接：将两个 2- 结点链接起来构成一个 3- 结点
黑链接：2-3 树中的普通链接
准确地说，2-3 树中的 3- 结点相当于红黑二叉查找树中由一条左斜的红色链接相连的两个 2- 结点

对于任意的 2-3 树，只要对结点进行转换，都可以派生出一棵对应的二叉查找树。我们将用这种方式表示 2-3 树的二叉查找树称为红黑二叉查找树（以下简称红黑树）

一种等价的定义

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：

红链接均为左链接
没有任何一个结点同时和两条红链接相连
该树是黑色完美平衡的，即任意空链接到根结点的路径上的黑链接数量相等
满足这样定义的红黑树和相应的 2-3 树是一一对应的

如果将红黑树的红链接画平，则所有的空链接到根结点的距离都是相同的

如果我们将由红链接相连的结点合并，得到的就是一棵 2-3 树

因此，红黑树结合了二叉查找树中简洁高效的查找方法和 2-3 树中高效的平衡插入算法

颜色表示

在表示结点的 Node 数据类型中加入颜色信息（boolean color），若指向该结点的链接是红色，则 color 为 true

private static final boolean RED = true;

private static final boolean BLACK = false;

private class Node {

	Key key;
	
	Value val;
	
	Node left, right;
	
	int n;
	
	boolean color;
	
	Node(Key key, Value val, int n, boolean color) {
	
		this.key = key;
		
		this.val = val;
		
		this.n = n;
		
		this.color = color;
		
	}
	
}

private boolean isRed(Node x) {

	if (x == null) return false;
	
	return x.color == RED;
	
}

旋转

在对红黑树进行操作时可能会出现红色的右链接或两条连续的红链接，这时候就需要对红黑树进行旋转操作来修复树，旋转操作会改变红链接的指向

将一条红色的右链接转换为左链接称为左旋转

右旋转类似

旋转操作可以保持红黑树的两个重要性质：有序性和完美平衡性

向单个 2- 结点插入新键

若新键小于老键，只需要新增一个红色的结点，新的红黑树和单个 3- 结点完全等价。若新键大于老键，则新增的红色结点将会产生一条红色的右链接，只需要进行一次左旋转即可

向树底部的 2- 结点插入新键

用和二叉查找树相同的方式向一棵红黑树中插入一个新键会在树的底部新增一个结点，但总是用红链接将新结点与它的父结点相连

如果它的父结点是一个 2- 结点（即黑结点），那么刚讨论的向单个 2- 结点插入新键的方法仍然适用

向一棵双键树（即一个 3- 结点）中插入新键

此情况又可分为三种子情况：新键小于树中的两个键、在两者之间、大于树中的两个键，每个情况中都会产生一个同时连接到两条红链接的结点

最简单的是新键大于树中的两个键，因此它被连接到 3- 结点的右链接。此时树是平衡的，根结点为中间大小的键。如果将两条链接的颜色都由红变黑，那么我们就得到了一棵由三个结点组成、高为 2 的平衡树。其他两种情况最终也会转换为这种情况
若新键小于树中的两个键，则会产生两条连续的红色左链接。此时我们次要将上层的红链接右旋转即可得到第一种情况
若新键位于树中两键之间，则会产生一条上层红色左链接和一条下层红色右链接，则将下层红链接左旋转即可转换为两条连续的红色左链接的情况

总的来说，我们通过 0、1 和 2 次旋转以及颜色的变化得到了期望的结果

第一种情况下两条链接的颜色由红变黑，而中键结点的颜色需要设为红

根结点总是黑色

刚讨论过颜色转换会使根结点遍为红色。严格地说，红色的根结点说明根结点是 3- 结点的一部分，但实际情况并不是这样。因此我们在每次插入后都会将根结点设为黑色

注意，每当根结点由红变黑时数的黑链接高度就会加一

向树底部的 3- 结点插入新键

此种情况同向一棵双键树种插入新键的情况类似，中键结点的颜色变红，相当于将它送入了父结点。这意味者在父结点种继续插入一个新键，等价于 2-3 树中将中键结点一层层地往上浮

红黑树中的红链接向上传递情况如下