紅黑二叉查找樹的基本思想是用標準的二叉查找樹和一些額外的信息來表示2-3樹，有以下特性：
1.紅鏈接均為左鏈接；
2.沒有任何一個結點同時和兩條紅鏈接相連；
3.該樹是完美平衡的，即任意空鏈接到根結點的路徑上的黑鏈接數(shù)量相
同。

紅黑樹的結點表示如下：

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 = coloe;
    }
}
private boolean isRed(Node x){
    if(x == null)  return false;
    return x.color = RED;
}

在我們實現(xiàn)某些操作過程中可能會出現(xià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 = size(h.left) + size(h.right) + 1;
    return x;
}

//將左側的紅色鏈接旋轉至右側
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 = size(h.left) + size(h.right) + 1;
    return x;
}

//將兩條紅鏈接轉化為黑鏈接
void flipColors(Node h){
    h.color = RED;
    h.left = BLACK;
    h.right = BLACK;
}

通過謹慎的使用左旋轉，右旋轉和顏色轉換這三種簡單的操作，我們就能保證插入操作后的紅黑樹和2-3樹的一一對應關系。

紅黑樹的插入算法：

public class RedBlackBST<Key extends Comparable<Key>, Value>{
    private Node root;
    private class Node   // 含有color變量的Node對象定義

    private boolean isRed(Node h);
    private Node rotateLeft(Node h);
    private Node rotateRight(Node h);
    private void flipColors(Node h);
    private int size();

    private void put(Key key, Value val){
        root = put(root, key, val);
        root.color = BLACK;
    }
    private Node put(Node h, Key key, Value val){
        if( h== null)
            return new Node(Key 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))  h = flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }
}

紅黑樹的刪除算法：
（待續(xù)）