数据结构-红黑树分析+代码

二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 。

不过，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 O(n)。要解决这个复杂度退化的问题，我们需要设计一种平衡二叉查找树，也就是今天要讲的这种数据结构。

很多书籍里，但凡讲到平衡二叉查找树，就会拿红黑树作为例子。不仅如此，如果你有一定的开发经验，你会发现，在工程中，很多用到平衡二叉查找树的地方都会用红黑树。你有没有想过，为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？

什么是“平衡二叉查找树”？

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是不满足完全二叉树的条件也有可能是平衡二叉树。

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。最先被发明的平衡二叉查找树是 AVL 树，它严格符合我刚讲到的平衡二叉查找树的定义，即任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。

但是很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如我们下面要讲的红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。

所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

所以，如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比 log2n 大很多（比如树的高度仍然是对数量级的），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。

如何定义一棵“红黑树”？

平衡二叉查找树其实有很多，比如，Splay Tree（伸展树）、Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。它的出镜率甚至要高于“平衡二叉查找树”这几个字，有时候，我们甚至默认平衡二叉查找树就是红黑树，那我们现在就来看看这个“明星树”。

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树。红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

我前面说了，它的定义是不严格符合平衡二叉查找树的定义的。这里给出红黑树的五条性质：

• 每个节点要么是红色，要么是黑色；

• 根节点是黑色的；

• 所有叶节点都是是黑色空节点（注意这里说叶子节点其实是 NIL 节点，不存储数据）

• 红色节点一定被黑色节点隔开的，也就是说每个红色节点的两个子节点和父节点一定都是黑色；

• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

这里要求“所有叶子节点都是黑色空节点”，稍微有些奇怪，它主要是为了简化红黑树的代码实现而设置的，之后在画图和讲解的时候，我将黑色的、空的叶子节点为图方便可能会将其省去。

性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。红黑树并不是标准平衡二叉树，它以性质 5 作为一种平衡方法，使自己的性能得到了提升。

为了让你更好地理解上面的定义，我画了两个红黑树的图例，你可以对照着看下。

为什么说红黑树是“近似平衡”的？

我们前面也讲到，平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化得太严重。

我们在上一节讲过，二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。

红黑树的高度不是很好分析，我带你一步一步来推导。

首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？

上一节我们说，完全二叉树的高度近似 log2n，这里的四叉“黑树”的高度要低于完全二叉树，所以去掉红色节点的“黑树”的高度也不会超过 log2n。

我们现在知道只包含黑色节点的“黑树”的高度，那我们现在把红色节点加回去，高度会变成多少呢？

从上面我画的红黑树的例子和定义看，在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

实现红黑树的基本思想

实际上，红黑树的平衡过程跟魔方复原非常神似，大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。

在正式开始之前，我先介绍两个非常重要的操作，左旋（rotate left）、右旋（rotate right）。左旋全称其实是叫围绕某个节点的左旋，那右旋的全称估计你已经猜到了，就叫围绕某个节点的右旋。

我们下面的平衡调整中，会一直用到这两个操作。

左旋我的记忆就是左高右低然后往反方向进行翘转  \ -> /

低端的左节点拆下给高端的右节点

右旋我的记忆就是左低右高然后往反方向进行翘转  / ->

低端的右节点拆下给高端的左节点

插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。

• 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。

• 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。

除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：左右旋转和改变颜色。

红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫做关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点。

新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况。我们只需要根据每种情况的特点，不停地调整，就可以让红黑树继续符合定义，也就是继续保持平衡。

我们下面依次来看每种情况的调整过程。提醒你注意下，为了简化描述，我把父节点的兄弟节点叫做叔叔节点，父节点的父节点叫做祖父节点。

CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色，我们就依次执行下面的操作：

将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；

将关注节点 a 的祖父节点 c 的颜色设置成红色；

关注节点变成 a 的祖父节点 c；

跳到 CASE  2 或者 CASE  3。

CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点，我们就依次执行下面的操作：

• 关注节点变成节点 a 的父节点 b；

• 围绕新的关注节点b 左旋；

• 跳到 CASE  3。

CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点，我们就依次执行下面的操作：

• 围绕关注节点 a 的祖父节点 c 右旋；

• 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。

• 调整结束。

删除节点

删除元素的过程和普通二叉搜索树的搜索过程大体也比较类似，首先是根据待删除节点的情况进行分析。

第二步则是删除后的调整

我们根据红黑树的第 5 个特性：如果当前待删除节点是红色的，它被删除之后对当前树的特性不会造成任何破坏影响。 而如果被删除的节点是黑色的，这就需要进行进一步的调整来保证后续的树结构满足要求。

删除元素之后的调整和前面的插入元素调整的过程比起来更复杂。它不是一个简单的在原来过程中取反。我们先从一个最基本的点开始入手。首先一个，我们要进行调整的这个点肯定是因为我们要删除的这个点破坏了红黑树的本质特性。而如果我们删除的这个点是红色的，则它肯定不会破坏里面的属性。因为从前面删除的过程来看，我们这个要删除的点是已经在濒临叶节点的附近了，它要么有一个子节点，要么就是一个叶节点。如果它是红色的，删除了，从上面的节点到叶节点所经历的黑色节点没有变化。所以，这里的一个前置条件就是待删除的节点是黑色的。

在前面的那个前提下，我们要调整红黑树的目的就是要保证，这个原来是黑色的节点被删除后，我们要通过一定的变化，使得他们仍然是合法的红黑树。我们都知道，在一个黑色节点被删除后，从上面的节点到它所在的叶节点路径所经历的黑色节点就少了一个。我们需要做一些调整，使得它少的这个在后面某个地方能够补上。

ok，有了这一部分的理解，我们再来看调整节点的几种情况。

1. 当前节点和它的父节点是黑色的，而它的兄弟节点是红色的：

这种情况下既然它的兄弟节点是红色的，从红黑树的属性来看，它的兄弟节点必然有两个黑色的子节点。这里就通过节点x的父节点左旋，然后父节点B颜色变成红色，而原来的兄弟节点 D 变成黑色。这样我们就将树转变成第二种情形中的某一种情况。在做后续变化前，这棵树这么的变化还是保持着原来的平衡。

2. 1） 当前节点的父节点为红色，而它的兄弟节点，包括兄弟节点的所有子节点都是黑色。

在这种情况下，我们将它的兄弟节点设置为红色，然后 x 节点指向它的父节点。这里有个比较难以理解的地方，就是为什么我这么一变之后它就平衡了呢？因为我们假定 A 节点是要调整的节点一路调整过来的。因为原来那个要调整的节点为黑色，它一旦被删除就路径上的黑色节点少了 1。所以这里 A 所在的路径都是黑色节点少 1.这里将A的兄弟节点变成红色后，从它的父节点到下面的所有路径就都统一少了 1.保证最后又都平衡了。

当然，大家还会有一个担忧，就是当前调整的毕竟只是一棵树中间的字数，这里头的节点B可能还有父节点，这么一直往上到根节点。你这么一棵字数少了一个黑色节点，要保证整理合格还是不够的。这里在代码里有了一个保证。假设这里B 已经是红色的了。那么代码里那个循环块就跳出来了，最后的部分还是会对 B 节点，也就是 x 所指向的这个节点置成黑色。这样保证前面亏的那一个黑色节点就补回来了。

2） 当前节点的父节点为黑色，而它的兄弟节点，包括兄弟节点的所有子节点都是黑色。

这种情况和前面比较类似。如果接着前面的讨论来，在做了那个将兄弟节点置成红色的操作之后，从父节点 B 开始的所有子节点都少了 1。那么这里从代码中间看的话，由于x指向了父节点，仍然是黑色。则这个时候以父节点 B 作为基准的子树下面都少了黑节点1。我们就接着以这么一种情况向上面推进。

3.  当前节点的父节点为红色，而它的兄弟节点是黑色，同时兄弟节点有一个节点是红色。

这里所做的操作就是先将兄弟节点做一个右旋操作，转变成第4种情况。当然，前面的前提是B为红色，在B为黑色的情况下也可以同样的处理。

4. 在当前兄弟节点的右子节点是红色的情况下。

image.png

这里是一种比较理想的处理情况，我们将父节点做一个左旋操作，同时将父节点B变成黑色，而将原来的兄弟节点 D 变成红色，并将 D 的右子节点变成黑色。这样保证了新的子树中间根节点到各叶子节点的路径依然是平衡的。大家看到这里也许会觉得有点奇怪，为什么这一步调整结束后就直接 x = T.root 了呢？也就是说我们一走完这个就可以 x 直接跳到根节点，其他的都不需要看了。这是因为我们前面的一个前提，A 节点向上所在的路径都是黑色节点少了一个的，这里我们以调整之后相当于给它增加了一个黑色节点，同时对其他子树的节点没有任何变化。相当于我内部已经给它补偿上来了。所以后续就不需要再往上去调整。

前面讨论的这4种情况是在当前节点是父节点的左子节点的条件下进行的。如果当前节点是父节点的右子节点，则可以对应的做对称的操作处理，过程也是一样的。

根据 TreeMap 的代码来验证这个过程：

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));  
            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 {  
                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 { // symmetric  
            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);  
}

我的代码实现

仿照以上的思路和 TreeMap 的源码进行改写而来。

src/main/java/com/s10/tree · leiTKai/struct - 码云 - 开源中国

https://gitee.com/kaiLee/struct/tree/master/src/main/java/com/s10/tree

其他

TreeMap 的红黑树实现当然也包含其他部分的代码实现，如用于查找元素的getEntry方法，取第一个和最后一个元素的 getFirstEntry，getLastEntry 方法以及求前驱和后继的 predecesor, successor 方法。这些方法的实现和普通二叉搜索树的实现没什么明显差别。这里就忽略不讨论了。这里还有一个有意思的方法实现，就是 buildFromSorted 方法。它的实现过程并不复杂，不过经常被作为面试的问题来讨论。后续文章也会针对这个小问题进行进一步的讨论。

总结

在一篇文章里光要把红黑树的来龙去脉折腾清楚就挺麻烦的，如果还要针对它的一个具体 jdk 的实现代码进行分析的话，这个话题就显得比较大了。不过一开始就结合优秀的实现代码来学习这个数据结构的话，对于自己体会其中的思想和锻炼编程的功力还是很有帮助的。TreeMap 里面实现得最出彩的地方还是红黑树的部分，当然，还有其他一两个比较有意思的方法，其问题还经常被作为一些面试的问题来讨论，后续的文章也会针对这部分进行一些分析。

参考

• 25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？

https://time.geekbang.org/column/article/68638

• 26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树 https://time.geekbang.org/column/article/68976

• Red/Black Tree Visualization
  https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

• java集合类深入分析之 TreeMap/TreeSet 篇 - 点缀星辰 - ITeye博客 https://www.iteye.com/blog/shmilyaw-hotmail-com-1836431

• 重温数据结构：深入理解红黑树_张拭心的博客 shixinzhang-CSDN博客 https://blog.csdn.net/u011240877/article/details/53329023

• 自己手写HashMap——红黑树的 Java 实现 | 码农网 https://www.codercto.com/a/76803.html

• 从 2-3 树到 红黑树_fei33423 的专栏-CSDN博客 https://blog.csdn.net/fei33423/article/details/79132930

• java/24_tree/BinarySearchTree.java · 编程语言算法集/algo - 码云 - 开源中国 https://gitee.com/TheAlgorithms/algo/blob/master/java/24_tree/BinarySearchTree.java

• 图文详解 BFS, DFS - 力扣（LeetCode）
  https://leetcode-cn.com/circle/article/YLb5l4/