引言

红黑树是一种弱平衡的二叉树，相比 AVL 这种严格平衡的二叉树来说，红黑树的这种弱平衡使得它在插入、删除元素的时候比 AVL 树更高效。所以即使在最坏情况下，它也可以保证查询、插入、删除在 O(logN) 的时间复杂度。

红黑树在实际中的应用也十分广泛，如：JDK1.8 中的 HashMap、TreeMap、ConcurrentHashMap 等底层实现、Linux 底层的 CFS 进程调度算法中，vruntime 的存储、多路复用 Epoll 的核心结构等。为了将专注点放在红黑树上，本文将以 JDK1.8 的 TreeMap 源码实现为基础进行介绍。希望本篇文章能让你彻底掌握红黑树。

2-3-4 树

要想搞懂红黑树，首先必须要知道红黑树的本质，它其实是 2-3-4 树的一种实现。所以我们先看看什么是 2-3-4 树。

2-3-4 树是阶数为 4 的 B 树（BalanceTree，即平衡树）。所谓树的阶数是指节点中子节点的最大值，阶数为 4 也就是节点最大含有 4 个子节点。如下图所示：

图中则是一个简单的 2-3-4 树，既然叫 2-3-4 树，说明树由 2 节点、3 节点、4 节点组成。其中节点 P 为 3 节点、L 跟 M 为 2 节点，R 为 4 节点。

树的增长

2-3-4 树的增长是自下而上的，如果满足条件的节点会先考虑合并，如果不满足的节点则分裂。我们以插入 1、2、3、4、5、6、7 元素为例，进行说明：

步骤一
插入 1、2、3 个元素后，由于满足最大节点为 4 的条件，所以三者会合并。接下来插入 4 的时候，发现已经超过最大节点为 4 的限制了。
步骤二
由于 4 的插入不满足条件，所以需要对原有 1、2、3 这个节点进行分裂，分裂是以中间元素为增长点，向上增长，也就是说 2 要往上提。然后 4 跟 3 进行合并为 3 节点。
步骤三
当插入到 6 时，发现不满足条件。
步骤四
同步骤二，4 要向上增长，6 则跟 5 进行合并。
步骤五
当增长的 4 发现，跟它同一级的还有一个 2 元素，所以 4 就会跟 2 进行合并，形成 3 节点
步骤六
接下来的 7 由于满足条件，所以会与 5、6 进行合并，形成最终的形态。

红黑树与 2-3-4 树的等价关系

明白了树的增长，我们接下就要看一下红黑树与 2-3-4 树的等价关系了。

2 节点

2-3-4 树的 2 节点对应红黑树的黑色节点。

3 节点

2-3-4 树的 3 节点对应与红黑树的两种状态，分别为左倾与右倾（注意：一定是黑上红下，并且都是双向指针）。

4 节点

红黑树需要平衡，所以不可能出现两个连续的红色节点（注意：黑上红下）。

分裂

当发生分裂时，由于不能有连续的红色节点，所以原有的 5、7 红色节点需要变黑，同时它们的父节点变红（如果父节点为根节点，那么还要变黑）。

红黑树转 2-3-4 树

有了以上的等价关系后，我们就可以通过红黑树得到 2-3-4 树。

如图所示，将红黑树中红色节点经过 45° 旋转之后，就会得到 2-3-4 树。

红黑树的性质

这里我们先列举下红黑树的五大性质以及倒推下五大性质的由来。

性质

节点是红色或者黑色。
根节点是黑色。
所有叶子节点都是黑色（注意：叶子都是 NIL 节点）。
每个红色节点必须有两个黑色的子节点（也就是说，从每个叶子到根的所有路径上不能有连续的红色节点）。
从任一节点到其每个叶子的所有简单路径都包含相同数量的黑色节点（黑色平衡）。

由来

节点是红色或者黑色
我们知道，2-3-4 树包括三类节点，分别为 2 节点、3 节点、4 节点。红黑树为了实现以上功能同时降低复杂度，通过两种颜色即可表示出以上三种节点。
根节点是黑色
为了说明这个问题，我们先看下 2-3-4 树有几种情况：
情况一

2-3-4 树的根节点为 2 节点时，由于 2 节点对应红黑树的黑节点。所以红黑树的根节点为黑色。

情况二

当 2-3-4 树的根节点为 3 节点时，对应于红黑树的右图状态，根节点 2 依然是黑色。

情况三

当 2-3-4 树的根节点为 4 节点时，我们发现红黑树的根节点 4 依然为黑色。所以，红黑树的根节点总为黑色。
所有的叶子都是黑色

其实每棵红黑树的叶子节点都挂了一个 Nil 的节点，如图所示。只不过该节点属于隐藏节点。
每个红色节点必须有两个黑色的子节点
该性质的另外一个意思是，两个红色节点不能同时相连，这怎么推导呢？我们看下图：

我们把红黑树转换成 2-3-4 树之后，发现（2，4）组成的 3 节点包含了 3 跟（5，6，7）两个节点。其中 3 为 2 节点，（5，6，7）为 4 节点。我们回想一下，无论是 2 节点、3 节点还是 4 节点。黑色节点都在红色节点上边，所以并不会出现红色节点挂载红色节点的场景。
从任一节点到其每个叶子的所有简单路径都包含相同数量的黑色节点

如图所示，2-3-4 树有一个特性就是从根到每一个叶子的路径都相等。从 2-3-4 树节点与红黑树的对应关系来看，2-3-4 树的每一个节点都包含一个黑色节点，所以自然而然每条路径的黑色节点数量也就相等了。这也是红黑树的弱平衡——黑色平衡。