8分钟，复习一遍红黑树！

作者: java的小粉丝 | 来源:发表于2022-08-30 15:16 被阅读0次

数据结构—树—红黑树
TreeMap
图解红黑树插入
数据结构与算法-AVL 红黑树
[转载]红黑树
拿下红黑树
红黑树
彻底理解红黑树（二）之插入
彻底理解红黑树（三）之删除
Golang红黑树

image.png

简单介绍

什么是红黑树？

红黑树（Red Black Tree）是一种平衡二叉搜索树。红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

为什么使用红黑树？

红黑树相比AVL树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。
其次红黑树不像AVL树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，AVL树调平衡有时候代价较大，所以效率不如红黑树。红黑树只是做到了近似平衡，并不严格的平衡，所以在维护的成本上，要比AVL树要低。
红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上却好很多。
红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

红黑树的前身 234树（4阶B树）

它的效率不如红黑树
234树：是一种多叉树，它的每个节点最多有3个数据项和四个子节点。
节点分为3类：

2节点：存储1个数据项，2个子节点

image.png

3节点：存储2个数据项，3个子节点

image.png

4节点：存储3个数据项，4个子节点

image.png

插入操作
我们将1~10依次插入到234树中，观察如何平衡调整。

首先是1~3的插入，插完以后已经变成一个4节点了。

image.png

接着我们插入4，但是234树最多就是4节点，不能直接接在后面了。我们需要进行一步节点上溢操作。上溢中间的节点2，形成一个新的二节点，然后4就接在3后面。接着插入5就直接接在4后面形成4节点了。

image.png

接着插入6，由于不能超过4节点又要进行节点上溢了，这里4上溢，然后形成的新树和2要进行合并。

image.png

同理插入到8的时候也一样。

image.png
最后插入10的时候，将8进行上溢。

image.png

上溢并合并以后发现一久大于4节点，于是再将4进行上溢。

image.png

最终我们的234树为

image.png

234树与红黑树的关联

左边是一棵红黑树，我们将红色节点上移到和他们的父节点同一高度上，实际上就是一棵234树。

image.png

所以红黑树和234树是具有等价性的。
红黑树的黑色节点个数=234树的节点数
234树的每一个节点中：
黑色节点必为父节点，红色节点为子节点（黑色中间，红色两边）
那么红黑树的每一种插入情况我们都可以转换为234树来理解。

23树

根据234树的逻辑我们可以完美套用到23树上，只需要知道234树最大是4节点，23树最大是3节点就行了。

红黑树的性质

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉搜索树的基础上，对于任何有效的红黑树有如下性质:

性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色，且都为空。
性质4. 每个红色结点的父节点 and 子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

234树思维理解红黑树的操作

下面我们采用234树来辅助理解红黑树的插入操作和删除操作。

红黑树的插入操作

如果插入的是根节点，则为黑色。
其余情况插入的节点最开始一定为红色。（如果插入红色节点，仅有一种冲突状况，就是可能出现连续两个红色节点，这时候只需要旋转和变色进行调整。）
红黑树的插入操作分为12种情况：

插入节点的父节点为黑色（4种）：直接插入，不做调整。因为不会影响到它红黑树的性质。

image.png

叔父节点不是红色（4种）：变色+旋转。

image.png

对于（6)RR型以234树的思维进行构想，我们会把13加在12的后面，但是红黑树不能有两个一样的红节点，所以我们需要进行变色，将中间的12变成黑色，两边的节点变成红色。

image.png
光变色还是不行的，因为黑色节点必须是父节点。我们得进行一次左旋操作。

image.png

对于（7)LL型同理上面的RR型，直接染色加右旋即可。

对于（5）RL型我们实际上希望11是在10和12中间的，这样的话一次旋转操作是不够的，需要做两次旋转。

image.png

首先插入节点染成黑色，然后插入节点的祖父节点也就是10染成红色。

image.png

染色到此为止，接下来是旋转操作首先是父节点12进行一次右旋

image.png

然后祖父节点10进行一次左旋。最终到了下图所示的状态，这个是满足红黑树的性质的。

image.png

对于（8)LR型和上面的RL型同理，染色然后对父节点进行一次左旋，然后对祖父节点进行一次右旋。

叔父节点是红色（4种上溢）：变色。

image.png

我们依旧用234树的思维来理解，这里无论是哪种情况都是肯定需要上溢的（将4抬高)

image.png
然后开始染色，将插入节点的父节点和叔父节点染成黑色。上溢节点4作为新节点染成红色插入到上面一层。

image.png

接着由于上溢节点在逻辑上是新插入到上一层的，于是依旧需要再用上面的方式再处理一次4这个节点。从整体上来看就是一种递归的形式。
其他的情况实际上都是一样的，首先将父节点和叔父节点染黑，将祖父节点染红，祖父作为新插入节点上溢，然后递归处理。（写代码的时候需要将4种情况写明，毕竟位置不同。）
红黑树的删除操作

什么是下溢？

讲删除之前首先还是讲下溢，上溢情况我们知道是超过了4节点了需要把中间节点抬高。下溢则是原来是一个2||3||4节点，但是删除掉下面一层的节点后子节点数目和2||3||4节点需要的数目对不上了。
讲完下溢之后我们开始正式讲删除操作

红黑树的删除操作比较复杂，分支很多，耐心看还是有收获的。

对于非叶子节点是转换为其前驱/后继节点的删除：

image.png

我们删除8这个节点。前驱节点就是6，后继节点就是10。我们这里选择前驱节点，进行交换操作，然后删除。

image.png
所以对应红黑树来说，删除操作最后都是对应红黑树最后两行的删除。
删除实际上分成两类

红色节点可以直接删除（删除最后一层的节点对红黑树性质没有影响）

黑色节点的删除

有2个红色子节点的黑色节点（会转化成对子节点的删除，不作考虑）

有1个红色子节点的黑色节点
我们这里删除10这个节点

image.png

用唯一的红色子节点12来代替被删除的节点10，然后删除掉节点10，最后将替代的红色节点12染成黑色。

image.png
总结步骤：替代，删除，将替代节点染黑。

黑色叶子节点（下溢的情况）

删除节点为根节点，直接删除

删除节点的兄弟节点为黑色

兄弟节点有红色子节点（借用兄弟子节点修复）
（1）当要删除的节点的兄弟节点有一个左子节点。
对于这个红黑树我们删除36，它的兄弟就是20，然后有一个红色左子节点18。

image.png

我们首先删除36，第一层本来就是4节点了，而删完后下面指向的数据项只有3个了，少了一个。所以我们需要通过旋转和变色来补上空缺的这个数据项。

image.png
我们对删除节点的父节点25进行一次右旋，然后进行染色，将父节点染成红色，子节点染成黑色，这样才能保持性质。

image.png
最后来看实际是当时被删除节点父节点25来替代了被删除节点的位置。

image.png

（2）当要删除的节点的兄弟节点有一个右子节点。

对于这个红黑树我们删除36，它的兄弟就是20，然后有一个红色右子节点22。

image.png

和上面同理，我们对被删除节点的兄弟节点进行左旋，然后对父节点进行右旋，最后进行染色，父染红，子染黑。

image.png
（3）当要删除的节点的兄弟节点有一个左子节点和一个右子节点。

对于这个红黑树我们删除36，它的兄弟就是20，然后有一个红色左子节点18和一个红色右子节点22。

image.png

这种我们可以自行选择左子节点或者右子节点进行修复。
总结的话步骤就是：
1.在删除节点后进行旋转
2.中心节点染成父节点颜色
3.两个子节点染为黑色

兄弟节点没有红色子节点（兄弟节点无节点可借出，父节点向下合并）
（1）父节点是红色
对于下面的树，我们删除36这个节点。有一个红色父节点25，兄弟节点20无红色子节点。

image.png

删除掉36后，第一层一样出现了下溢的情况。修复需要父节点25向下合并，与被删除节点的兄弟节点形成一个3节点。

image.png
染色的话将父节点25染成黑色，将之前的兄弟节点20染成红色。修复就完成了。

image.png
（2）父节点是黑色

对于下面的树，我们删除36，父节点25为黑色，兄弟节点无红色子节点。

image.png

这个时候我们删除后处理下溢再染色会变成这样，25的父节点又出现下溢了。于是我们把这个父节点当作一个被删除的节点进行一个递归的操作。

image.png

删除节点的兄弟节点为红色（转变为黑色处理）

删除节点36，兄弟节点20为红色。

image.png

对被删除节点36的父节点25进行一次右旋，然后将被删除节点的兄弟节点20染成黑色，将父节点25染成红色。

image.png
总结就是：父节点右旋，兄弟节点染黑，父节点染红，然后使用兄弟为黑色的方法进行修复。

红黑树的编码

红黑树节点定义

/**
     * 红黑树节点定义
     *
     * @author pixel-revolve
     * @date 2022/08/28
     */
public static class RBTNode<T extends Comparable<T>> {
    boolean color;        // 颜色
    T key;                // 关键字(键值)
    RBTNode<T> left;    // 左孩子
    RBTNode<T> right;    // 右孩子
    RBTNode<T> parent;    // 父结点

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

    public T getKey() {
        return key;
    }

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

旋转操作

左旋

/**
     * 对红黑树的节点(x)进行左旋转
     *
     * 左旋示意图(对节点x进行左旋)：
     *      px                              px
     *     /                               /
     *    x                               y
     *   /  \      --(左旋)-.           / \                #
     *  lx   y                          x  ry
     *     /   \                       /  \
     *    ly   ry                     lx  ly
     *
     *
     */
private void leftRotate(RBTNode<T> x) {
    // 设置x的右孩子为y
    RBTNode<T> y = x.right;

    // 将 “y的左孩子” 设为 “x的右孩子”；
    // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
    x.right = y.left;
    if (y.left != null)
        y.left.parent = x;

    // 将 “x的父亲” 设为 “y的父亲”
    y.parent = x.parent;

    if (x.parent == null) {
        this.mRoot = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点
    } else {
        if (x.parent.left == x)
            x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
        else
            x.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
    }

    // 将 “x” 设为 “y的左孩子”
    y.left = x;
    // 将 “x的父节点” 设为 “y”
    x.parent = y;
}

右旋

/**
 * 对红黑树的节点(y)进行右旋转
 *
 * 右旋示意图(对节点y进行左旋)：
 *            py                               py
 *           /                                /
 *          y                                x
 *         /  \      --(右旋)-.            /  \                     #
 *        x   ry                           lx   y
 *       / \                                   / \                   #
 *      lx  rx                                rx  ry
 *
 */
private void rightRotate(RBTNode<T> y) {
    // 设置x是当前节点的左孩子。
    RBTNode<T> x = y.left;

    // 将 “x的右孩子” 设为 “y的左孩子”；
    // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
    y.left = x.right;
    if (x.right != null)
        x.right.parent = y;

    // 将 “y的父亲” 设为 “x的父亲”
    x.parent = y.parent;

    if (y.parent == null) {
        this.mRoot = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
    } else {
        if (y == y.parent.right)
            y.parent.right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
        else
            y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
    }

    // 将 “y” 设为 “x的右孩子”
    x.right = y;

    // 将 “y的父节点” 设为 “x”
    y.parent = x;
}

插入操作
看着很多，但是我做了很多的注释，配合上面的图看理解不难。

/**
     * 红黑树插入修正函数
     *
     * 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
     * 目的是将它重新塑造成一颗红黑树。
     *
     * 参数说明：
     *     node 插入的结点        // 对应《算法导论》中的z
     */
private void insertFixUp(RBTNode<T> node) {
    RBTNode<T> parent, gparent;
    // 若“父节点存在，并且父节点的颜色是黑色”
    // 不做任何调整

    // 若“父节点存在，并且父节点的颜色是红色”
    while (((parent = parentOf(node))!=null) && isRed(parent)) {
        gparent = parentOf(parent);

        //若“父节点”是“祖父节点的左孩子”
        if (parent == gparent.left) {
            // Case 1条件：叔叔节点是红色 我们直接变色处理就行
            RBTNode<T> uncle = gparent.right;
            if ((uncle!=null) && isRed(uncle)) {
                setBlack(uncle);
                setBlack(parent);
                setRed(gparent);
                node = gparent;
                continue;
            }

            // 到这里，叔父节点是黑色，我们分成功左右孩讨论
            // Case 2条件：叔叔是黑色，且当前节点是右孩子
            if (parent.right == node) {
                RBTNode<T> tmp;
                leftRotate(parent);
                // parent和插入节点进行变量逻辑交换
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // Case 3条件：叔叔是黑色，且当前节点是左孩子。
            setBlack(parent);// 将插入节点现在是parent的位置，染成黑色
            setRed(gparent);// 将插入节点的祖父节点（位置没变）染成红色
            rightRotate(gparent); // 完成第二次旋转，对于RR和LL型，此次旋转无效
        } else {    //若“z的父节点”是“z的祖父节点的右孩子”
            // Case 1条件：叔叔节点是红色，直接染色处理
            RBTNode<T> uncle = gparent.left;
            if ((uncle!=null) && isRed(uncle)) {
                setBlack(uncle);
                setBlack(parent);
                setRed(gparent);
                node = gparent;
                continue;
            }

            // Case 2条件：叔叔是黑色，且当前节点是左孩子
            if (parent.left == node) {
                RBTNode<T> tmp;
                rightRotate(parent);
                tmp = parent;
                parent = node;
                node = tmp;
            }

            // Case 3条件：叔叔是黑色，且当前节点是右孩子。
            setBlack(parent);// 将插入节点现在是parent的位置，染成黑色
            setRed(gparent);// 将插入节点的祖父节点（位置没变）染成红色
            leftRotate(gparent); // 完成第二次旋转，对于RR和LL型，此次旋转无效
        }
    }

    // 将根节点设为黑色
    setBlack(this.mRoot);
}

/**
     * 将结点插入到红黑树中
     *
     * 参数说明：
     *     node 插入的结点        // 对应《算法导论》中的node
     */
private void insert(RBTNode<T> node) {
    int cmp;
    RBTNode<T> y = null;
    RBTNode<T> x = this.mRoot;

    // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
    while (x != null) {
        y = x;
        cmp = node.key.compareTo(x.key);
        if (cmp < 0)
            x = x.left;
        else
            x = x.right;
    }
    // y用来作为node的父亲
    node.parent = y;
    // 执行node的插入
    if (y!=null) {
        cmp = node.key.compareTo(y.key);
        if (cmp < 0)
            y.left = node;
        else
            y.right = node;
    } else {
        this.mRoot = node;
    }

    // 2. 设置节点的颜色为红色（我们只插入红色节点）
    node.color = RED;

    // 3. 将它重新修正为一颗二叉查找树
    insertFixUp(node);
}

/**
     * 新建结点(key)，并将其插入到红黑树中
     * 对外的接口
     *
     * 参数说明：
     *     key 插入结点的键值
     */
public void insert(T key) {
    RBTNode<T> node= new RBTNode<T>(key, BLACK, null, null, null);
    insert(node);
}

删除操作
代码的结构和插入操作是一样的，同样做了大量注释。请放心食用。

/**
     * 红黑树删除修正函数
     *
     * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
     * 目的是将它重新塑造成一颗红黑树。
     *
     * 参数说明：
     *     node 待修正的节点
     */
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
    RBTNode<T> other;
    // 当被删除节点为黑色节点
    while ((node==null || isBlack(node)) && (node != this.mRoot)) {
        if (parent.left == node) {// 被删除的是父节点的左孩子
            other = parent.right;
            // Case 1: x的兄弟w是红色的。（借用兄弟节点修复）
            if (isRed(other)) {
                setBlack(other);
                setRed(parent);
                leftRotate(parent);
                other = parent.right;
            }
            // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的。兄弟节点无红色子节点（兄弟无节点借出，父节点向下合并）
            if ((other.left==null || isBlack(other.left)) &&
                (other.right==null || isBlack(other.right))) {
                setRed(other);
                node = parent;
                parent = parentOf(node);
            } else {// 兄弟节点有红子节点
                // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。兄弟节点有一个红色左子节点
                if (other.right==null || isBlack(other.right)) {
                    setBlack(other.left);
                    setRed(other);
                    rightRotate(other);
                    other = parent.right;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。兄弟节点有一个红色右子节点
                setColor(other, colorOf(parent));
                setBlack(parent);
                setBlack(other.right);
                leftRotate(parent);
                node = this.mRoot;
                break;
            }
        } else {// 被删除的是父节点的左孩子
            other = parent.left;
            // Case 1: x的兄弟w是红色的（借用兄弟节点修复）
            if (isRed(other)) {
                setBlack(other);
                setRed(parent);
                rightRotate(parent);
                other = parent.left;
            }
            // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的。兄弟节点无红色子节点（兄弟无节点借出，父节点向下合并）
            if ((other.left==null || isBlack(other.left)) &&
                (other.right==null || isBlack(other.right))) {
                setRed(other);
                node = parent;
                parent = parentOf(node);
            } else {// 兄弟节点有红子节点
                // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。兄弟节点有一个红色左子节点
                if (other.left==null || isBlack(other.left)) {
                    setBlack(other.right);
                    setRed(other);
                    leftRotate(other);
                    other = parent.left;
                }
                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
                setColor(other, colorOf(parent));
                setBlack(parent);
                setBlack(other.left);
                rightRotate(parent);
                node = this.mRoot;
                break;
            }
        }
    }

    if (node!=null)
        setBlack(node);
}

/**
     * 删除结点(node)，并返回被删除的结点
     *
     * 参数说明：
     *     node 删除的结点
     */
private void remove(RBTNode<T> node) {
    RBTNode<T> child, parent;
    boolean color;

    // 被删除节点的"左右孩子都不为空"的情况。对于非叶子节点转换为对前驱/后继的删除
    if ( (node.left!=null) && (node.right!=null) ) {
        // 被删节点的后继节点。(称为"取代节点")
        // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
        RBTNode<T> replace = node;

        // 获取后继节点
        replace = replace.right;
        while (replace.left != null)
            replace = replace.left;

        // "node节点"不是根节点(只有根节点不存在父节点)
        if (parentOf(node)!=null) {
            if (parentOf(node).left == node)
                parentOf(node).left = replace;
            else
                parentOf(node).right = replace;
        } else {
            // "node节点"是根节点，更新根节点。
            this.mRoot = replace;
        }

        // child是"取代节点"的右孩子，也是需要"调整的节点"。
        // "取代节点"肯定不存在左孩子！因为它是一个后继节点。
        child = replace.right;
        parent = parentOf(replace);
        // 保存"取代节点"的颜色
        color = colorOf(replace);

        // "被删除节点"是"它的后继节点的父节点"
        if (parent == node) {
            parent = replace;
        } else {
            // child不为空
            if (child != null)
                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;

        // 完成替换后开始真正的删除和调整
        // Case1 红色节点可以直接删除（删除最后一层的节点对红黑树性质没有影响）

        // Case2 黑色节点的删除调整
        if (color == BLACK)
            removeFixUp(child, parent);

        node = null;
        return ;
    }

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

    parent = node.parent;
    // 保存"取代节点"的颜色
    color = node.color;

    if (child!=null)
        child.parent = parent;

    // "node节点"不是根节点
    if (parent!=null) {
        if (parent.left == node)
            parent.left = child;
        else
            parent.right = child;
    } else {
        this.mRoot = child;
    }

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

/**
     * 删除结点(z)，并返回被删除的结点
     * 对外接口
     *
     * 参数说明：
     *     tree 红黑树的根结点
     *     z 删除的结点
     */
public void remove(T key) {
    RBTNode<T> node;

    if ((node = search(mRoot, key)) != null)
        remove(node);
}

其他操作

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

    public RBTNode<T> mRoot;    // 根结点

    private static final boolean RED   = false;
    private static final boolean BLACK = true;
    
     public RedBlackTree() {
        mRoot=null;
    }

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

    /**
     * 返回红黑树节点的颜色
     *
     * @param node 节点
     * @return boolean
     */
    private boolean colorOf(RBTNode<T> node) {
        return node!=null ? node.color : BLACK;
    }
    private boolean isRed(RBTNode<T> node) {
        return ((node!=null)&&(node.color==RED)) ? true : false;
    }
    private boolean isBlack(RBTNode<T> node) {
        return !isRed(node);
    }
    private void setBlack(RBTNode<T> node) {
        if (node!=null)
            node.color = BLACK;
    }
    private void setRed(RBTNode<T> node) {
        if (node!=null)
            node.color = RED;
    }
    private void setParent(RBTNode<T> node, RBTNode<T> parent) {
        if (node!=null)
            node.parent = parent;
    }
    private void setColor(RBTNode<T> node, boolean color) {
        if (node!=null)
            node.color = color;
    }
    
    /*
     * (递归实现)查找"红黑树x"中键值为key的节点
     */
    private RBTNode<T> search(RBTNode<T> x, T key) {
        if (x==null)
            return x;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }
    
    /*
     * (非递归实现)查找"红黑树x"中键值为key的节点
     */
    private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {
        while (x!=null) {
            int cmp = key.compareTo(x.key);

            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else
                return x;
        }

        return x;
    }

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

    /*
     * 查找最小结点：返回tree为根结点的红黑树的最小结点。
     */
    private RBTNode<T> minimum(RBTNode<T> tree) {
        if (tree == null)
            return null;

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

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

        return null;
    }

    /*
     * 查找最大结点：返回tree为根结点的红黑树的最大结点。
     */
    private RBTNode<T> maximum(RBTNode<T> tree) {
        if (tree == null)
            return null;

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

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

        return null;
    }


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

    /**
     * 销毁红黑树
     */
    private void destroy(RBTNode<T> tree) {
        if (tree==null)
            return ;

        if (tree.left != null)
            destroy(tree.left);
        if (tree.right != null)
            destroy(tree.right);

        tree=null;
    }

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


    ...
}

功能测试
我们这里引入一个红黑树展示工具类，它能形象的为我们打印红黑树。

public class TreeOperation {

      /*
    树的结构示例：
              1
            /   \
          2       3
         / \     / \
        4   5   6   7
    */

    /**
     * 用于获得树的层数
     *
     * @param root
     * @return
     */
    public static int getTreeDepth(RedBlackTree.RBTNode<?> root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }

    private static void writeArray(RedBlackTree.RBTNode<?> currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null) {
            return;
        }
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.format("%s-%s ", currNode.key, "true".equals(String.valueOf(currNode.color)) ? "R" : "B");

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth) {
            return;
        }
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的""与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = <img src=""\";" alt="" width="50%" />
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }

    }


    public static void show(RedBlackTree.RBTNode<?> root) {
        if (root == null) {
            System.out.println("EMPTY!");
        }
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

接下来开始测试功能

测试插入：

public final int[] a = {10, 40, 30, 60, 90, 70, 20, 50, 80};

@Test
public void insertTest(){
    int i, ilen = a.length;
    RedBlackTree<Integer> tree=new RedBlackTree<>();

    for(i=0; i<ilen; i++) {
        tree.insert(a[i]);
    }

    TreeOperation.show(tree.mRoot);
}

测试结果：

            30-R           
         /     \         
      10-R          60-B     
        \       /   \    
          20-B  40-R      80-R 
               \     / \ 
                50-B  70-B  90-B

测试删除：

public final int[] a = {10, 40, 30, 60, 90, 70, 20, 50, 80};
   
@Test
public void deleteTest(){
    int i, ilen = a.length;
    RedBlackTree<Integer> tree=new RedBlackTree<>();

    for(i=0; i<ilen; i++) {
        tree.insert(a[i]);
    }

    tree.remove(30);

    TreeOperation.show(tree.mRoot);
}

测试结果：

            40-R           
         /     \         
      10-R          60-B     
        \       /   \    
          20-B  50-R      80-R 
                     / \ 
                    70-B  90-B

小结
红黑树并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以 O(logn) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。
总得来说红黑树是一个查找，删除效率都很好的树结构。并且操作稳定，是适用于工业化的数据结构。
相信看完本篇文章后，你能对这个底层偏爱的数据结构有所了解。