2-3查找树

定义

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

2-结点，含有一个键（及其对应的值）和两条链接，左链接指向的2-3树中的键都小于该结点，右结点指向的2-3树中的键都大于该结点。
3-结点，含有两个键（及其对应的值）和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右结点指向的2-3树中的键都大于该结点。
注：一棵完美平衡的2-3查找树中所有的空链接到根结点的距离应该都是相同的。

基本操作

查找

要判断一个键是否存在树中，先将它和根结点中的键比较，如果它和其中任意一个相等，查找命中；否则我们就根据比较结果找到指定的区间的链接，并在其指向的子树中递归的继续查找，如果是空链接，查找未命中。

如上图对于H的查找命中，对于B的查找未命中

向2-结点中插入新键

要在2-3树中插入一个新的结点，可以和查找二叉查找树一样先进行一次未命中查找，然后把新结点挂在树的底部，但是为了保证树的完美平衡性，要将2-结点替换成3-结点，将要插入的键保存于其中。

向3-结点中插入新键

假设我们需要向一棵只含有一个3-结点的树中插入一个新键。这棵树有两个键，所以在它唯一的结点中已经没有可插入新建的空间，为了新键的插入，我们先将新键存入该结点中，使之成为一个4-结点，然后将它转换成一棵由3个2-结点组成的2-3树，其中一个结点（根）含有中键，一个结点含有3个键中的最小者（和根结点的左链接相连），一个结点含有3个键中的最大者（和根结点的右链接相连）。这棵树既是一棵含有3个结点的二叉查找树，同时也是一颗完美平衡的2-3树，因为其中所有的空链接到根结点的距离都相等。插入之前树的高度为0，插入后树的高度为1。

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

假设未命中的查找结束于一个3-结点，而他的父结点是一个2-结点。在这种情况下我们需要在维持树的完美平衡的前提下为新键腾出空间。我们先像刚才那样构造一个4-结点并将其分解，此时的分解不会为中键创建一个新结点，而是将其移动到原来的父结点中。如下

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

假设为命中的查找命中于一个父结点为3-结点的结点，我们可以再次像刚才一样构造一个临时的4-结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3-结点，因此我们要用这个中键构造一个新的临时4-结点，然后在这个结点上进行相同的变换，即分解这个父结点并将它插入到他的父结点中，推广到一般情况，这样一直向上不断分解临时的4-结点并将中键插入到更高级的父结点，直到遇见一个2-结点并将它替换为一个不需要继续分解的3-结点，或者是到达3-结点的根

分解根结点

如果从插入结点一直到根结点的路径上都是3-结点，我们的根结点最终变成一个临时的4-结点，我们可以按照向一棵只有3-结点的树中插入新键的方法处理这个问题，将临时的4-结点分解成3个2-结点，使得树高加1.

红黑二叉查找树

基本思想：

红黑二叉查找树背后的基本思想是用标准的二叉树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。树中的链接分成两种类型：红链接将两个2-结点连接起来构成一个3-结点，黑链接则是2-3树中的普通链接

等价定义：

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：
1.红链接均为左链接
2.没有任何一个结点同时和两个红链接相连。
3.该输是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
满足这样定义的红黑树和相应的2-3树是一一对应的

如上图所画的，如果将一棵红黑树中的红链接画平，那么所有的空链接到根结点的距离都是相同的，如果将所有的红链接相连的结点合并，就可以得到一棵2-3树。

实现

颜色表示

每一条结点都会只有一条指向自己的链接（从它父结点的父结点指向它），将链接的颜色保存在表示结点的Node数据类型的布尔变量color中。

private static final boolean RED = true;
private static final boolean BLACK = false;

//含有color变量的Node对象
private class Node{
	Key key;			//键
	Value value;		//相关联的值
	Node left,right;	//左右子树
	int N;				//这课子树中的节点总数
	boolean color;		//由其父节点指向他的链接的颜色
	
	Node(Key key, Value value, int N, boolean color){
		this.key = key;
		this.value = value;
		this.N = N;
		this.color = color;
	}
}

private boolean isRed(Node x){
	if(x==null)
		return false;
	return x.color = RED;
}

旋转

在实现红黑树的操作中可能会出现右链接或者两条连续的红链接，在完成操作之前这些情况都会被小心地旋转并修复。旋转操作会改变红链接的指向，首先假设我们有一条红色的右链接需要被转换成左链接，这种操作叫做左旋转

同时也有一种操作叫做右旋转，即一条红链接需要被转换成右链接

向单个2-结点插入新键

一棵只有一个键的红黑树只含有一个2-结点，插入另一个键后，我们需要将他们进行旋转，如果新键小于老键，只需要新增一个红色的结点即可，如果新键大于老键，则需要旋转来进行修改操作，如下图

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

用和二叉查找树相同的方法向一棵红黑树中插入一个新建结点，会在树底部新增一个结点，为了保证有序性，总是用红链接将新结点和它的父结点相连，如果父结点是一个2-结点，那么会出现如图情况

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

可以分成三种情况：新键小于树中的两个键，在两者之间，或者是大于树中的两个键，每种情况都会出现一个同时连接到两个红链接的结点。
1.新建大于原树中的两个键
2.新建小于原树中的两个键 3.新建介于原树中的两个键之间

颜色转换

除了将子结点的颜色由红变黑之外，还要将父结点的颜色由红变成黑色，这项操作最重要的性质在于它和旋转操作一样是局部变换，不会影响整棵树的黑色平衡性，我们每次插入后都会将根结点设为黑色（每次根结点由红变黑时树的黑链接高度就会加1），因此： 1.如果右子结点是红色的而左子结点是黑色的，进行左旋转。
2.如果左子结点是红色的而且它的左子结点也是红色的，进行右旋转。 3.如果左右子结点均是红色的，进行颜色转换。

算法实现

/**
 * 红黑树的插入算法
 * @author zzk
 *
 */
public class RedBlackBST<Key extends Comparable<Key>,Value> {

private static final boolean RED = true;
private static final boolean BLACK = false;

private Node root;
//含有color变量的Node对象
private class Node{
	Key key;			//键
	Value value;		//相关联的值
	Node left,right;	//左右子树
	int N;				//这课子树中的节点总数
	boolean color;		//由其父节点指向他的链接的颜色
	
	Node(Key key, Value value, int N, boolean color){
		this.key = key;
		this.value = value;
		this.N = N;
		this.color = color;
	}
}

private boolean isRed(Node x){
	if(x==null)
		return false;
	return x.color = RED;
}

public int size(){
	return size(root);
}

private int size(Node x) {
	if(x==null)
		return 0;
	else
		return x.N;
}

//向左旋转h的右链接
private Node rotateLeft(Node h){
	Node x = h.right;
	h.right = x.left;
	x.left = h;
	x.color = h.color;
	h.color = RED;
	x.N = h.N;
	h.N = 1 + size(h.left)+ size(h.right);
	return x;
}
//向右旋转h的左链接
private Node rotateRight(Node h){
	Node x = h.left;
	h.left = x.right;
	x.right = h;
	x.color = h.color;
	h.color = RED;
	x.N = h.N;
	h.N = 1 + size(h.left)+size(h.right);
	return x;
}
//颜色转换（转换一个结点的两个红色子结点的颜色）
private void flipColors(Node h){
	h.color = RED;
	h.left.color = BLACK;
	h.right.color = BLACK;
}

public void put(Key key, Value value){
	//查找key，找到就更新其值，否则就为他新建一个结点
	root = put(root, key, value);
	root.color = BLACK;
}

/**
 * 1.如果右子结点是红色的而左结点是黑色的，进行左旋转
 * 2.如果左子结点是红色的且它的左结点也是红色的，进行右旋转
 * 3.如果左右子结点均为红色，进行颜色转换
 * @param h
 * @param key
 * @param value
 * @return
 */
private Node put(Node h, Key key, Value value){
	if(h==null)
		return new Node(key,value,1,RED);
	int cmp = key.compareTo(h.key);
	if(cmp<0)
		h.left = put(h.left, key, value);
	else if(cmp>0)
		h.right = put(h.right, key, value);
	else
		h.value = value;
	//如果右子结点是红色的而左结点是黑色的，进行左旋转
	if(isRed(h.right) && !isRed(h.left))
		h = rotateLeft(h);
	//如果左子结点是红色的且它的左结点也是红色的，进行右旋转
	if(isRed(h.left) && isRed(h.left.left))
		h = rotateRight(h);
	//如果左右子结点均为红色，进行颜色转换
	if(isRed(h.left) && isRed(h.right))
		flipColors(h);
	
	h.N = size(h.left) + size(h.right) + 1;
	return h;
}

}

红黑树的性质

所有基于红黑树的符号实现都能保证操作的运行时间为对数级别（除了范围查找外，他所需的额外时间和返回的键的数量成正比）

各种符号表实现的性能总结：

算法（数据结构）	最坏的情况下的运行时间的增长数量级（N次插入之后）	-	平均情况下的运行时间的增长数量级（N次随机插入之后）	-	是否支持有序相关的操作
-	查找	插入	查找命中	插入	-:
顺序查询（无序链表）	N	N	N/2	N	否
二分查找（有序数组）	lgN	N	lgN	N/2	是
二叉树查找（二叉查找树）	N	N	1.39lgN	1.39lgN	是
2-3树查找	2lgN	2lgN	1.00lgN	1.00lgN	是