浅谈红黑树

在学习linux内核进程调度时,发现CFS算法多次使用红黑树来组织可运行进程队列,并用其来查找进程。于是对红黑树究竟是怎样的产生了兴趣,这次就让我们来了解一下红黑树的原理和算法吧。
(Linux 内核红黑树的实现代码位于:lib/rbtree.c,同时头文件在 include/linux/rbtree.h 中,内核中很多模块都使用了红黑树,详细介绍参见内核文档 Documentation/rbtree.txt。)



R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它是一种自平衡二叉搜索树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

像所有二叉搜索树一样,红黑树允许有效的按顺序遍历(即:按照左根 - 右)顺序遍历它们的元素。从根到叶遍历的搜索时间结果,因此具有最小树高度的n个节点的平衡树导致O(log n)搜索时间。

★红黑树的特性:
(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。(这个规则有时被省略,由于根始终可以从红色变为黑色,反之亦然,因此它对分析的影响的不大)
(3)所有叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
(一些定义:从根到节点的黑色节点的数量是节点的黑色深度 ; 从根到叶的所有路径中的黑色节点的统一数量称为红黑树的黑色高度。)

注意:
 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

3347563.png
 

 

1.红黑树的基本操作
红黑树的基本操作是插入删除。在对红黑树进行插入或删除之后,都会用到旋转方法。插入或删除红黑树中的节点之后,红黑树就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转,可以使这颗树重新成为红黑树。简单点说,旋转的目的是让树保持红黑树的特性。
旋转包括两种:左旋 右旋
1.1左旋和右旋
19050093.png对x进行左旋,意味着将x变成一个左节点。
《算法导论》中左旋的伪代码:



19325981.png对y进行右旋,意味着将y变为右节点
伪代码如下:


 1.1.1 区分左旋和右旋

左旋示意图(以x为节点进行左旋):
19599606.png
 对x进行左旋,也就是将”x的右孩子“设为”x的父节点“。即,将 x变成了一个左节点(x成了为z的左孩子)。 因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”。

右旋示意图(以x为节点进行右旋):
19737074.png
 
对x进行右旋,意味着,将“x的左孩子”设为“x的父节点”;即,将 x变成了一个右节点(x成了为y的右孩子)。 因此,右旋中的“右”,意味着“被旋转的节点将变成一个右节点”。
 


1.2 插入
将一个节点插入到红黑树中,需要执行的步骤如下:

第一步: 将红黑树当作一颗二叉查找树,将节点插入。
      红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。
     那接下来,我们就来想方设法的旋转以及重新着色,使这颗树重新成为红黑树。

第二步:将插入的节点着色为”红色”。
      为什么着色成红色,而不是黑色呢?在这之前,我们需要重新温习一下红黑树的特性:
(1) 每个节点或者是黑色,或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点]
(4) 如果一个节点是红色的,则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
      将插入的节点着色为红色,不会违背”特性(5)”。少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。

第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。
      第二步中,将插入节点着色为”红色”之后,不会违背”特性(5)”。那它到底会违背哪些特性呢?
      对于”特性(1)”,显然不会违背了。因为我们已经将它涂成红色了。
      对于”特性(2)”,显然也不会违背。在第一步中,我们是将红黑树当作二叉查找树,然后执行的插入操作。而根据二叉查找数的特点,插入操作不会改变根节点。所以,根节点仍然是黑色。
      对于”特性(3)”,显然不会违背了。这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响。
      对于”特性(4)”,是有可能违背的。
      那接下来,想办法使之”满足特性(4)”,就可以将树重新构造成红黑树了。

插入操作的伪代码《算法导论》:
理解了RB-INSERT之后,接着对 RB-INSERT-FIXUP的伪代码进行说明:
根据被插入节点的父节点的情况,可以将”当节点z被着色为红色节点,并插入二叉树”划分为三种情况来处理。
① 情况说明:被插入的节点是根节点。
    处理方法:直接把此节点涂为黑色。

② 情况说明:被插入的节点的父节点是黑色。
    处理方法:什么也不需要做。节点被插入后,仍然是红黑树。

③ 情况说明:被插入的节点的父节点是红色。
    处理方法:那么,该情况与红黑树的“特性(5)”相冲突。这种情况下,被插入节点是一定存在非空祖父节点的;进一步的讲,被插入节点也一定存在叔叔节点(即使叔叔节点为空,我们也视之为存在,空节点本身就是黑色节点)。理解这点之后,我们依据”叔叔节点的情况”,将这种情况进一步划分为上面伪代码中的3种情况(Case)。
上面三种情况(Case)处理问题的核心思路都是:将红色的节点移到根节点;然后,将根节点设为黑色。接下来对这三种情况进行分析:
1.2.1 (case 1)叔叔是红色
当前被插入节点的父节点是红色,而该节点的祖父节点的另一个子节点(叔叔节点)也是红色。
对策处理:
(1)将“父节点”设为黑色。
(2) 将“叔叔节点”设为黑色。
(3) 将“祖父节点”设为“红色”。
(4) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

示意图:
20990652.png
“当前节点”和“父节点”都是红色,违背“特性(4)”。所以,将“父节点”设置“黑色”以解决这个问题。 
但是将“父节点”由“红色”变成“黑色”之后,违背了“特性(5)”:因为,包含“父节点”的分支的黑色节点的总数增加了1。  解决这个问题的办法是:将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”。
按照上面的步骤处理之后:当前节点、父节点、叔叔节点之间都不会违背红黑树特性,但祖父节点却不一定。若此时,祖父节点是根节点,直接将祖父节点设为“黑色”,那就完全解决这个问题了;若祖父节点不是根节点,那我们需要将“祖父节点”设为“新的当前节点”,接着对“新的当前节点”进行分析。

1.2.2 (case 2) 叔叔是黑色,且当前节点是右孩子
当前被插入节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子。
处理对策:
(1)将“父节点”作为“新的当前节点”。
(2)以“新的当前节点”作为支点进行左旋。

示意图:
21445894.png
被插入节点为“70”,此时将其父节点“60”设置为当前节点,并以其为支点进行左旋。 
根据处理红黑树的核心思想:将红色的节点移到根节点,然后将根节点设为黑色。也就是说:要不断地将破坏红黑树特性的红色节点上移。而当前节点是右孩子,也就是只要将其进行左旋来上移。


1.2.3 (case 3)叔叔是黑色,且当前节点是左孩子
当前被插入节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子。
处理对策:
(1)将“父节点”设为黑色。
(2)将”祖父节点“设为红色。
(3)以”祖父节点“为支点进行右旋。

示意图:
21958919.png
 首先当前节点和父节点都为红色,违背了“特性(4)”,于是将父节点设为黑色。这时又违反了“特性(5)”,所有经过父节点的分支的黑色节点的个数增加了1.为了解决这个问题,将祖父节点设置为红色,再以祖父节点为支点进行右旋就行了。
上面的进行Case 3处理之后,再将节点”120”当作当前节点,就变成了Case 2的情况。


1.3 删除
将红黑树内的某一个节点删除。需要执行的操作依次是:首先,将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除;然后,通过”旋转和重新着色”等一系列来修正该树,使之重新成为一棵红黑树。详细描述如下:

第一步:将红黑树当作一颗二叉查找树,将节点删除。
      这和”删除常规二叉查找树中删除节点的方法是一样的”。分3种情况:
      ① 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。
      ② 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。
      ③ 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给”被删除节点”之后,再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了,下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空,就意味着”该节点的后继节点”要么没有儿子,要么只有一个儿子。若没有儿子,则按”情况① “进行处理;若只有一个儿子,则按”情况② “进行处理。

第二步:通过”旋转和重新着色”等一系列来修正该树,使之重新成为一棵红黑树。
      因为第一步中删除节点之后,可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树,使之重新成为一棵红黑树。

删除操作的伪代码:
RB-DELETE-FIXUP()的伪代码:


通过RB-DELETE算法,我们知道:删除节点y之后,x占据了原来节点y的位置。 既然删除y(y是黑色),意味着减少一个黑色节点;那么,再在该位置上增加一个黑色即可。于是,当我们假设”x包含一个额外的黑色”,就正好弥补了”删除y所丢失的黑色节点”,也就不会违反”特性(5)”。
现在,x不仅包含它原本的颜色属性,x还包含一个额外的黑色。即x的颜色属性是”红+黑”或”黑+黑”,它违反了”特性(1)”。


RB-DELETE-FIXUP需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是:将x所包含的额外的黑色不断沿树上移(向根方向移动),直到出现下面的姿态:
a) x指向一个”红+黑”节点。此时,将x设为一个”黑”节点即可。
b) x指向根。此时,将x设为一个”黑”节点即可。
c) 非前面两种姿态。

将上面的姿态,可以概括为3种情况。
① 情况说明:x是“红+黑”节点。
    处理方法:直接把x设为黑色,结束。此时红黑树性质全部恢复。

② 情况说明:x是“黑+黑”节点,且x是根。
    处理方法:什么都不做,结束。此时红黑树性质全部恢复。

③ 情况说明:x是“黑+黑”节点,且x不是根。
    处理方法:这种情况又可以划分为下面4种情况(case)。
1.3.1 (case 1)x是“黑+黑”节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
处理方法:
(1)将x的兄弟节点设为黑色。
(2)将x的父节点设为红色
(3)对x的父节点继续左旋。
(4)左旋后,重新设置x的兄弟节点。

示意图:
24281711.png
 这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”,从而进行进一步的处理。
对x的父节点进行左旋;左旋后,为了保持红黑树特性,就需要在左旋前“将x的兄弟节点设为黑色”,同时“将x的父节点设为红色”;左旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。


1.3.2 (case 2) x是“黑+黑”节点,x的兄弟节点是黑色,x的1兄弟节点的俩个孩子1都是黑色
处理对策:
(1)将x的兄弟节点设为红色。
(2)设置x的父节点为”新的x节点“

示意图:
24496010.png
 这个情况的处理思想:是将“x中多余的一个黑色属性上移(往根方向移动)”。 
x是“黑+黑”节点,我们将x由“黑+黑”节点 变成 “黑”节点,多余的一个“黑”属性移到x的父节点中,即x的父节点多出了一个黑属性(若x的父节点原先是“黑”,则此时变成了“黑+黑”;若x的父节点原先时“红”,则此时变成了“红+黑”)。 此时,需要注意的是:所有经过x的分支中黑节点个数没变化;但是,所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)!为了解决这个问题,我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可,那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
      经过上面的步骤(将x的兄弟节点设为红色),多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”,直接将“新的x节点”设为黑色,即可完全解决该问题;若“新的x节点”是“黑+黑”,则需要对“新的x节点”进行进一步处理。


1.3.3 (case 3) x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的左孩子是红色,右孩子是黑色
处理对策:
(1)将x的兄弟节点的左孩子设为黑色
(2)将x的兄弟节点设为红色
(3)对x的兄弟节点进行右旋
(4)右旋后,重新设置x的兄弟节点

示意图:
24816576.png
 我们处理“Case 3”的目的是为了将“Case 3”进行转换,转换成“Case 4”,从而进行进一步的处理。
转换的方式是对x的兄弟节点进行右旋;为了保证右旋后,它仍然是红黑树,就需要在右旋前“将x的兄弟节点的左孩子设为黑色”,同时“将x的兄弟节点设为红色”;右旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。


1.3.4 (case 4) x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的右孩子是红色,兄弟节点的左孩子是任意颜色。
处理对策:
(1)将x的父节点的颜色赋值给x的兄弟节点。
(2)将x的父节点设为黑色
(3)将x的兄弟节点的右孩子设为黑色
(4)对x的父节点进行左旋
(5)设置x为根节点

示意图:
25080249.png
 我们处理“Case 4”的目的是:去掉x中额外的黑色,将x变成单独的黑色。处理的方式是“:进行颜色修改,然后对x的父节点进行左旋。
设置当前子节点为S,父节点为F,兄弟节点为B,兄弟节点的右孩子为BRS,左孩子为BLS。
我们要对F进行左旋。但在左旋前,我们需要调换F和B的颜色,并设置BRS为黑色。为什么需要这里处理呢?因为左旋后,F和BLS是父子关系,而我们已知BL是红色,如果F是红色,则违背了“特性(4)”;为了解决这一问题,我们将“F设置为黑色”。 
但是,F设置为黑色之后,为了保证满足“特性(5)”,即为了保证左旋之后:
      第一,“同时经过根节点和S的分支的黑色节点个数不变”。
            若满足“第一”,只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”,而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1;现在,只需将S由“黑+黑”变成单独的“黑”节点,即可满足“第一”。
      第二,“同时经过根节点和BLS的分支的黑色节点数不变”。
            若满足“第二”,只需要将“F的原始颜色”赋值给B即可。之前,我们已经将“F设置为黑色”(即,将B的颜色”黑色”,赋值给了F)。至此,我们算是调换了F和B的颜色。
      第三,“同时经过根节点和BRS的分支的黑色节点数不变”。
            在“第二”已经满足的情况下,若要满足“第三”,只需要将BRS设置为“黑色”即可。
经过,上面的处理之后。红黑树的特性全部得到的满足。接着,我们将x设为根节点,就可以跳出while循环(参考伪代码);即完成了全部处理。


参考:
关于红黑树在linux内核中的C实现可查看这篇博客:

```