• 好好学习,天天向上~
  • 欢迎欢迎~

linux学习22,linux内核中的红黑树是怎样设计和使用C语言实现的?

linux笔记 lcc 22℃ 0评论

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

为什么红黑树插入或者删除节点时,要重新调整树?

在回答这个问题之前,先来回顾一下红黑树的 5 条规则,要想保持一棵树始终是红黑树,就必须遵守这 5 条规则。

  1. 所有节点要么是红色,要么是黑色
  2. 根节点必须是黑色
  3. 所有叶子(NULL,or NIL)节点都是黑色的
  4. 红色节点的两个子节点必须是黑色(不能有连续的红色节点)
  5. 从根节点到任意叶子节点,黑色节点的数目是相等的

现在设想一下,如果往树中插入的节点是红色的,并且它的父节点也是红色的,那不就与规则4冲突了吗?可能你会说,那我把插入的节点染成黑色,不就没这个问题了吗?的确,这样就不会违反规则4,但是它可能会违反规则5!而对于从树中“删除节点”的操作,只要删除的节点是黑色,它就会违反规则5

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

先来看看往红黑树中插入新节点的情况

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

普通二叉搜索树节点的插入和删除操作,第 20 节文章已经介绍的比较清楚,感到陌生的朋友可以过去看看。

插入新节点后,首先要为新节点染色(规则1)。Linux 内核默认新节点是红色,为什么不是黑色呢?这是因为新节点是红色时,需要考虑的情况比较少,较容易作调整。

我们假设插入的节点不是根节点,那么新插入的红色节点显然不会违反红黑树的规则1、规则2、规则3、规则5,唯一可能会违反的只有规则4

那么,如何作调整,才能确保插入新节点的二叉树仍然是一棵红黑树呢?来看看 Linux 内核源代码是怎么实现的吧。内核的红黑树时用到的数据结构的 C语言代码如下,请看:

    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 };


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

    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)


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

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

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

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


linux学习22,linux内核中的红黑树是怎样设计和使用C语言实现的? - 刘冲的博客(https://blog.popkx.com) 原创版权所有,转载请注明出处。
点赞 (0)分享 (0)
发表我的评论
取消评论
表情     4 + 7 = ? (必填)