Java实现红黑树(平衡二叉树)的详细过程

public interface RedBlackBST<Key extends Comparable<Key>,Value> {

    
    Value get(Key key);

    
    void put(Key key,Value value);

    
    void delete(Key key);

}

    
    Key select(int k);

    
    Key min();

    
    Key max();

    
    int rank(Key key);

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{
        
        private boolean color;//指向该结点的链接的颜色
        
        private Key key;//键
        
        private Value value;//值
        
        private Node left,right;//该结点指向左结点的链接和右结点的链接
        
        private int n;//该子树的结点树

        public Node(Key key,Value value,boolean color,int n){
            this.key = key;
            this.value = value;
            this.color = color;
            this.n = n;
        }
    }
    
}

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

    //计算某个子树的结点总数
    private int size(Node x){
        if (x == null) return 0;
        else return x.n;
    }

    
    private Node rotateLeft(Node h){
        Node t = h.right;
        h.right = t.left;
        t.left = h;
        t.color = h.color;
        h.color = RED;
        t.n = h.n;//转换后子树的结点是不变的，
        h.n = size(h.left) + size(h.right) + 1;
        return t;
    }

    //判断链接是否为红色，不是返回false
    private boolean isRed(Node x){
        if (x == null) return false;
        return x.color;
    }

    
    private void changeColor(Node x){
        x.color = true;
        x.left.color = false;
        x.right.color = true;
    }

    
    public Value get(Key key){
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        return get(root,key);
    }
    
    private Value get(Node x,Key key){
        for (;;){
            if (x == null) return null;
            int cmp = key.compareTo(x.key);
            if (cmp == 0) return x.value;
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
    }

    
    public void put(Key key,Value value){
        if (key == null) throw new IllegalArgumentException("argument to put() is null");
        root = put(root,key,value);
        root.color = false;
    }

    private Node put(Node x,Key key,Value value){
        if (x == null) return new Node(key,value,RED,1);
        int cmp = key.compareTo(x.key);
        if (cmp == 0) {x.value = value;}
        else if (cmp < 0) x.left = put(x.left,key,value);
        else x.right = put(x.right,key,value);
        
        if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
        if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
        if (isRed(x.left) && isRed(x.right)) changeColor(x);
        
        x.n = size(x.left) + size(x.right) + 1;
        return x;
    }

    
    public Key select(int k){
        return select(root,k);
    }

    private Key select(Node x,int k){
        while(x != null){
            int t = x.left.N;
            if (t > k) x = x.left;
            else if (t < k){
                x = x.right;
                k = k - t - 1;
            }
            else return x.key;
        }
        return null;
    }

    
    public int rank(Key key){
        return rank(root,key);
    }

    private int rank(Node x,Key key){
        while (x != null){
            int cmp = key.compareTo(x.key);
            int count = x.left.N;
            if (cmp == 0) return (count < root.N ? count : 1 + root.left.N + count);
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
        return 0;
    }