容易遗忘的红黑树

作为一个被广泛应用的数据结构，我们必须了解红黑树的前世今生。红黑树是一种特殊平衡二叉树，其特殊的定义可以保证比较高效的查找效率。看了很多相关的博客，但是目前还没有完全理解其中删除后的调整策略。而且特别容易遗忘，所以在这里做个笔记，以便以后的学习和复习。

红黑树的特性：

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空 (NIL 或 NULL) 的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

代码：

package data.structure;

import javax.print.attribute.standard.NumberUp;

/***
 * 红黑树特点
 * 1、每个节点不是红色就是黑色的；
 * 2、根节点总是黑色的；
 * 3、所有的叶节点都是是黑色的（红黑树的叶子节点都是空节点（NIL或者NULL））；
 * 4、如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
 * 5、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
 * @param <T>
 */

public class RBTree<T extends Comparable<T>> {

    public RBNode<T> mRoot = null; // 根节点

    public static boolean RED = true;
    public static boolean BLACK = false;

    public class RBNode<T extends Comparable<T>> {
        T key; // 节点中的值
        boolean color; // 颜色
        RBNode<T> parent; // 父节点
        RBNode<T> left; // 左子节点
        RBNode<T> right; // 右自节点

        public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
            this.key = key;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        public T getKey() {
            return key;
        }

        @Override
        public String toString() {
            return "" + "key:" + key + (color == RED ? " R" : " B");
        }
    }

    public RBTree() {
        mRoot = null;
    }

    private RBNode<T> parentOf(RBNode<T> node) {
        return node != null ? node.parent : null;
    }

    private void setParent(RBNode<T> node, RBNode<T> parent) {
        if (node != null) {
            node.parent = parent;
        }
    }

    private boolean colorOf(RBNode<T> node) {
        return node != null ? node.color : BLACK;
    }

    private void setColor(RBNode<T> node, boolean color) {
        if (node != null) {
            node.color = color;
        }
    }

    private boolean isRed(RBNode<T> node) {
        return node != null && node.color == RED;
    }

    private void setRed(RBNode<T> node) {
        if (node != null) {
            node.color = RED;
        }
    }

    private boolean isBlack(RBNode<T> node) {
        return !isRed(node);
    }

    private void setBlack(RBNode<T> node) {
        if (node != null) {
            node.color = BLACK;
        }
    }

    /**
     * 前序遍历RBTree
     */
    public void preOrder() {
        preOrder(mRoot);
    }

    private void preOrder(RBNode<T> tree) {
        if (tree != null) {
            System.out.println(tree.key + " ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    /**
     * 中序遍历RBTree
     */
    public void inOrder() {
        inOrder(mRoot);
    }

    private void inOrder(RBNode<T> tree) {
        if (tree != null) {
            inOrder(tree.left);
            System.out.println(tree.key + " ");
            inOrder(tree.right);
        }
    }

    /**
     * 后序遍历RBTree
     */
    public void postOrder() {
        postOrder(mRoot);
    }

    private void postOrder(RBNode<T> tree) {
        if (tree != null) {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.println(tree.key + " ");
        }
    }

    public RBNode<T> search(T key) {
        return search(mRoot, key);
    }

    /**
     * 查找红黑树（node）中，健值为key的节点 (递归查找)
     *
     * @param node
     * @param key
     * @return
     */
    private RBNode<T> search(RBNode<T> node, T key) {
        if (node == null) {
            return node;
        }

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

    }

    public RBNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

    /**
     * 查找红黑树（node）中，健值为key的节点 (非递归查找)
     *
     * @param node
     * @param key
     * @return
     */
    private RBNode<T> iterativeSearch(RBNode<T> node, T key) {
        while (node != null) {
            int cmp = key.compareTo(node.key);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else {
                return node;
            }
        }
        return node;
    }

    public T minimum() {
        RBNode<T> p = minimum(mRoot);
        if (p != null) {
            return p.key;
        }
        return null;
    }

    /**
     * 查找最小节点： 返回tree为根节点的红黑树的最小节点
     *
     * @param tree
     * @return
     */
    private RBNode<T> minimum(RBNode<T> tree) {
        if (tree == null) {
            return tree;
        }

        while (tree.left != null) {
            tree = tree.left;
        }
        return tree;
    }

    public T maximum() {
        RBNode<T> p = maximum(mRoot);
        if (p != null) {
            return p.key;
        }
        return null;
    }

    /**
     * 查找最大节点： 返回tree为更节点的红黑树的最大节点
     *
     * @param tree
     * @return
     */
    private RBNode<T> maximum(RBNode<T> tree) {
        if (tree == null) {
            return tree;
        }

        while (tree.right != null) {
            tree = tree.right;
        }
        return tree;
    }

    /**
     * 查找节点x的后继节点。即，查找红黑树中数值大于x的最小节点
     *
     * @param x
     * @return
     */
    public RBNode<T> successor(RBNode<T> x) {
        // 如果x的右子节点存在，则"x的后继节点"为以x右节点为根节点的最小节点
        if (x.right != null) {
            return minimum(x.right);
        }

        // 如果x的右子节点不存在，则x有2中可能：
        // 1：x为左节点，那么x的后继节点为x的父节点；
        // 2：x为右节点，那么x的后继节点为x祖父节点，并且x的父节点为祖父节点的左子节点；否则x不存在后继节点；
        RBNode<T> y = x.parent;
        while ((y != null) && x == y.right) {
            x = y;
            y = y.parent;
        }
        return y;
    }

    /**
     * 查找节点x的前驱节点。即，查找红黑树中数据值小于该节点的最大节点
     *
     * @param x
     * @return
     */
    public RBNode<T> predecessor(RBNode<T> x) {
        // 若x的左子节点存在，那么x的前驱节点为以x左子节点为根节点的最大子节点
        if (x.left != null) {
            return maximum(x.left);
        }

        // 如果x的左子节点不存在，则x有2中可能：
        // 1： x为左节点，
        // 2： x为右节点，那么x的前驱节点为x的父节点；
        RBNode<T> y = x.parent;
        while ((y != null) && x == y.left) {
            x = y;
            y = y.parent;
        }
        return y;
    }

    /*************对红黑树节点x进行左旋操作 ******************/
    /*
     * 左旋示意图：对节点x进行左旋
     *     p                       p
     *    /                       /
     *   x                       y
     *  / \                     / \
     * lx  y      ----->       x  ry
     *    / \                 / \
     *   ly ry               lx ly
     * 左旋做了三件事：
     * 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
     * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
     * 3. 将y的左子节点设为x，将x的父节点设为y
     */
    public void leftRotate(RBNode<T> x) {
        if (x == null) {
            return;
        }
        // 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
        RBNode<T> y = x.right;
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }

        // 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
        y.parent = x.parent;
        if (x.parent == null) {
            this.mRoot = y;
        } else {
            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        }

        // 3. 将y的左子节点设为x，将x的父节点设为y
        y.left = x;
        x.parent = y;
    }

    /*************对红黑树节点y进行右旋操作 ******************/
    /*
     * 右旋示意图：对节点y进行右旋
     *        p                   p
     *       /                   /
     *      y                   x
     *     / \                 / \
     *    x  ry   ----->      lx  y
     *   / \                     / \
     * lx  rx                   rx ry
     * 右旋做了三件事：
     * 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
     * 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
     * 3. 将x的右子节点设为y，将y的父节点设为x
     */
    public void rightRotate(RBNode<T> x) {
        if (x == null) {
            return;
        }

        RBNode<T> y = x.left;
        x.left = y.right;
        if (y.right != null) {
            y.right.parent = x;
        }

        y.parent = x.parent;
        if (x.parent == null) {
            this.mRoot = y;
        } else {
            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        }

        y.right = x;
        x.parent = y;
    }

    /*********************** 向红黑树中插入节点 **********************/
    public void insert(T data) {
        RBNode<T> node = new RBNode<>(data, BLACK, null, null, null);
        if (node != null) {
            insert(node);
        }
    }

    /**
     * 1、将节点插入到红黑树中，这个过程与二叉搜索树是一样的
     * 2、将插入的节点着色为"红色"；将插入的节点着色为红色，不会违背"特性5"！
     * 少违背了一条特性，意味着我们需要处理的情况越少。
     * 3、通过一系列的旋转或者着色等操作，使之重新成为一颗红黑树。
     *
     * @param node 插入的节点
     */
    public void insert(RBNode<T> node) {
        int cmp;
        // 假设current 为 node 的父节点
        RBNode<T> current = null;
        RBNode<T> x = mRoot;

        while (x != null) {
            current = x;
            cmp = node.key.compareTo(x.key);
            if (cmp < 0) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        // 找到了node需要插入的位置，将当前current作为node的父节点
        node.parent = current;
        // 判断node是插在左子节点还是右子节点
        if (current != null) {
            cmp = node.key.compareTo(current.key);
            if (cmp < 0) {
                current.left = node;
            } else {
                current.right = node;
            }
        } else {
            this.mRoot = node;
        }

        // 将node标记为红色
        node.color = RED;
        insertFixUp(node);
    }

    private void insertFixUp(RBNode<T> node) {
        RBNode<T> parent, gparent;
        //需要修整的条件：父节点存在，且父节点的颜色是红色
        while ((parent = parentOf(node)) != null && isRed(parent)) {
            // 祖父节点
            gparent = parentOf(parent);

            // 若父节点是祖父节点的左子节点
            if (parent == gparent.left) {
                // 获取叔叔节点，叔叔节点为祖父节点的右子节点
                RBNode<T> uncle = gparent.right;
                // case1: 叔叔节点是红色
                if ((uncle != null) && isRed(uncle)) {
                    // 将父节点和叔叔节点都染成黑色
                    setBlack(uncle);
                    setBlack(parent);
                    // 则祖父节点必须染成红色
                    setRed(gparent);
                    // 将位置放在祖父节点
                    node = gparent;
                    // 为了满足特性5，继续向上循环染色
                    continue;
                }

                // case2: 叔叔节点是黑色，且当前需要插入的节点为有右子节点
                // 将父节点进行左旋，调换父节点与子节点的位置，在按照 case3 继续调整
                if (node == parent.right) {
                    // 从父节点处 左旋
                    leftRotate(parent);
                    // 将父节点和自己调换位置，为右旋准备
                    RBNode<T> tmp = parent;
                    parent = node;
                    node = tmp;
                }

                // case3：叔叔节点为黑色，切当前需要插入的节点为左自节点
                // a.先父节点染成黑色； b.将祖父节点染成红色；c.将父节点进行右旋
                setBlack(parent);
                setRed(gparent);
                rightRotate(gparent);
            } else {
                // 若父节点为祖父节点的右自节点
                RBNode<T> uncle = gparent.left;
                // case1: 叔叔节点也是红色节点
                if (uncle != null && isRed(uncle)) {
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(gparent);
                    node = gparent;
                    continue;
                }

                // case2: 叔叔节点为黑色，当前要插入的节点为父节点的左子节点
                // 将父节点进行右旋
                if (node == parent.left) {
                    rightRotate(parent);
                    RBNode<T> tmp = parent;
                    parent = node;
                    node = tmp;
                }

                // case3: 叔叔节点为黑色，且当前要插入的节点为父节点的右子节点
                setBlack(parent);
                setRed(gparent);
                leftRotate(gparent);
            }
        }
        //将根节点设置为黑色
        setBlack(this.mRoot);
    }


    public void remove(T key) {
        RBNode<T> node;
        if ((node = search(mRoot, key)) != null) {
            remove(node);
        }
    }

    /**
     * 1、被删除的节点没有儿子，即删除的是叶子节点。那么，直接删除该节点。
     * 2、被删除的节点只有一个儿子。那么直接删除该节点，并用该节点的唯一子节点顶替它的初始位置。
     * 3、被删除的节点有两个儿子。那么先找出它的后继节点（右孩子中的最小的(最左子节点)，该孩子没有子节点或者只有一右孩子）。
     * 然后把"它的后继节点的内容"复制给"该节点的内容"；之后，删除"它的后继节点"。
     * 在这里后继节点相当与替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。
     * ------这样问题就转化为怎么删除后继即节点的问题？
     * 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子都非空。
     * 注：后继节点为补充被删除的节点；
     * 即：意味着"要么没有儿子，要么只有一个儿子"。
     * 若没有儿子，则回归到（1）。
     * 若只有一个儿子，则回归到（2）。
     *
     * @param node 需要删除的节点
     */
    public void remove(RBNode<T> node) {
        RBNode<T> child, parent;
        boolean color;

        // case1: 需要删除的节点的左右子节点都不为空
        if (node.left != null && node.right != null) {
            RBNode<T> replace = node;

            // a: 获取后继节点，右孩子中最小（需要被删除节点右子节点中的最左子节点）
            replace = replace.right;
            while (replace.left != null) {
                replace = replace.left;
            }

            // b: 处理【后继节点的子节点】和【被删除节点的子节点】之间的关系
            //    将后继节点的位置转换至被删除节点
            if (parentOf(node) != null) {
                // 要删除的不是根节点
                if (node == parentOf(node).left) {
                    // 此时 replace 的父节点还是原来的父节点，因为还没有指定replace.parent = node.parent.
                    parentOf(node).left = replace;
                } else {
                    parentOf(node).right = replace;
                }
            } else {
                mRoot = replace;
            }

            //c: 处理【后继节点的子节点】和【被删除节点的子节点】之间的关系
            //后继节点肯定不存在左子节点
            child = replace.right;
            parent = parentOf(replace);
            color = colorOf(replace);
            if (parent == node) {
                // 如果replace 为删除节点的唯一右节点，则replace直接替换node 的位置
                parent = replace;
            } else {
                if (child != null) {
                    // 如果replace 还有右子节点，则直接更换为replace原来 父节点子节点
                    child.parent = parent;
                }
                parent.left = child;
                // 将node原来的所有关系都复制给replace
                replace.right = node.right;
                setParent(node.right, replace);
            }
            replace.parent = node.parent;
            replace.color = node.color;
            replace.left = node.left;

            // 如果被删除的节点颜色为黑色，则需要调整
            if (color == BLACK) {
                removeFixUp(child, parent);
            }
            node = null;
        } else {
            //被删除的节点是叶子节点
            // a.被删除的节点没有儿子，即删除的是叶子节点。那么，直接删除该节点
            // b.被删除的节点只有一个孩子, 那么直接删除该节点，并用该节点的唯一子节点顶替它的初始位置。
            if (node.left != null) {
                child = node.left;
            } else {
                child = node.right;
            }
            parent = node.parent;
            color = node.color;
            if (child != null) {
                child.parent = parent;
            }

            if (parent != null) {
                if (parent.left == node) {
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            } else {
                // 如果删除的节点是根节点
                mRoot = child;
            }

            // 如果被删除的节点颜色为黑色，则需要调整
            if (color == BLACK) {
                removeFixUp(child, parent);
            }
            node = null;
        }

    }

    /**
     * 红黑树删除修正函数
     * <p>
     * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
     * 目的是将它重新塑造成一颗红黑树。
     * 如果当前待删除节点是红色的，它被删除之后对当前树的特性不会造成任何破坏影响。
     * 而如果被删除的节点是黑色的，这就需要进行进一步的调整来保证后续的树结构满足要求。
     * 这里我们只修正删除的节点是黑色的情况：
     * <p>
     * 调整思想：
     * 为了保证删除节点的父节点左右两边黑色节点数一致，需要重点关注父节点没删除的那一边节点是不是黑色。
     * 如果删除后父亲节点另一边比删除的一边黑色多，就要想办法搞到平衡。
     * 1、把父亲节点另一边（即删除节点的兄弟树）其中一个节点弄成红色，也少了一个黑色。
     * 2、或者把另一边多的节点（染成黑色）转过来一个
     * <p>
     * 1）、当前节点是黑色的，且兄弟节点是红色的（那么父节点和兄弟节点的子节点肯定是黑色的）；
     * x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
     * 处理策略:
     * (01) 将x的兄弟节点设为“黑色”;
     * (02) 将x的父节点设为“红色”;
     * (03) 对x的父节点进行左旋;
     * (04) 左旋后，重新设置x的兄弟节点。
     * 这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”，从而进行进一步的处理。
     * 对x的父节点进行左旋；左旋后，为了保持红黑树特性，就需要在左旋前“将x的兄弟节点设为黑色”，
     * 同时“将x的父节点设为红色”；左旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。
     * <p>
     * 2）、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的两个子节点均为黑色的；
     * x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
     * 处理策略:
     * (01) 将x的兄弟节点设为“红色”;
     * (02) 设置“x的父节点”为“新的x节点”。
     * 这个情况的处理思想：是将“x中多余的一个黑色属性上移(往根方向移动)”。
     * x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，
     * 即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先时“红”，则此时变成了“红+黑”)。
     * 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；
     * 但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！
     * 为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，
     * 那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
     * <p>
     * 经过上面的步骤(将x的兄弟节点设为红色)，多余的一个颜色属性(黑色)已经跑到x的父节点中。
     * 我们需要将x的父节点设为“新的x节点”进行处理。
     * 若“新的x节点”是“黑+红”，直接将“新的x节点”设为黑色，即可完全解决该问题；
     * 若“新的x节点”是“黑+黑”，则需要对“新的x节点”进行进一步处理。
     * <p>
     * 3）、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的左子节点是红色，右子节点时黑色的；
     * x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的
     * 处理策略:
     * (01) 将x兄弟节点的左孩子设为“黑色”;
     * (02) 将x兄弟节点设为“红色”;
     * (03) 对x的兄弟节点进行右旋;
     * (04) 右旋后，重新设置x的兄弟节点。
     * 我们处理“Case 3”的目的是为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理。
     * 转换的方式是对x的兄弟节点进行右旋；为了保证右旋后，它仍然是红黑树，就需要在右旋前“将x的兄弟节点的左孩子设为黑色”，
     * 同时“将x的兄弟节点设为红色”；右旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理.
     * <p>
     * 4）、当前节点是黑色的，且兄弟节点是黑色的，且兄弟节点的右子节点是红色，左子节点任意颜色。
     * x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色
     * 处理策略:
     * (01) 将x父节点颜色 赋值给 x的兄弟节点;
     * (02) 将x父节点设为“黑色”;
     * (03) 将x兄弟节点的右子节设为“黑色”;
     * (04) 对x的父节点进行左旋;
     * (05) 设置“x”为“根节点”.
     * 我们处理“Case 4”的目的是：去掉x中额外的黑色，将x变成单独的黑色。
     * 处理的方式是“：进行颜色修改，然后对x的父节点进行左旋。下面，我们来分析是如何实现的。
     * 为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，
     * “兄弟节点的左孩子”为BLS(Brother's Left Son)，“兄弟节点的右孩子”为BRS(Brother's Right Son)，
     * “父节点”为F(Father)。
     * 我们要对F进行左旋。但在左旋前，我们需要调换F和B的颜色，并设置BRS为黑色。为什么需要这里处理呢？
     * 因为左旋后，F和BLS是父子关系，而我们已知BL是红色，如果F是红色，则违背了“特性(4)”；
     * 为了解决这一问题，我们将“F设置为黑色”。 但是，F设置为黑色之后，为了保证满足“特性(5)”，即为了保证左旋之后：
     * 第一，“同时经过根节点和S的分支的黑色节点个数不变”。
     * 若满足“第一”，只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”，而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1；
     * 现在，只需将S由“黑+黑”变成单独的“黑”节点，即可满足“第一”。
     * 第二，“同时经过根节点和BLS的分支的黑色节点数不变”。
     * 若满足“第二”，只需要将“F的原始颜色”赋值给B即可。之前，我们已经将“F设置为黑色”(即，将B的颜色"黑色"，赋值给了F)。
     * 至此，我们算是调换了F和B的颜色。
     * 第三，“同时经过根节点和BRS的分支的黑色节点数不变”。
     * 在“第二”已经满足的情况下，若要满足“第三”，只需要将BRS设置为“黑色”即可。
     * 经过，上面的处理之后。红黑树的特性全部得到的满足！接着，我们将x设为根节点，就可以跳出while循环(参考伪代码)；即完成了全部处理。
     * <p>
     * 至此，我们就完成了Case 4的处理。理解Case 4的核心，是了解如何“去掉当前节点额外的黑色”。
     * <p>
     * 以上四种情况中，2，3，4都是（当前节点是黑色的，且兄弟节点是黑色的）的子集。
     * <p>
     * 参数说明：
     *
     * @param node   删除之后代替的节点（后序节点）
     * @param parent 后序节点的父节点
     */
    private void removeFixUp(RBNode<T> node, RBNode<T> parent) {
        RBNode<T> other;

        while ((node == null || isBlack(node)) && (node != mRoot)) {
            if (parent.left == node) {
                other = parent.right;
                if (isRed(other)) {
                    // case 1:
                    setBlack(other);
                    setRed(parent);
                    leftRotate(parent);
                    other = parent.right;
                }

                if ((other.left == null || isBlack(other.left))
                        && ((other.right == null) || isBlack(other.right))) {
                    // case 2:
                    setRed(other);
                    node = parent;
                    parent = parentOf(node);
                } else {
                    if (other.right == null || isBlack(other.right)) {
                        // case 3:
                        setBlack(other.left);
                        setRed(other);
                        rightRotate(other);
                        other = parent.right;
                    }
                    // case 4:
                    setColor(other, colorOf(parent));
                    setBlack(parent);
                    setBlack(other.right);
                    leftRotate(parent);
                    node = mRoot;
                    break;
                }

            } else {
                other = parent.left;
                if (isRed(other)) {
                    // case 1:
                    setBlack(other);
                    setRed(parent);
                    rightRotate(parent);
                    other = parent.left;
                }

                if ((other.left == null || isBlack(other.left))
                        && (other.right == null || isBlack(other.right))) {
                    // case 2:
                    setRed(other);
                    node = parent;
                    parent = parentOf(node);
                } else {
                    if (other.left == null || isBlack(other.left)) {
                        // case 3:
                        setBlack(other.right);
                        setRed(other);
                        leftRotate(other);
                        other = parent.left;
                    }

                    // case 4:
                    setColor(other, colorOf(parent));
                    setBlack(parent);
                    setBlack(other.left);
                    rightRotate(parent);
                    node = mRoot;
                    break;
                }
            }
        }
        if (node != null) {
            setBlack(node);
        }
    }

    public void clear() {
        destory(mRoot);
        mRoot = null;
    }

    /**
     * 销毁红黑树
     *
     * @param tree
     */
    private void destory(RBNode<T> tree) {
        if (tree == null) {
            return;
        }

        if (tree.left != null) {
            destory(tree.left);
        }
        if (tree.right != null) {
            destory(tree.right);
        }

        tree = null;
    }

    /*
     * 打印"红黑树"
     *
     * key        -- 节点的键值
     * direction  --  0，表示该节点是根节点;
     *               -1，表示该节点是它的父结点的左孩子;
     *                1，表示该节点是它的父结点的右孩子。
     */
    private void print(RBNode<T> tree, T key, int direction) {
        if (tree != null) {
            if (direction == 0) { // tree是根节点
                System.out.printf("%2d(B) is root\n", tree.key);
            } else {// tree是分支节点
                System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree) ? "R" : "B", key, direction == 1 ? "right" : "left");
            }
            print(tree.left, tree.key, -1);
            print(tree.right, tree.key, 1);
        }
    }

    public void print() {
        if (mRoot != null) {
            print(mRoot, mRoot.key, 0);
        }
    }
}

测试代码：

package data.structure;

public class RBTreeTest {

    private static final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
    private static final boolean mDebugInsert = true;    // "插入"动作的检测开关(false，关闭；true，打开)
    private static final boolean mDebugDelete = true;    // "删除"动作的检测开关(false，关闭；true，打开)

    public static void main(String[] args) {
        int i, ilen = a.length;
        RBTree<Integer> tree=new RBTree<Integer>();

        System.out.printf("== 原始数据: ");
        for(i=0; i<ilen; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        for(i=0; i<ilen; i++) {
            tree.insert(a[i]);
            // 设置mDebugInsert=true,测试"添加函数"
            if (mDebugInsert) {
                System.out.printf("== 添加节点: %d\n", a[i]);
                System.out.printf("== 树的详细信息: \n");
                tree.print();
                System.out.printf("\n");
            }
        }

        System.out.printf("== 前序遍历: ");
        tree.preOrder();

        System.out.printf("\n== 中序遍历: ");
        tree.inOrder();

        System.out.printf("\n== 后序遍历: ");
        tree.postOrder();
        System.out.printf("\n");

        System.out.printf("== 最小值: %s\n", tree.minimum());
        System.out.printf("== 最大值: %s\n", tree.maximum());
        System.out.printf("== 树的详细信息: \n");
        tree.print();
        System.out.printf("\n");

        // 设置mDebugDelete=true,测试"删除函数"
        if (mDebugDelete) {
            for(i=0; i<ilen; i++)
            {
                tree.remove(a[i]);

                System.out.printf("== 删除节点: %d\n", a[i]);
                System.out.printf("== 树的详细信息: \n");
                tree.print();
                System.out.printf("\n");
            }
        }

        // 销毁二叉树
        tree.clear();
    }
}

Output：

== 原始数据: 10 40 30 60 90 70 20 50 80 
== 添加节点: 10
== 树的详细信息: 
10(B) is root

== 添加节点: 40
== 树的详细信息: 
10(B) is root
40(R) is 10's  right child

== 添加节点: 30
== 树的详细信息: 
30(B) is root
10(R) is 30's   left child
40(R) is 30's  right child

== 添加节点: 60
== 树的详细信息: 
30(B) is root
10(B) is 30's   left child
40(B) is 30's  right child
60(R) is 40's  right child

== 添加节点: 90
== 树的详细信息: 
30(B) is root
10(B) is 30's   left child
60(B) is 30's  right child
40(R) is 60's   left child
90(R) is 60's  right child

== 添加节点: 70
== 树的详细信息: 
30(B) is root
10(B) is 30's   left child
60(R) is 30's  right child
40(B) is 60's   left child
90(B) is 60's  right child
70(R) is 90's   left child

== 添加节点: 20
== 树的详细信息: 
30(B) is root
10(B) is 30's   left child
20(R) is 10's  right child
60(R) is 30's  right child
40(B) is 60's   left child
90(B) is 60's  right child
70(R) is 90's   left child

== 添加节点: 50
== 树的详细信息: 
30(B) is root
10(B) is 30's   left child
20(R) is 10's  right child
60(R) is 30's  right child
40(B) is 60's   left child
50(R) is 40's  right child
90(B) is 60's  right child
70(R) is 90's   left child

== 添加节点: 80
== 树的详细信息: 
30(B) is root
10(B) is 30's   left child
20(R) is 10's  right child
60(R) is 30's  right child
40(B) is 60's   left child
50(R) is 40's  right child
80(B) is 60's  right child
70(R) is 80's   left child
90(R) is 80's  right child

== 前序遍历: 30 
10 
20 
60 
40 
50 
80 
70 
90 

== 中序遍历: 10 
20 
30 
40 
50 
60 
70 
80 
90 

== 后序遍历: 20 
10 
50 
40 
70 
90 
80 
60 
30 

== 最小值: 10
== 最大值: 90
== 树的详细信息: 
30(B) is root
10(B) is 30's   left child
20(R) is 10's  right child
60(R) is 30's  right child
40(B) is 60's   left child
50(R) is 40's  right child
80(B) is 60's  right child
70(R) is 80's   left child
90(R) is 80's  right child

== 删除节点: 10
== 树的详细信息: 
30(B) is root
20(B) is 30's   left child
60(R) is 30's  right child
40(B) is 60's   left child
50(R) is 40's  right child
80(B) is 60's  right child
70(R) is 80's   left child
90(R) is 80's  right child

== 删除节点: 40
== 树的详细信息: 
30(B) is root
20(B) is 30's   left child
60(R) is 30's  right child
50(B) is 60's   left child
80(B) is 60's  right child
70(R) is 80's   left child
90(R) is 80's  right child

== 删除节点: 30
== 树的详细信息: 
50(B) is root
20(B) is 50's   left child
80(R) is 50's  right child
60(B) is 80's   left child
70(R) is 60's  right child
90(B) is 80's  right child

== 删除节点: 60
== 树的详细信息: 
50(B) is root
20(B) is 50's   left child
80(R) is 50's  right child
70(B) is 80's   left child
90(B) is 80's  right child

== 删除节点: 90
== 树的详细信息: 
50(B) is root
20(B) is 50's   left child
80(B) is 50's  right child
70(R) is 80's   left child

== 删除节点: 70
== 树的详细信息: 
50(B) is root
20(B) is 50's   left child
80(B) is 50's  right child

== 删除节点: 20
== 树的详细信息: 
60(B) is root
30(B) is 60's   left child
70(B) is 60's  right child

== 删除节点: 50
== 树的详细信息: 
60(B) is root
30(B) is 60's   left child
70(B) is 60's  right child

== 删除节点: 80
== 树的详细信息: 
60(B) is root
30(B) is 60's   left child
70(B) is 60's  right child

引用：

1. 红黑树 (一) 之 原理和算法详细介绍
2. 寻找红黑树的操作手册
3. 二叉树知识点回忆以及整理
4. 教你初步了解红黑树