红黑树

红黑二叉查找树的基本思想是用标准的二叉查找树和一些额外的信息来表示2-3树，有以下特性：
1.红链接均为左链接；
2.没有任何一个结点同时和两条红链接相连；
3.该树是完美平衡的，即任意空链接到根结点的路径上的黑链接数量相
同。

红黑树的结点表示如下：

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;
}

---

在我们实现某些操作过程中可能会出现红色右链接或者是两条红色左链接，故我们需要在操作结束的时候修复这些情况。

//将右侧的红色链接旋转至左侧
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;
    }
}

---

红黑树的删除算法：
（待续）