结合 TreeMap 源码分析红黑树在 java 中的实现

注：本文的源码摘自 jdk1.8 中 TreeMap

红黑树的意义
红黑树的性质
左旋、右旋
增
删
总结

红黑树的意义

红黑树本质上是一种特殊的二叉查找树，红黑树保证了一种平衡，插入、删除、查找的最坏时间复杂度都为 O(lgN)。那么红黑树是如何实现这个特性的呢？红黑树区别于其他二叉查找树的规则在于它的每个结点拥有红色或黑色中的一种颜色，然后按照一定的规则组成红黑树，而这个规则就是我们这篇文章所想要阐述的了。
红黑树的性质

红黑树遵循以下五点性质：

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

以下有几个违反上述规则的结点示例：

违反性质1

结点必须是红色或黑色

违反性质2

根结点必须是黑色的

违反性质3

叶子结点必须是黑色的

违反性质4

以上三个都是错误的红黑树示例，每个红色结点的两个子结点都是黑色，而如下是合格的

遵循性质4

当然，细心的读者应该发现了我只是展示了前四条性质而没有展示第五条性质，没有什么理由，笔者就是懒，第五条挺好理解的。

左旋、右旋

在学习红黑树之前想要介绍一个概念——左旋、右旋。这是一种结点操作，是红黑树里面时常出现的一个操作，请看下图 ——
左旋右旋概念图

左旋右旋概念图

这里的左旋右旋都是针对根节点而言的，所以左图到右图是 y 结点右旋，右图到左图是 x 结点左旋。

左旋：根结点退居右位，左子结点上位，同时左子结点的右子结点变成根节点左结点。
右旋：根节点退居左位，右子节点上位，同时右子结点的左子结点变成根节点右结点。

现在不理解这俩概念有什么用不重要，但是希望读者能理解它的变幻过程，到后面会涉及到。

说起来枯燥无意，我们可以结合 TreeMap 来看看左旋右旋的源码 ——

方法图

在这里我们就针对左旋源码看看 ——

左旋源码

笔者就直接一行一行解释吧：

复制代码private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right;         // r 是根结点右子结点
        p.right = r.left;               // 为根结点的左结点指向右子结点（也就是 r）的左结点
        if (r.left != null)
            r.left.parent = p;          // 意义同第二步，这步是右子结点（也就是 r）的左结点将父结点引用指向 p
        r.parent = p.parent;            // 将 r 结点的父引用指向 p 结点的父引用
        if (p.parent == null)
            root = r;                   // 将根结点替换为 r
        else if (p.parent.left == p)
            p.parent.left = r;          // 意义同上
        else
            p.parent.right = r;         // 意义同上
        r.left = p;                     // r 左结点引用指向 p 结点
        p.parent = r;                   // p 结点父引用指向 r 结点
    }
}

增

假设现在我们找到了相应的结点插入位置，那么我们接下来就可以插入相应的结点了，这个时候迎来一个头疼的问题，我们知道红黑树结点是有颜色的，那么我们应该给它设置成黑色的还是红色的呢？
设置成黑色的吧，就违反了性质5，设置成了红色的吧，就容易违反了性质4。那怎么办？总要给一个颜色，那我们就给红色的吧。为什么？因为如果设置成黑色的话，该分支的黑色结点数量肯定比其他分支多一个，而这样的话相当地不好做调整。如果将插入结点颜色置为红色的话，运气比较好的情况下该父结点就是黑色的，那这样就不需要做任何调整。另一种情况是插入结点的父结点颜色是红色的，这种情况我们就需要详细讨论了，具体分为以下两种（此处我们以插入结点的父结点是爷爷结点的左子结点为例（有点拗口），镜像操作道理相同）：

1.父结点与叔叔结点都为红

父结点与叔叔结点都为红

父结点与叔叔结点都为红的话那么必定爷爷结点为黑，实际上此时我们最简单的操作就是将父结点和叔叔结点染黑，将爷爷结点染红（将爷爷结点染红的目的是为了保证爷爷结点路径的黑色结点数量不改变），如下 ——

染黑

现在目标结点、父结点、叔叔结点都符合要求了，但是爷爷结点的父结点是红色的，那么就冲突了，聪明的读者可能已经发现了，此时的爷爷结点就相当于目标结点，我们不妨将爷爷结点置换为目标结点，再进行递归操作就可以达到解决冲突的目的了。

2.父结点为红，叔叔结点为黑

父结点为红，叔叔结点为黑

但凡有一个结点是红色，那么它的父结点必定是黑色（性质4），所以爷爷结点一定是黑色的。

有细心的小伙伴可能觉察到，上图违反了性质五。实际上上图是一张简化后的图，为了我们后面的内容更加便于理解，上图的原图应该是以下模样 ——

上图原图

ps：上图中叔叔结点和兄弟结点可以理解成 java 中的 null 结点，笔者特地将它们的个头缩小了，以便区分。

那么此时该怎么操作呢？爷爷结点右旋，爷爷结点置红，父结点置黑。这条操作过后，性质4、5都没有违反。

爷爷结点右旋，爷爷结点置红，父结点置黑

当然，上图也只是一张简化图，实际上原图如下：

上图原图

那么结合 TreeMap 源码我们来看看：

插入调整源码

翻译如下：

复制代码private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;      // 目标结点颜色赋红

    // 目标结点非空，非根，同时父结点为红，此时才需要调整
    while (x != null && x != root && x.parent.color == RED) {
        // 父结点是爷爷的左子结点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));  // y 是叔叔结点
            // 情况1 叔叔结点也为红
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);               // 父结点赋黑
                setColor(y, BLACK);                         // 叔叔结点赋黑
                setColor(parentOf(parentOf(x)), RED);       // 爷爷结点赋红
                x = parentOf(parentOf(x));                  // 爷爷结点置为目标结点，递归
            } else {
                // 情况2 叔叔结点为黑
                // 小插曲，如果目标结点是父结点的右子结点，左旋父结点
                // 当然，此时目标结点应改为父结点
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);               // 父结点赋黑
                setColor(parentOf(parentOf(x)), RED);       // 爷爷结点赋红
                rotateRight(parentOf(parentOf(x)));         // 爷爷结点右旋
            }
        } else {
            // 镜像操作，道理同上
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;     // 根结点必须赋黑
}

看完代码我们发现我们好像漏了一个小插曲（当然，这是笔者故意的），那么小插曲是一个什么情况呢？言语来说，在叔叔结点为黑的前提下，当目标结点是父结点的右子结点的时候，需要对父结点进行左旋然后才能接续下一步操作，为什么会这样，我们一图胜千言 ——

小插曲

如果忽略上述情况，那么最终会得到以下情况：

小插曲忽略情况下实现

由于目标结点是父结点的右子节点，在爷爷结点右旋过程中，它会转为原爷爷结点的左子结点，这样的话就违反了特性4和特性5。解决方法就是上面所提到的将父结点先进行左旋然后再进行前面所提到的操作，如下图 ——

小插曲修正

当然，不要忘了，现在需要调整的结点是原父结点，也就是要将上图左下角那个结点作为目标结点进行调整。

所以红黑树的添操作分为以下三步：

找到相应的插入位置
将目标结点设置为红色并插入
通过着色和旋转等操作使之重新成为一棵二叉树

删

这一小节我想先 show 出源码再来解释 ——
删除结点源码

删除结点源码

翻译如下：

复制代码private void deleteEntry(Entry<K,V> p) {
    // 优先选择左子结点作为被删结点的替代结点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    // 如果替代结点不为空
    if (replacement != null) {
        replacement.parent = p.parent;
        // 如果删除结点为根节点，那么根节点重定向引用指向替代结点
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            // 如果删除结点是其父结点的左子结点，更改父结点左子结点引用指向替代结点
            p.parent.left  = replacement;
        else
            // 如果删除结点是其父结点的右子结点，更改父结点右子结点引用指向替代结点
            p.parent.right = replacement;

        // 将删除结点的各个引用置 null
        p.left = p.right = p.parent = null;

        // 如果删除结点颜色为黑色，那么需要进行删后调整
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) {
        // 如果替代结点为空且删除结点为 root 结点
        root = null;
    } else {
        // 如果删除结点为空且不是 root 结点
        // 如果删除结点颜色为黑色，那么需要进行删后调整
        if (p.color == BLACK)
            fixAfterDeletion(p);

        // 将删除结点的各个引用置 null
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

删除时可能分为三种情况，具体的做法也在上述代码中做了清晰的解释，笔者在此就不扩展了，细心的读者可能发现了，上述删除操作凡是涉及到了删除结点是黑色的情况下，都需要调用 fixAfterDeletion() 方法对红黑树进行调整。这是因为如果删除结点是黑色的，当它被删除后就会违反性质5，所以我们需要对红黑树进行结构调整。

为了便于理解红色结点为什么不会影响红黑树整体结构，笔者还是举了一个例子给各位读者理解一下，下图是删除前：

删除前

下图是删除后：

删除后

实际上红黑树是使用以下2点思想来进行调整的（笔者认为，在分析 fixAfterDeletion() 代码实现之前，作为开发者应该去自行思考一下如果我们作为源码设计者，我们会如何来解决这个问题。） ——

1.给删除结点的路径增加一个黑色结点（将兄弟路径的一个黑色结点移过来）
2.给删除结点的兄弟路径减少一个黑色结点（将兄弟路径的一个红色结点染黑）

ps:后面我们会针对第一条称为思想1，第二条称为思想2。

说完思想，我们讨论一下具体删除操作是如何进行的。红黑树在保障删除结点的兄弟结点为黑色的情况下（没有什么特殊缘由，仅仅是为了后期好操作），分以下两点来进行分析：

1.兄弟结点的两个子结点都是黑色的
2.另一种情况（兄弟结点的两个子结点至多一个黑色的）

ps:后面我们会针对第一条称为情况1，第二条称为情况2。

对于情况1来说，红黑树采用思想2，将兄弟结点置为红色，但是这样带来了两个问题——对于父路径来说，它与兄弟路径黑色结点数量不同，违反性质5；且如果父结点也是红色，那么它势必与孩子结点冲突，还会违反性质4，如下图——

下图示例违反性质5：

原图

违反性质5

下图示例违反性质5且违反性质4：

原图

违反性质4、5

对于前一个问题用递归的思想来解决，将父亲结点置为目标结点，让父亲结点的兄弟结点也要减少一个黑色结点就可以了（借鉴思想2）；而对于后一个问题，只需要将父结点置黑即可（借鉴思想2）。jdk 中相关实现源码如下：

复制代码while (x != root && colorOf(x) == BLACK) {
    Entry<K,V> sib = rightOf(parentOf(x));
    if (colorOf(leftOf(sib))  == BLACK &&
        colorOf(rightOf(sib)) == BLACK) {
        setColor(sib, RED);
        x = parentOf(x);
    }
}

setColor(x, BLACK);

前面阐述的是针对情况1而言，针对于情况2而言，红黑树采用的是思想1，具体做法分为又得分为以下两种小情况：

兄弟结点的右子结点不为黑
兄弟结点的右子结点为黑

对于第一种小情况，红黑树采用以下操作：

1.兄弟结点置父结点颜色（准备谋权篡位）
2.父结点置黑、兄弟结点右结点置黑
3.父结点左旋

该思想不仅保证了更新结点后不会冲突（父结点与兄弟结点不冲突，兄弟结点与右子结点不冲突，兄弟结点左子结点与父结点不冲突），并且保证了黑色结点数量不会改变，一图胜千言——

第一种小情况原图

第一种小情况删除后修正

jdk 中相关源码如下：

复制代码while (x != root && colorOf(x) == BLACK) {
    setColor(sib, colorOf(parentOf(x)));
    setColor(parentOf(x), BLACK);
    setColor(rightOf(sib), BLACK);
    rotateLeft(parentOf(x));
    x = root;
}

setColor(x, BLACK);

而对于第二种小情况，红黑树采用以下操作：

1.将兄弟结点的左子结点染黑
2.兄弟结点染红
3.兄弟结点右旋

第二种小情况原图

第二种小情况删除后修正

实际上细心的读者发现了，转换后的结构是等同于第一种小情况的初始结构，所以接下来就按照第一种小情况的步骤去变换结构，相关源码如下：

复制代码while (x != root && colorOf(x) == BLACK) {
    if (colorOf(rightOf(sib)) == BLACK) {   // 情况2
        setColor(leftOf(sib), BLACK);
        setColor(sib, RED);
        rotateRight(sib);
        sib = rightOf(parentOf(x));
    }

    // 情况1
    setColor(sib, colorOf(parentOf(x)));
    setColor(parentOf(x), BLACK);
    setColor(rightOf(sib), BLACK);
    rotateLeft(parentOf(x));
    x = root;
}

setColor(x, BLACK);

这一块可能有一些复杂，但记住以下三点核心思想问题就不是很大了：

父结点替换删除结点（保障了删除结点路径上的黑色结点数量不变）
兄弟结点替换父结点（保障了父结点路径上的黑色结点数量不变）
右子结点（结构变化前一定是红色的，变换后置黑）替换兄弟结点（保障了兄弟路径上的黑色结点数量不变）

那么接下来就是看看 fixAfterDeletion() 的代码实现了 ——

结点删除调整源码

解释如下：

复制代码private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        // 目标结点是左子结点
        if (x == leftOf(parentOf(x))) {
            // 目标结点的兄弟结点
            Entry<K,V> sib = rightOf(parentOf(x));

            // 小插曲1，如果兄弟结点为红
            // 这步是保障兄弟结点一定为黑
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);           // 兄弟结点置黑
                setColor(parentOf(x), RED);     // 父结点置红
                rotateLeft(parentOf(x));        // 父结点左旋
                sib = rightOf(parentOf(x));     // 重定向兄弟结点
            }

            // 兄弟结点的两个子结点是黑色
            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);             // 兄弟结点置红
                x = parentOf(x);                // 重定向目标结点为父结点
            } else {
                // 兄弟结点的子结点至多一个是黑色的

                // 小插曲2，兄弟结点左子结点为红，右子结点为黑的情况
                // 这步的意义是让兄弟结点的右子结点的数量多一个
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                // 将兄弟结点颜色置为父结点颜色（言外之意肯定是兄弟结点要替换父结点的位置）
                setColor(sib, colorOf(parentOf(x)));
                // 将父结点置黑
                setColor(parentOf(x), BLACK);
                // 将兄弟结点右子结点置黑
                setColor(rightOf(sib), BLACK);
                // 左旋父结点
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // 镜像操作
            Entry<K,V> sib = leftOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }

    setColor(x, BLACK);
}

总结

红黑树的插入操作是基于插入结点颜色为红色，原因是如果插入结点是黑色的话，会导致涉及到该结点的路径上的黑色结点数量会比兄弟路径的黑色结点数量多一个，那么整体调节起来势必很不方便。而删除操作是基于删除结点如果是黑色的情况下，才需要进行调整，因为黑色结点的删除会导致涉及到该结点的路径上的黑色结点数量会比兄弟路径的黑色结点数量少一个，那么就需要进行整体调节。
红黑树在 java 中的运用实际上还是挺多的，例如 TreeSet 的默认底层实现实际上也是 TreeMap；jdk 8中的 HashMap 实现也由原来的数组+链表更改为了数组+链表/红黑树。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有