Nginx 中的红黑树

1.ngx_rbtree_t红黑树

ngx_rbtree_t（红黑树）是一种非常有效的数据结构，nginx中的核心模块（如定时器管理、文件缓存模块）需要进行快速检索的场合下都使用了ngx_rbtree_t。红黑树实际上是一种自平衡二叉查找树，普通的二叉查找树在极端情况可能会退化成单链表，操作效率低下。那么什么是自平衡二叉查找树？在不断的向二叉查找树种添加、删除节点时，二叉查找树自身通过形态的转换，始终保持一定程度上的平衡，即为自平衡二叉查找树。红黑树就是一种自平衡性较好的二叉查找树，它支持快速的快速的检索、插入、删除操作，同时支持范围查询、遍历操作，是一种应用场景很广泛的高级数据结构。

2.红黑树的由来与特性

2.1 红黑树前言

算法导论中的红黑树概念：

1.每个节点不是黑色的，就是红色的。

2.根节点是黑色的。

3.每个叶子节点（最后的空节点）是黑色的

4.如果一个节点是红色的，那么他的孩子节点都是黑色的。

5.从任意一个节点到叶子节点，经过的黑色节点是一样的。

这样的一个介绍，没有介绍清楚红黑树是怎么来的，而是直接给出特别生硬的定义,过于形式化，让人无法理解。

红黑树的发明人在算法4中，直接绕过了五个算法导论中的定义，首先探索了另外一种树2-3树。

事实上红黑树和2-3树是等价的，当你理解了等价关系，再看红黑树的五条基本性质，发现是非常自然的。

 2.2 什么是2-3树

1.首先满足二分搜索树的基本性质。

2.节点可以存放一个元素或者两个元素。

有一个元素的节点叫二节点，有二个元素的节点叫三节点。

2.3 2-3树是一颗绝对平衡的树

从根节点到任意一个叶子节点经过的节点数量是相同的。那么2-3树是如何维持绝对平衡

下面我将展示如何向2-3树中添加节点。

2-3树添加节点的原则：永远不会添加到一个空的位置，只会和最后找到的叶子节点做融合。

示例：依次添加 42，37 , 12 ，18，6， 11，5

1.   首先，添加42节点。对于一颗空2-3树，添加一个节点非常容易，这个唯一的节点作为根节点。

2. 添加第二个节点37。

3.添加第三个节点12。

由于37的左子树为空，添加的过程中找到的最后叶子结点为一个三节点，依然做融合。 暂时形成一个四节点。 对于2-3树来说不能有四节点，所以要分裂成一颗子树。

一个四节点变成了一颗由三个二节点组成的平衡树。

4. 添加四个节点18。

5.添加第五个节点6。

如果一个叶子节点本身就是3节点，添加一个变成了四节点，向下拆解时，不是一颗绝对平衡的2-3树。所以向上融合，12与37直接融合变成一个3节点。

依然是一颗绝对平衡的2-3树。

6.添加第六个节点11。

7.添加第七个节点5。

步骤一：对于5这个节点融合进去它的父亲节点之后，形成一个新的四节点。

步骤二：把四节点的三个元素化成三个二节点。

步骤三：此时因为不是绝对平衡，所以继续向上融合，形成一个新的四节点

步骤四：对于2-3树来说不能有四节点，所以要拆分四节点，对于这一颗2-3树来说，现在全部都是2节点，保持绝对平衡。

2.4.红黑树与2-3树的等价性

对于咱们所熟悉的树结构，每个节点都只能存储一个元素，这是因为，对节点的操作，包括对树的操作，以及对代码的编写上会简单很多。(有兴趣的可以编写下2-3树的代码)

我们依然让每个节点只存储一个元素，基于这样的方式，实现2-3树的逻辑。实际上这样的树结构就是红黑树。

如图所示：对于二节点来说很简单，一个黑色节点代表二节点。复杂的是三节点，我们用两个节点来表示三节点，

在2-3树中，3节点(b，c)是一起的，并列关系，而在红黑树中为了表示这种关系 ，我们将b,c之间的边设置为红色来表示这种(并列)关系。

不过对于我们常见的树(二分搜索树)结构来说，对于边这个对象，没有专门用个类来表示，这样会比较复杂，增加复杂度。那么怎么实现呢？

首先每个节点只有一个父亲，换句话来说，每个节点和他的父亲节点所连接的边，只有一根。所以我们可以把边的信息存放到节点上，  也就是把b节点设置为红色。

即，b节点，和他的父亲c 节点，表示在原来2-3树中的3节点。     

所有的红色节点都是向左倾斜的。这个其实是定义，并不是结论。对于三节点，因为我们选择了这样的一种方法来定义，

左边的元素当做右边元素的孩子节点来看待，与此同时左边的节点是红色节点。所以红色节点是向左倾斜的。这里我们讲的是左倾红黑树。

如果大家明白了上面的论述，那么对于一颗2-3树，自然而然的就能用红黑树表示出来。

如果仍觉得抽象，请看下面右图。相信大家已经明白了2-3树与红黑树的等价关系。

2.5.红黑树的基本性质与复杂度分析

当我们明白红黑树与2-3树的等价关系后，在往上看基于算法导论中的性质。

1：不是红色就是黑色(没什么好说的~~)。

2：根节点是黑色。对于红黑树来说，本身等价于2-3树，所以根节点不是2-节点，就是3-节点。

3：每个叶子节点（最后的空节点，而不是左右子树都为空的节点）是黑色的。这条性质是个定义，红黑树中定义空这样的一个节点是黑色的。

也与上条性质吻合，对于空树来说，他的根节点为空，根节点为黑色，空节点也为红色。

4：如果一个节点是红色的，那么他的孩子节点都是黑色的。

在红黑树中，红色节点，它表示的是2-3树的三节点左侧的元素，这个红色节点，它的孩子节点要么是2-节点，要么是3-节点。

当是2-节点时，显然是黑色的。

当是3-节点时，这其实跟 根节点是黑色 的是一样的。它首先先连接的一定是个黑色节点。

5：在红黑树中，从任意一个节点到叶子节点，经过的 黑色节点 一定是一样的。

2-3树是一颗绝对平衡的树，这意味着，从任意节点出发到叶子节点所经历的节点数是一样多的。

又因在2-3树中，不管是2-节点，还是3-节点，转换成红黑树中节点表示时，都会有一个黑色节点。

所以从红黑树任意一个节点出发，每经过一个黑色节点，其实就等同于原来2-3树中的某一个节点。

所以红黑树是一颗保持 黑平衡 的的二叉树：对于红黑树来说，从根节点出发，到任意一个叶子节点所经历的黑色节点是一样多的。

最大高度为2logN，时间复杂度为o(logN)。极端情况，从根节点出发到最深的叶子节点，经历了logN级别个黑色节点，同时每个黑色节点的左子树都为红色节点

路径对应到2-3树，每个节点都是3节点。所以我们又经历了logN级别个红色节点,所以最大高度为2logN。

2.6.红黑树的变色和旋转

红黑树本身作为一棵二叉查找树，所以其任务就是用于动态表中数据的插入和删除的操作。在进行该操作时，避免不了会破坏红黑树的结构，此时就需要进行适当的调整，使其重新成为一棵红黑树，可以从两个方面着手对树进行调整：

• 调整树中某些结点的指针结构；

• 调整树中某些结点的颜色；

2.6.1 左旋转

左旋转的过程：

这里有个小问题，如果node的color本身就是红色，x.color也是红色，可能无法保持红黑树的基本性质。

此时有个说明，因为左旋转是个子过程，不维持红黑树的基本性质，后续还有处理过程。

2.6.2颜色翻转

2.6.3右旋转

3.ngx_rbtree_t红黑树添加删除节点源码分析

上面讲的是一种特殊的红黑树——左倾红黑树。但是红黑树不一定全是左倾红黑树，也可以有右倾红黑树，也可以两个子节点都是红色，这意味着红黑树也可以与2-3-4树（包含2-，3-，4-节点）等价。

ngx_rbtree_t就是与2-3-4树等价的红黑树。

3.1 Nginx红黑树相关结构

结构图：

红黑树操作方法：

3.2 Nginx红黑树插入新节点

当创建一个红黑树或者向已有红黑树中插入新的数据时，需要3步：

• 由于红黑树本身是一棵二叉查找树，所以在插入新的结点时，完全按照二叉查找树插入结点的方法，找到新结点插入的位置；

• 将新插入的结点结点初始化，颜色设置为红色后插入到指定位置；（将新结点初始化为红色插入后，不会破坏红黑树第 5 条的性质）

• 由于插入新的结点，可能会破坏红黑树第 4 条的性质（若其父结点颜色为红色，就破坏了红黑树的性质），此时需要调整二叉查找树，想办法通过旋转以及修改树中结点的颜色，使其重新成为红黑树。

插入结点的第 1 步和第 2 步都非常简单，最后一步复杂，在红黑树中插入结点时，根据插入位置的不同可分为以下 3 种情况：

1. 插入位置为整棵树的树根。

   处理方法：根节点为黑色。

2. 插入位置的父节点的颜色为黑色。

   处理方法：此种情况不需要做任何工作，新插入的颜色为红色的结点不会破坏红黑树的性质。

3. 插入位置的父节点的颜色为红色。

   处理方法：由于插入结点颜色为红色，其双亲结点也为红色，破坏了红黑树第 4 条性质，此时需要结合其祖父结点和祖父结点的另一个孩子结点（此处称为“叔叔结点”）的状态，分为 3 种情况讨论:

• 当前结点的父节点是红色，且“叔叔结点”也是红色：破坏了红黑树的第 4 条性质，解决方案为：将父结点颜色改为黑色；将叔叔结点颜色改为黑色；将祖父结点颜色改为红色；下一步将祖父结点认做当前结点（也就是继续向上融合，类比2-3树），继续判断，处理结果如下图所示：

分析 ： 此种情况下，由于父结点和当前结点颜色都是红色，所以为了不产生冲突，将父结点的颜色改为黑色。但是虽避免了破坏第 4 条，但是却导致该条路径上的黑高度增加了 1 ，破坏了第 5 条性质。但是在将祖父结点颜色改为红色、叔叔结点颜色改为黑色后，该部分子树没有破坏第 5 条性质。但是由于将祖父结点的颜色改变，还需判断是否破坏了上层树的结构，所以需要将祖父结点看做当前结点，继续判断。

• 当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的右孩子。解决方案：将父结点作为当前结点做左旋操作。

提示： 在进行以父结点为当前结点的左旋操作后，此种情况就转变成了第 3 种情况，处理过程跟第 3 种情况同步进行。

• 当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的左孩子。解决方案：将父结点颜色改为黑色，祖父结点颜色改为红色，从祖父结点处进行右旋处理。如下图所示：

分析 ：在此种情况下，由于当前结点 F 和父结点 S 颜色都为红色，违背了红黑树的性质 4，此时可以将 S 颜色改为黑色，有违反了性质 5，因为所有通过 S 的路径其黑高度都增加了 1 ，所以需要将其祖父结点颜色设为红色后紧接一个右旋，这样这部分子树有成为了红黑树。（上图中的有图虽看似不是红黑树，但是只是整棵树的一部分，以 S 为根结点的子树一定是一棵红黑树）

3.3 Nginx红黑树删除新节点

在红黑树中删除结点，思路更简单，只需要完成 2 步操作：

1. 将红黑树按照二叉查找树删除结点的方法删除指定结点；

2. 重新调整删除结点后的树，使之重新成为红黑树；（还是通过旋转和重新着色的方式进行调整）

在二叉查找树删除结点时，分为 3 种情况：

• 若该删除结点本身是叶子结点，则可以直接删除；

• 若只有一个孩子结点（左孩子或者右孩子），则直接让其孩子结点顶替该删除结点；

• 若有两个孩子结点，则找到该结点的右子树中值最小的叶子结点( 左 子树最大也可以 )来顶替该结点，然后删除这个值最小的叶子结点。

以上三种情况最终都需要删除某个结点，此时需要判断删除该结点是否会破坏红黑树的性质。判断的依据是：

1.如果删除结点的颜色为红色，则不会破坏；

2.如果删除结点的颜色为黑色，则肯定会破坏红黑树的第 5 条性质，此时就需要对树进行调整，调整方案分 4 种情况讨论：

• 删除结点的兄弟结点颜色是红色，调整措施为：将兄弟结点颜色改为黑色，父亲结点改为红色，以父亲结点来进行左旋操作，同时更新删除结点的兄弟结点（左旋后兄弟结点发生了变化），如下图所示：

  

• 删除结点的兄弟结点及其孩子全部都是黑色的，调整措施为：将删除结点的兄弟结点设为红色，同时设置删除结点的父结点标记为新的结点，继续判断；

  如下图所示：

  

• 删除结点的兄弟结点是黑色，其左孩子是红色，右孩子是黑色。调整措施为：将兄弟结点设为红色，兄弟结点的左孩子结点设为黑色，以兄弟结点为准进行右旋操作，最终更新删除结点的兄弟结点；

  如下图所示:

  

• 删除结点的兄弟结点是黑色，其右孩子是红色（左孩子不管是什么颜色），调整措施为：将删除结点的父结点的颜色赋值给其兄弟结点，然后再设置父结点颜色为黑色，兄弟结点的右孩子结点为黑色，根据其父结点做左旋操作，最后设置替换删除结点的结点为根结点；

  如下图所示:

4.结尾

至此，我们就基本讲完了红黑树的基本原理和实现。  我们首先从2-3树开始讲起，然后引出(左倾)红黑树其实就是2-3树的BST（二叉搜索树）的表示。事实上左倾红黑树是定义的， 也可以有右倾红黑树，也可以左右子树都是红色节点，也就是与2-3-4树（同时可以有2-,3-,4-节点）等价， nginx中红黑树就是与 2-3-4树等价的， 接着介绍插入和删除算法了。

插入和删除难免会破坏红黑树的基本性质， 此时就需要 通过旋转和变色 ，使其重新成为一棵红黑树。

最后，如果你也在学习红黑树，希望这篇文章能够帮助到你。由于红黑树本身比较复杂，加之本人水平有限，难免会出一些错误。如果有错，还望大家指出来，我们共同讨论。

参考文献

• 《算法》第四版

• 红黑树 -- 维基百科

▼往期精彩回顾▼