[TOC]
背景：
二叉查找树在最坏情况下的性能是很糟糕的。它会成为只有一个分支的树。所以我们需要提出一种新的数据结构来满足要求。接下来介绍的二分查找树能保证不论如何改造它，它的运行时间都是对数级别的。
定义：
- 一颗2-3查找树或为一颗空树，或由一下结点组成：
- 2-结点，含有一个键和两条链接，左链接指向的2-3树的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
- 3-结点，含有两个键和三条链接，左链接指向的2-3树的键都小于该结点，中链接指向的2-3树都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
我们将指向一颗空树的链接成为空链接。
一颗完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的。
查找算法：
-
将二叉查找树中的查找算法进行一般化，就可以得到2-3树的查找算法。
插入算法：
-
向2-结点中插入新键。
-
向一颗只含有一个3-结点的树中插入新键。
-
向一个父结点为2-结点的3-结点中插入新键。
-
向一个父结点为3-结点的3-结点中插入新键。
存在的问题：
尽管我们可以用不同的数据类型表示2-结点和3-结点并写出变换所需的代码，但用这种直白的表示方法实现大多数的操作并不方便，因为需要处理的情况实在太多。所以，我们进一步提出一种新的抽象数据类型---红黑二叉查找树。用这种数据结构来表达并实现2-3树。
思想：
红黑二叉查找树背后的基本思想使用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。
我们将树中的链接分为两种类型：红链接将两个2-结点连接起来构成一个3-结点，黑链接则是2-3树中的普通链接。
红黑树完整实现代码：
public class RedBlackBST<Key extends Comparable<Key>,Value> {
private Node root;
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;
}
private int size(Node x){
if(x == null)
return 0;
else
return x.N;
}
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);
}
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;
}
void flipColors(Node h){
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
private void put(Key key, Value val){
//查找key，找到则更新其值，否则为它新建一个结点
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val){
if(h == null)
//标准的插入操作，和父结点用红链接相连
return new Node(key, val, 1, RED);
int cmp = key.compareTo(h.key);
if(cmp < 0)
h.left = put(h.left, key, val);
else if(cmp > 0)
h.right = put(h.right, key, val);
else
h.val = val; //找到了，则跟新这个键的值
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;
}