汉扬编程 C语言入门 Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

上一节较为详细的讨论了普通二叉搜索树的局限性,在此基础上引出了红黑树的概念并介绍了其原理。在文章最后提到,为了维护一棵红黑树,在插入或者删除节点后,需要对二叉树做重着色和变换操作。那么,为什么要做重着色和变换操作呢?怎么做呢?本节将结合 linux 内核源代码讨论之。

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

为什么红黑树插入或者删除节点时,要重新调整树? 在回答这个问题之前,先来回顾一下红黑树的 5 条规则,要想保持一棵树始终是红黑树,就必须遵守这 5 条规则。

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

所有节点要么是红色,要么是黑色根节点必须是黑色所有叶子(NULL,or NIL)节点都是黑色的红色节点的两个子节点必须是黑色(不能有连续的红色节点)从根节点到任意叶子节点,黑色节点的数目是相等的 现在设想一下,如果往树中插入的节点是红色的,并且它的父节点也是红色的,那不就与规则4冲突了吗?可能你会说,那我把插入的节点染成黑色,不就没这个问题了吗?的确,这样就不会违反规则4,但是它可能会违反规则5!而对于从树中“删除节点”的操作,只要删除的节点是黑色,它就会违反规则5。

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

因此,在往红黑树中插入新节点,或者从中删除节点时,非常有必要仔细检查一下是否需要对树做重着色和旋转变换操作。那么,如果需要,该怎么对树做“重着色”或者“旋转变换”呢?

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

先来看看往红黑树中插入新节点的情况 首先应该清楚,红黑树仍然是一棵二叉搜索树,所以往红黑树中插入新节点,把它当做一棵普通的二叉搜索树插入就可以了。然后再判断新树是否违反了红黑树的 5 条性质,是否需要做调整。

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

普通二叉搜索树节点的插入和删除操作,第 20 节文章已经介绍的比较清楚,感到陌生的朋友可以过去看看。 插入新节点后,首先要为新节点染色(规则1)。Linux 内核默认新节点是红色,为什么不是黑色呢?这是因为新节点是红色时,需要考虑的情况比较少,较容易作调整。

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

我们假设插入的节点不是根节点,那么新插入的红色节点显然不会违反红黑树的规则1、规则2、规则3、规则5,唯一可能会违反的只有规则4。 那么,如何作调整,才能确保插入新节点的二叉树仍然是一棵红黑树呢?来看看 Linux 内核源代码是怎么实现的吧。内核的红黑树时用到的数据结构的 C语言代码如下,请看:

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

100 struct rb_node – 101 { | 102 unsigned long rb_parent_color;| 103 #define RB_RED 0| 104 #define RB_BLACK 1| 105 struct rb_node *rb_right;| 106 struct rb_node *rb_left;| 107 } __attribute__((aligned(sizeof(long)))); 108 /* The alignment might seem pointless, but allegedly CRIS needs it */ 109 110 struct rb_root – 111 { | 112 struct rb_node *rb_node;| 113 };

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

其中 rb_parent_color 成员不仅记录节点的颜色,也负责记录父节点地址,请看下面的 C语言代码:

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

116 #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) 117 #define rb_color(r) ((r)->rb_parent_color & 1) 118 #define rb_is_red(r) (!rb_color(r)) 119 #define rb_is_black(r) rb_color(r)- 120 #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)- 121 #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

显然,rb_parent_color 的最低位记录着节点的颜色,除低 2 位的其他位则负责记录父节点地址。Linux 内核在往红黑树插入新节点后,负责检查,以及做重着色和旋转变换的是 rb_insert_color() 函数。

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

下面为了方便,将新插入的节点用 N 表示,它的父节点用 P 表示,祖父节点(父节点的父节点)用 G 表示,叔叔节点(祖父节点的另一个子节点)用 U 表示。P 可能是 G 的左儿子,也有可能是 G 的右儿子,但这两种情况是对称的,下面仅详细分析 P 是 G 的左儿子的情况。

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

当 U 是红色的时候,如下图(白色表示不关心节点的颜色):

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

Linux学习第22节,超详细多图文章,5分钟彻底弄懂红黑树

这时 N 违反了规则4,应想办法解决之。内核的解决办法是:把 U 和 P 染成黑色,再把 G 染成红色。这样虽然在局部解决了问题,但是如果把 G 看作是新插入的节点,它可能也会违反规则,所以要返回到程序开头,重新处理。请看下面的C语言代码:

继续分析,如果 U 是黑色并且 N 是 P 的右儿子,如下图:

这时就没法简单的交换颜色解决冲突了,内核采取的解决办法是先以 P 为指点做左旋转,请看下图C语言代码:

然后再将 P 染成黑色,G 染成红色,最后再以 G 为支点做右旋转,就解决了所有冲突,如下图,现在红黑树就仍然是一棵红黑树了。

关于“左旋转”和“右旋转”可参考上一节的文章。 需要说明的是,这些操作步骤都是递归的,解决问题的关键思路就是先解决局部问题,让局部称为一棵红黑树,把违反规则的部分逐层往上推,一直推到根节点。到根节点就好办了,直接把它染成黑色即可。

从红黑树删除一个节点,Linux 内核如何做调整,以继续维持一棵红黑树呢? 要从红黑树删除节点,首先仍然是把它当做一棵普通的二叉搜索树。在第 20 节我们详细讨论过,如果要删除的节点至多只有一个子树,那么直接把它的子树挂到它的父节点上就可以了。

如果要删除的节点有两个子树呢?Linux 内核采取的方法和第 20 节介绍的方法是类似的:都是选择一个替代节点。替代节点要么在要删除节点的左子树的最右边,要么在要删除节点右子树的最左边,无论如何,替代节点都至多只有一个子树。这种情况下,使用替代节点的值替换要删除节点的值,实际上,真正要删除的是“替代节点”。

这就清楚了,当从红黑树中删除节点时,Linux 内核采取的方法巧妙的保证了要删除节点至多只有一个子树。为了方便,我们仍然把要删除节点用 N 表示,它的兄弟节点(父节点的另一个子节点)用O表示,父节点用 P 表示,祖父节点用 G 表示。

如果 N 是黑色,那么它显然很可能至少会违反红黑树的规则5。那么怎么解决这种冲突呢?来看看 Linux 内核源代码是怎么解决的。内核中负责检查,以及调整删除节点后的红黑树的是 __rb_erase_color() 函数,它的C语言代码如下:

和插入新节点一样,N 可能是 P 的左儿子,也有可能是 P 的右儿子,因为这两种情况完全对称,所以这里只详细分析 N 是 P 左儿子的情况。

如果 O 是红色的,那么 P 必定是黑色的,如下图:

这种情况 Linux 内核先将 O 染成黑色,然后将 P 染成红色,再以 P 为支点坐旋转,请看C语言代码如下:

现在 O-P 这条线仍然少了一个黑色节点(违反规则5),所以需要继续变换。

如果 O 的两个儿子都是黑色,如下图:

直接将 O 染成红色,P 染成黑色,就解决了问题。

否则,如果 O 的右儿子是黑色,左儿子时红色,如下图:

内核首先把 O 的左儿子染成黑色,然后把 O 染成红色,再以 O 为支点右旋,接着把 P 的右儿子当作 O,继续进一步操作。请看C语言代码如下:

接着,内核把 O 染成 P 的颜色,把 P 和 O 的右儿子染成黑色,在以 P 为支点左旋。这样就解决了所有冲突,二叉树就又是红黑树了。

总结 至此,我们就分析完 Linux 内核关于红黑树调整部分的源代码了。可以看出,维护一棵红黑树其实并不是特别难,往树中插入新节点,或者从树中删除节点,完全可以先把其当作是一棵普通的二叉搜索树,之后再重新调整就可以了。这一过程是不是很像魔方?插入和删除操作可能会将魔方打乱,不过之后再变换,就又能把魔方还原了。

欢迎在评论区一起讨论,质疑。文章都是手打原创,每天最浅显的介绍C语言、linux等嵌入式开发,喜欢我的文章就关注一波吧,可以看到最新更新和之前的文章哦。

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6554.html

五分钟搞懂什么是红黑树(全程图解)

初入C语言江湖,才发现无法自拔

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部