下午写了一下红黑树的插入操作，这样就可以构造一棵红黑树。红黑树在很多地方都非常重要。例如：给你上千万或上亿数据(有重复),统计其中出现次数最多的前 N 个数据

package 红黑树;public class RedBlackBST 
    
     ,Value>{    private static final boolean RED = true;    private static final boolean Black = false;    private Node root;    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;        else            return x.color == RED;    }    //返回大小    public int size()    {        return size(root);    }    private int size(RedBlackBST
     
      .Node x) {        if(x == null)            return 0;        else            return x.N;    }    //节点的左旋转:有一条红色的右链接需要被转化为左链接    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;    }    //节点的右旋转:将一个红色左链接转化为一个红色右链接    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.right.color = Black;        h.left.color = Black;    }    //红黑树的插入    public 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,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.right) && isRed(h.left)) h = rotateRight(h);        if(isRed(h.right) && isRed(h.left)) flipColors(h);        h.N = 1 + size(h.left)+ size(h.right);        return h;    }}