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

上一节较为详细的讨论了普通二叉搜索树的局限性，在此基础上引出了红黑树的概念并介绍了其原理。在文章最后提到，为了维护一棵红黑树，在插入或者删除节点后，需要对二叉树做重着色和变换操作。那么，为什么要做重着色和变换操作呢？怎么做呢？本节将结合 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 内核关于红黑树调整部分的源代码了。可以看出，维护一棵红黑树其实并不是特别难，往树中插入新节点，或者从树中删除节点，完全可以先把其当作是一棵普通的二叉搜索树，之后再重新调整就可以了。这一过程是不是很像魔方？插入和删除操作可能会将魔方打乱，不过之后再变换，就又能把魔方还原了。