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树等价的, 接着介绍插入和删除算法了。

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

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

参考文献

  • 《算法》第四版

  • 红黑树 -- 维基百科

▼往期精彩回顾▼

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章