红黑树(Red–black tree)是一种自平衡的二叉搜索树。一棵红黑树具有下列性质:

  1. 结点颜色要么是红色,要么是黑色
  2. 根节点是黑色
  3. 所有叶子结点(位于树最底层的NULL结点)都是黑色
  4. 红色结点的孩子必须是黑色
  5. 每个结点到以它为根的子树的所有叶节点的路径上都包含相同数目的黑结点

下图既是一棵红黑树:红黑树的例子

红黑树的这些性质保证了从根结点到最远叶节点的距离不超过它到最近叶结点的距离的两倍。它是怎么保证的呢?假设根结点到叶结点的最短路径上黑结点的个数为N,根据性质5,最长路径上的黑结点也是N;又根据性质4,不可能有两个连续的红结点,所以最长路径上的总结点数最多为2N(红黑交替)。这样也保证了插入、删除和查找操作的时间复杂度都是O(log n)。

为了保证它的这些性质,在修改红黑树时需要重新排列和重新染色。这可以通过对树进行旋转操作,修改指针和颜色达到目的。旋转分为左旋和右旋,下面来对它们分别进行介绍。

1、左旋

红黑树的左旋

以K为根做左旋时,它的右孩子P成为它的父结点,P的左孩子N成为K的右孩子。

2、右旋

红黑树的右旋

如左旋类似,以P为根做右旋时,P的左孩子K成为它的父结点,K的右孩子N成为P的左孩子。

现在来看红黑树在内核中的实现。

GCC支持很多属性,用来说明声明变量或函数的特殊性质,__attribute__是关键字。aligned指定了变量的对齐方式。__attribute__((aligned(sizeof(long))))也就是要求对象要以long的长度对齐。了解更多可以点这里

显然,树的根用 struct rb_root 结构表示,它的 struct rb_node 指向根结点。struct rb_node 的 rb_left 指向左孩子,rb_right 指向右孩子。

其实 struct rb_node 结构中还包含了一个指向父结点的指针,那就是 __rb_parent_color 成员,它是 unsigned long 类型,因为在所有系统中,指针的长度总是和 long 型的长度相同,虽然C语言本身不要求这点,但事实确实如此。int 的长度就不一定了,在32位系统中int型也是32位,但在64位系统中,int型还是32位。

结点的颜色也包含在 __rb_parent_color 中,因为颜色只有黑或红,所以用1位就可以保存这个信息,那就是这个成员的最后一位。因为 struct rb_node 结构一定是按4或8对齐的,所以最后两位一定是0,所以用最后一位保存这个信息不会破坏指针的信息。红色用0表示,黑色用1表示:

注意,颜色的定义在<rbtree_augmented.h>中而不是<rbtree.h>,<rbtree_augmented.h>提供了增强特性,用于实现在红黑树结点中添加附加信息。本篇暂不考虑它的用法,只考虑普通的红黑树实现。

为了获得指向父结点的指针,只需要把 __rb_parent_color 成员的最后两位还原成0即可:

取得结点的颜色也是类似的:

下面来看看红黑树里最主要的操作。

1、插入操作

首先考虑插入操作会破坏红黑树的哪些性质?

新插入的结点总是红色的,这也是为什么把 RB_RED 定义为0,新结点的指向父结点的指针的最后一位总是为0。另外,新插入的结点的初始位置总是最底层(不考虑NULL结点的叶子),调整位置时不断把它上移。

如果插入的结点是根结点,那就破坏的性质2。

如果插入的结点的父结点是红色,就破坏了性质4。

其他性质是不会被破坏的。

那么都有哪些情况会破坏这些性质呢?

我们不妨把正在处理的结点称为当前结点,待插入结点总是第一个当前结点,当前结点总是红色的,并且当前结点的两个子树都是满足所有性质的红黑树。

  1. 父结点是NULL,说明当前结点是根结点,只需要把它染成黑色即可
  2. 父结点是黑色,性质2和性质4显然没有被破坏。因为当前结点是红色的,所以性质5也没有被破坏
  3. 父结点是红色,并且父结点的父结点(祖父结点)的另一个结点(叔叔结点)是红色,显然破坏性质4。
  4. 父结点是红色,并且叔叔结点是黑色,当前结点是父结点的右孩子,同样破坏性质4。
  5. 父结点是红色,并且叔叔结点是黑色,当前结点是父结点的左孩子,同样破坏性质4。

接下来来看内核是如果处理各种情形的。rb_insert_color 执行插入操作。

它立即把任务交给 __rb_insert :

显然,它的第一个参数是待插入的结点,第二个参数的树根,但第三个参数并不直观,它其实是用在增强版本的插入操作中的,普通版本中 rb_insert_color 给 __rb_insert 传递的 dummy_rotate 其实什么都没做:

接着看 __rb_insert 函数。

矫正工作在一个while循环中进行。它首先处理的就是情况1和情况2。rb_set_parent_color 的作用是设置父结点指针和颜色:

gparent是当前结点的祖父结点,tmp是祖父结点的右结点。首先判断了父结点是否是祖父结点的右结点。父结点是祖父结点的左结点还是右结点的处理都是类似的,接下来分别是在父结点是祖父结点左结点的情况下,情况3、情况4和情况5的处理。

首先是情况3,如果祖父结点的另一个结点是红色,就将父结点和叔叔结点都染成黑色,这样已祖父结点为根的路径上的黑结点数还是相同的,并且以父结点和以叔叔结点为根的子树又都满足条件4,它们都是红黑树。然后把祖父结点设为当前结点并将其染成红色,使循环能够继续。下图是这种情况下的一个例子:

红黑树插入操作情况3

当前结点是10,调整后:

红黑树插入操作情况3调整后

当前结点为15,现在就是情况4,还不满足性质4,需要继续调整。接着看__rb_insert函数:

它处理的就是情况4,叔叔结点是黑色,当前结点是父结点的右孩子。if语句里面进行的先是旋转操作,然后调用 augment_rotate 函数,之前看到过,它其实没有做任何工作。注意if语句里面并没有continue语句,所以程序会继续向下执行,将 parent 设置为当前结点,将 tmp 设置为当前结点的右结点实际上是让接下来的程序像处理情况5一样继续执行。通过下图可以更直观的理解:

红黑树插入操作情况4调整后

情况4处理后一定是情况5,只是当前结点并没有改变,因为后面并不需要这个信息。但 parent 和 tmp 指针的指向和直接执行情况5是一样的。也就是说,如果当前结点是7,那么 parent 同样是15,tmp 同样是17。

继续看接下来的处理。前面4行做的是右旋操作,然后调用 __rb_rotate_set_parents 函数,它是旋转操作的协作函数:

显然,它的工作是将 new 的父结点指针和颜色设置为old的父结点和颜色,然后将old的父结点设置为new,并将颜色设置为 color。最后使得old的父结点指向正确的孩子,这个工作是 __rb_change_child 完成的。

经过这样的处理后一定是满足红黑树所有性质的。为什么呢?在 __rb_insert 中,给 __rb_rotate_set_parents 传递的 old 是 祖父结点,new 是父结点,color 是红色。以父结点为根的所有路径上黑结点的数目是相同的,以祖父结点的右孩子为根的所有路径上的黑结点的数目也是相同的。经过处理后的父结点成为祖父结点的父结点。祖父结点一定是黑色的,所以处理后的父结点一定是黑色的,处理后祖父结点(现在是父结点的右孩子)变为红色,所以此时性质4得到满足,而且现在父结点的右孩子(原祖父结点,红色)不影响以父结点为根的右子树上路径的黑结点个数(还是插入新结点前路径上黑结点的个数)。经过前面的分析知道,情况3和情况4的处理也不改变路径上黑结点的个数,改变路径上黑结点个数的只有情况1,但情况1处理完成后整个插入过程就结束了。所以无论处理情况5前是否处理过情况3或情况4,以父结点为根的左子树路径上黑结点的个数还是插入新结点前的路径上的黑结点的个数。所以以父结点为根的子树满足了性质5,是棵红黑树。整棵树的其他地方没有经过调整,所以整棵树满足所有性质。

下图表示了旋转后的结果:

红黑树插入操作情况5调整后

当前结点的父结点是祖父结点的右孩子的处理和父结点是祖父的左孩子的处理类似,这里就不再详细分析了。

2、删除操作

删除操作也可能破坏红黑树的性质,采取的措施无非就是重新染色和重排。以下面的红黑树为例分析内核代码。

红黑树删除操作

删除操作是 rb_erase 函数完成的:

__rb_erase_augmented 定义在<rbtree_augmented.h>中,作用是删除结点,并返回需要重新调整的结点,也就是前面所说的“当前结点”(实际上是“当前结点”的父结点,下面会有解释)。

struct rb_augment_callbacks 结构封装了几个函数,用于增强版本中:

rb_erase 传递的第三个参数dummy_callbacks就是我们先前见过的什么都没做的哑函数。

下面开始分析 __rb_erase_augmented 的实现:

if (!tmp) 判断的是待删除结点是否有左孩子。假如现在要删除结点13,它的左右结点都为NULL,if (!tmp) 的判断将通过。if 中前三行做的就是将待删除结点移出红黑树。if (child) 判断的是待删除结点是否有右孩子,所以它将执行语句2。如果待删除结点是红色的,说明删除它不会破坏性质4和性质5,所以不需要进行其他调整,rebalance 为NULL;否则,删除黑色结点必然破坏性质5,需要从其父结点重排,这就是语句2的含义。

如果待删除结点有右孩子,比如删除结点12,它有且仅有右孩子,在这种情况下,待删除结点一定是黑色的,它唯一的孩子一定是红色的,因为如果待删除结点是红色的,那么它的孩子一定是黑色的,而另一个孩子是NULL,必然违背性质5。这时会执行语句1,仅仅需要把它的孩子(结点13)染成黑色并调整孩子的父结点指针使其指向它的父结点即可满足性质4和性质5,这就是语句1的含义。下图表示了删除结点12的结果:

红黑树删除操作删除12

如果待删除结点只有左孩子,刚刚说过了,待删除结点一定是黑色,它的孩子一定是红色,处理也和处理只有右孩子的情况一样。比如删除结点24。

如果待删除结点有两个孩子,则选择它的右子树中的最小者作为继承者。这个继承者将被放到它的位置并且继承它的颜色,这样就保证只有经过它的右子树的路径上的黑结点数暂时改变,并且不会违背性质4。处理的第一步就是找到这个继承者:

做法很简单,如果它的右孩子没有左孩子,那么它的右孩子就是要找的继承者,否则顺着左边一直找到最小值。然后调整指针指向使树的结构不被破坏。

待删除结点的左子树将成为继承者的左子树,父结点将成为继承者的父结点。

child2 是继承者在原树中的右孩子。我们说过,继承者是待删除结点的右子树中最小的结点,所以它要么有且仅有右孩子,要么没有孩子。其实现在的情形和前面讨论的删除一个没有孩子或只有一个孩子的结点的情形是一样的。继承者继承待删除结点的颜色和位置,它被从原位置移出。所以这里 if (child2) 和前面 if (child) 处理的是一样的。

最后,函数返回需要调整的结点。

如果有需要调整的结点,rb_erase 就会调用 ____rb_erase_color 函数。

经过前面的调整,其实可以把现在的情况想象成删除了一个黑色的叶子结点,含这个结点的路径上的黑结点数比其他路径少1。传递给 ____rb_erase_color 的第一个参数是这个叶子结点的父结点。

while 循环里的处理也会区分当前结点是父结点的左孩子还是右孩子,差别不大,下面还是以左孩子为例来分析。

首先处理的是兄弟结点是红色的情况。父结点一定是黑色,以父结点为根进行左旋并将父结点和兄弟结点的颜色互换。这个操作没有改变路径上黑结点的总数。下图说明了这个过程:

红黑树删除操作情况1

注意,第一次迭代时结点N是NULL结点。

观察后发现,现在的情况就是兄弟结点是黑色的情况(当前结点还是N),所以把 sibling 指向 T 后继续。

如果兄弟结点的孩子要么不存在要么是黑结点(要么没有孩子,要么都是黑结点,因为兄弟结点已经是黑色的了,它不可能只有一个黑色的孩子,前面说过),把兄弟结点染红。兄弟结点变红后经过它的路径的黑结点数就少1,和当前结点所在的路径上的黑结点数相同。如果父结点是红色,那么把父结点染黑后,它们路径上的黑结点数就都增加1,满足性质5,退出。如果父结点是黑色的并且父结点不是根结点,那么经过父结点的路径上的黑结点说比其他路径上少1,把父结点设为当前结点,继续循环。

如果兄弟结点右孩子不存在或者是黑色,兄弟结点的左孩子是红色,就将兄弟结点为根右旋,父结点的颜色没有影响。下图说明了这个过程:

红黑树删除操作情况2

虽然违背了性质4和性质5,但经下面的调整后会满足所有性质:

这段代码不仅用于继续处理上面的结果,还可以用于处理兄弟结点的右孩子是红色的情况。它做的是左旋+染色。先看看上面的结果经过它的处理会变成什么样子:

红黑树删除操作情况3

我们说过,经过当前结点的路径上的黑结点数会比其他路径上少1,经过这样的调整后,从图中可以看到经过当前结点的路径上的黑结点数增加了1,满足性质5,调整完毕。

兄弟结点的右孩子是红色的情况,可以用下图表示,父结点的颜色和兄弟结点的左孩子的颜色对处理没有影响:

红黑树删除操作情况4

显然,经过当前结点的路径上的黑结点数增加了1,其他路径没有变,满足性质5,调整完毕。

当前结点是父结点右孩子的处理与它是左孩子的处理类似:

 

除了插入删除操作外,内核还提供了一些其他的通用接口。

rb_first 和 rb_last 分别获取最左边和最右边的结点,也就是最小值和最大值:

rb_next 用在中序遍历中,获取当前结点的下一个结点。

RB_EMPTY_NODE 是个宏,用于判断结点是否在红黑树中,而不是它是否为NULL。但判断根结点是否为空就是判断的它是否为NULL:

如果当前结点有右孩子,那么它的下一个结点一定在右子树的最左端。如果没有右孩子,它的左子树上的结点都比它小,如果当前结点是父结点的左孩子,那么父结点就是它的下一个结点;否则,需要顺着父结点方向向上,找到第一个是父结点的左孩子的结点,它的父结点就是当前结点的下一个结点。下图表示了这几种情况:

红黑树的下一个结点

图中结点P表示当前结点,N表示P的下一个结点。

寻找前一个结点和寻找下一个结点类似:

rb_next_postorder 用于后序遍历中寻找当前结点的下一个结点:

rb_left_deepest_node 用于获取以参数node为根的最左边的叶子结点。

rb_first_postorder 用于获取后序遍历的第一个结点:

结点的替换操作仅仅需要修改周围结点的指针指向,并将原结点的指针和颜色拷贝给新结点: