没有删除功能。来自多方网络资料。

主要参考：
https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
如果天空不死：http://www.cnblogs.com/skywang12345/p/3624343.html#top

package DataStructureAndAlgor;

public class RBTree<T extends Comparable<T>> {
    private class Node {
        boolean color;
        T key;
        Node left;
        Node right;
        Node parent;

        Node(boolean color, T key, Node left, Node right, Node parent) {
            this.color = color;
            this.key = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

    private Node root;
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    /*
     * 对红黑树的节点(x)进行左旋转
     *
     * 左旋示意图(对节点x进行左旋)：
     *      px                              px
     *     /                               /
     *    x                               y
     *   /  \      --(左旋)->            / \                #
     *  lx   y                         x    ry
     *     /   \                     /  \
     *    ly   ry                   lx   ly
     *
     *
     */
    private void leftRotate(Node x) {
        //取x的右结点为y
        Node y = x.right;
        //将y的左子树完全分离为x的右子树
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }

        y.parent = x.parent;//y指向新的父结点
        //新的父结点指向y(以下)
        if (x.parent == null) {//如果x的父结点为null，说明x是根节点
            this.root = y;
        } else {//如果x不是根节点
            if (x.parent.left == x) {//如果x是左子树
                x.parent.left = y;
            } else {//如果x是右子树
                x.parent.right = y;
            }
        }
        y.left = x;
        x.parent = y;
        //TODO:我觉得可以试试返回当前根节点的方法，可能更简洁。
    }

    /*
     * 对红黑树的节点(y)进行右旋转
     *
     * 右旋示意图(对节点y进行左旋)：
     *            py                               py
     *           /                                /
     *          y                                x
     *         /  \      --(右旋)->            /  \                     #
     *        x   ry                         lx     y
     *       / \                                   / \                   #
     *      lx  rx                                rx  ry
     *
     */
    private void rightRotate(Node y) {
        Node x = y.left;

        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }

        x.parent = y.parent;
        if (y.parent == null) {//y是根节点
            this.root = x;
        } else {//y不是根节点
            if (y.parent.left == y) {//y在左
                y.parent.left = x;
            } else {//y在右
                y.parent.right = x;
            }
        }
        x.right = y;
        y.parent = x;
    }

    public void insert(T key) {
        root = insertNode(root, key, null);
        Node node = search(root, key);
        insert_case1(node);
    }

    private Node search(Node node, T key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            return search(node.left, key);
        } else if (cmp > 0) {
            return search(node.right, key);
        } else {
            return node;
        }
    }

    /**
     * @param node   插入的根起点
     * @param key    插入的值
     * @param parent node的父结点
     * @return
     */
    private Node insertNode(Node node, T key, Node parent) {
        if (node == null) {
            return new Node(RED, key, null, null, parent);//结点颜色初始化为RED
        } else {
            int cmp = key.compareTo(node.key);
            if (cmp < 0) {
                node.left = insertNode(node.left, key, node);
            } else if (cmp > 0) {
                node.right = insertNode(node.right, key, node);
            } //else{key equals node.key,二叉树不允许存在相同的值的结点。}
        }
        return node;
    }

    private Node grandparent(Node node) {
        return node.parent.parent;
    }
    private Node uncle(Node node) {
        if (node.parent == grandparent(node).left) {
            return grandparent(node).right;
        } else {
            return grandparent(node).left;
        }
    }

    //当前节点为父结点：直接把结点涂成黑色。
    private void insert_case1(Node n) {
        if (n.parent == null) {
            n.color = BLACK;
        } else {
            insert_case2(n);
        }
    }

    //当前节点的父结点为黑色：啥也不用做。
    private void insert_case2(Node n) {
        if (n.parent.color == BLACK) {
            return;
        } else {
            insert_case3(n);
        }
    }

    //当前结点的父结点是红色,且叔叔结点是红色。
    private void insert_case3(Node n) {
        if (uncle(n) != null && uncle(n).color == RED) {
            n.parent.color = BLACK;
            uncle(n).color = BLACK;
            grandparent(n).color = RED;
            insert_case1(grandparent(n));
        } else {
            insert_case4(n);
        }
    }
    //此时当前结点，父结点，祖父结点，三者呈之字形，将其调整为一字型。
    private void insert_case4(Node n) {
        if (n == n.parent.right && n.parent == grandparent(n).left) {
            leftRotate(n.parent);
            n = n.left;
        } else if (n == n.parent.left && n.parent == grandparent(n).right) {
            rightRotate(n.parent);
            n = n.right;
        }
        insert_case5(n);
    }
    //此时当前结点，父结点，祖父结点，三者呈一字型。
    private void insert_case5(Node n) {
        n.parent.color = BLACK;
        grandparent(n).color = RED;
        if (n == n.parent.left && n.parent == grandparent(n).left) {
            rightRotate(grandparent(n));
        }else {
            leftRotate(grandparent(n));
        }
    }

    private void print(Node node,int depth){
        if (node!=null){
            for (int i=0;i<depth;i++){
                System.out.print("--");
            }
            System.out.print(node.key);
            System.out.println();//换行

            depth++;

            print(node.left,depth);
            print(node.right,depth);
        }
    }
    public void print(){
        print(root,0);
    }
}