Java集合详解6：这次，从头到尾带你解读Java中的红黑树

*   Case 1:新节点的兄弟节点为**红色**，此时若新节点在左边则做左旋操作，否则做右旋操作，之后再将其父节点颜色改变为红色，兄弟节点

*   红父二黑侄：将父节点变成黑色，兄弟节点变成红色，新节点变成黑色即可,如下图所示

/* 插入一个节点
 * @param node
 */
private void insert(RBTreeNode<T> node){
    int cmp;
    RBTreeNode<T> root = this.rootNode;
    RBTreeNode<T> parent = null;

    //定位节点添加到哪个父节点下
    while(null != root){
        parent = root;
        cmp = node.key.compareTo(root.key);
        if (cmp < 0){
            root = root.left;
        } else {
            root = root.right;
        }
    }

    node.parent = parent;
    //表示当前没一个节点，那么就当新增的节点为根节点
    if (null == parent){
        this.rootNode = node;
    } else {
        //找出在当前父节点下新增节点的位置
        cmp = node.key.compareTo(parent.key);
        if (cmp < 0){
            parent.left = node;
        } else {
            parent.right = node;
        }
    }

    //设置插入节点的颜色为红色
    node.color = COLOR_RED;

    //修正为红黑树
    insertFixUp(node);
}

/**
 * 红黑树插入修正
 * @param node
 */
private void insertFixUp(RBTreeNode<T> node){
    RBTreeNode<T> parent,gparent;
    //节点的父节点存在并且为红色
    while( ((parent = getParent(node)) != null) && isRed(parent)){
        gparent = getParent(parent);

        //如果其祖父节点是空怎么处理
        // 若父节点是祖父节点的左孩子
        if(parent == gparent.left){
            RBTreeNode<T> uncle = gparent.right;
            if ((null != uncle) && isRed(uncle)){
                setColorBlack(uncle);
                setColorBlack(parent);
                setColorRed(gparent);
                node = gparent;
                continue;
            }

            if (parent.right == node){
                RBTreeNode<T> tmp;
                leftRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            setColorBlack(parent);
            setColorRed(gparent);
            rightRotate(gparent);
        } else {
            RBTreeNode<T> uncle = gparent.left;
            if ((null != uncle) && isRed(uncle)){
                setColorBlack(uncle);
                setColorBlack(parent);
                setColorRed(gparent);
                node = gparent;
                continue;
            }

            if (parent.left == node){
                RBTreeNode<T> tmp;
                rightRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            setColorBlack(parent);
            setColorRed(gparent);
            leftRotate(gparent);
        }
    }
    setColorBlack(this.rootNode);
}

private void remove(RBTreeNode<T> node){
    RBTreeNode<T> child,parent;
    boolean color;
    //被删除节点左右孩子都不为空的情况
    if ((null != node.left) && (null != node.right)){

        //获取到被删除节点的后继节点
        RBTreeNode<T> replace = node;

        replace = replace.right;
        while(null != replace.left){
            replace = replace.left;
        }

        //node节点不是根节点
        if (null != getParent(node)){
            //node是左节点
            if (getParent(node).left == node){
                getParent(node).left = replace;
            } else {
                getParent(node).right = replace;
            }
        } else {
            this.rootNode = replace;
        }

        child = replace.right;
        parent = getParent(replace);
        color = getColor(replace);

        if (parent == node){
            parent = replace;
        } else {
            if (null != child){
                setParent(child,parent);
            }
            parent.left = child;

            replace.right = node.right;
            setParent(node.right, replace);
        }

        replace.parent = node.parent;
        replace.color = node.color;
        replace.left = node.left;
        node.left.parent = replace;
        if (color == COLOR_BLACK){
            removeFixUp(child,parent);
        }

        node = null;
        return;
    }

    if (null != node.left){
        child = node.left;
    } else {
        child = node.right;
    }

    parent = node.parent;
    color = node.color;
    if (null != child){
        child.parent = parent;
    }

    if (null != parent){
        if (parent.left == node){
            parent.left = child;
        } else {
            parent.right = child;
        }
    } else {
        this.rootNode = child;
    }

    if (color == COLOR_BLACK){
        removeFixUp(child, parent);
    }
    node = null;
}

/**
 * 删除修复
 * @param node
 * @param parent
 */
private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent){
    RBTreeNode<T> other;
    //node不为空且为黑色，并且不为根节点
    while ((null == node || isBlack(node)) && (node != this.rootNode) ){
        //node是父节点的左孩子
        if (node == parent.left){
            //获取到其右孩子
            other = parent.right;
            //node节点的兄弟节点是红色
            if (isRed(other)){
                setColorBlack(other);
                setColorRed(parent);
                leftRotate(parent);
                other = parent.right;
            }

            //node节点的兄弟节点是黑色，且兄弟节点的两个孩子节点也是黑色
            if ((other.left == null || isBlack(other.left)) &&
                    (other.right == null || isBlack(other.right))){
                setColorRed(other);
                node = parent;
                parent = getParent(node);
            } else {
                //node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色
                if (null == other.right || isBlack(other.right)){
                    setColorBlack(other.left);
                    setColorRed(other);
                    rightRotate(other);
                    other = parent.right;
                }
                //node节点的兄弟节点是黑色，且兄弟节点的右孩子是红色，左孩子是任意颜色
                setColor(other, getColor(parent));
                setColorBlack(parent);
                setColorBlack(other.right);
                leftRotate(parent);
                node = this.rootNode;
                break;
            }
        } else {
            other = parent.left;
            if (isRed(other)){
                setColorBlack(other);
                setColorRed(parent);
                rightRotate(parent);
                other = parent.left;
            }

            if ((null == other.left || isBlack(other.left)) &&
                    (null == other.right || isBlack(other.right))){
                setColorRed(other);
                node = parent;
                parent = getParent(node);
            } else {
                if (null == other.left || isBlack(other.left)){
                    setColorBlack(other.right);
                    setColorRed(other);
                    leftRotate(other);
                    other = parent.left;
                }

                setColor(other,getColor(parent));
                setColorBlack(parent);
                setColorBlack(other.left);
                rightRotate(parent);
                node = this.rootNode;
                break;
            }
        }
    }
    if (node!=null)
        setColorBlack(node);
}