近期需要使用红黑树进行操作。此文目的只为巩固rbtree的一些概念和用法。代码原型为linux 中的rbtree

下图为一个红黑树视图。

 

红黑树的特性:
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点是没有显示出现的NIL节点，如上图]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

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

1. 左旋转：

                         

                 

          

2. 右旋转：

                  

            

 

linux中的节点定义如下：

struct rb_node
{
    unsigned long  rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root
{
    struct rb_node *rb_node;
};

这里 的节点需要注意有个小技，其中的parent和color为一个unsigned long变量.其实是将父节点的指针转换成了unsigned long，用于节点color的操作。衍生出了几个宏操作。如下：

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

rbtree的插入、删除操作除去根节点，其他的节点操作无外乎下面几种情况

                   C1： 新节点为左节点，叔叔节点为红色。

                   C2： 新节点为左节点，叔叔节点为黑色。

                   C3： 新节点为右节点， 叔叔节点为红色。

                   C4:   新节点为右节点， 叔叔节点为黑色。

其中C1和C3情形是一样的。所以我们可以将这两种情况看作一种情况,可以归纳为3种情况

         C1： 叔叔节点是红色节点；

         C2： 叔叔节点是黑色节点，新节点为右节点；

        C3： 叔叔节点是黑色节点，新节点为左节点；

下面以一个例子来说明rbtree的建立。

数列：30，94，78，77，71，34，83，63，44，54，18，81，82，2，99，8。下面分步来创建这个rbtree。

其中：实线为left，right指针，虚线为parent指针。

• 插入30.

       

• 插入94

  

• 插入78

p1: 将78节点插入94节点的左节点。此时78和94两个节点均是红节点。需要进行旋转操作。

p3: 此时以94节点为中心进行右旋操作，得到此图，此时调换parent和node指针，使得78节点为parent指针，将其设着色为black。

p4: 此图是以94节点为中心右旋操作后的示意图。此时注意指针的变化。

p5：此时以上图中gparent为中心进行左旋转。调整后的指针图。

p6: 调整最终的红黑树逻辑图。

• 插入77

• 插入71

图1: 插入节点71.此时节点为红色。而父节点77也为红色，冲突，需要进行调整

图2：展示各个指针位置；

图3：以77节点为圆心进行右旋转操作，此时71节点为parent，着色为黑。祖父节点为30.

图4：以祖父节点30为基点进行左旋转时的指针变化。

图5：以节点30为基点进行左旋转操作，得到的二叉树逻辑图。

图6：经过右旋转，左旋转之后的最终红黑树逻辑图。

• 插入34

图1：插入节点34，红色，各个指针指向情况

图2：设置各个节点颜色。

图3：调整后的最终红黑树逻辑图。

• 插入83

• 插入63

图1： 插入63节点；

图2： 不满足红黑树条件，需要调整，此时只需进行左旋转即可，各个指针标识情况。

图3： 左旋转操作完成后指针状况。

图4： 调整后的红黑树逻辑图。

• 插入44

图1： 查找节点44位置，插入节点44。

图2： 根据条件对节点着色，各个指针指向如图所示。

图3： 对节点进行循环设置（着色），各个指针如图所示；

图4： 对节点进行循环设置，发现此处需要以78节点为基准做右旋转操作。

图5：右旋转操作各个指针如图所示

图６：最终调整后的红黑树。

• 插入54

图1： 添加节点54；

图2：节点54添加后各个指针指向；

图3：以44节点为基点左旋转，此时54为子树的父节点。着色为黑；

图4：左旋转之后的红黑树逻辑图

图５：以63为基点进行右旋转，此时的各个指针指向；

图６：红黑树节点调整之后的状态。

• 插入18

• 插入82

图１：插入节点82，节点插入后指针情况；

图2：以94为基点进行右旋转之后指针情况；

图3： 调整后的红黑树逻辑图。

• 插入2

图1：添加节点2，添加后指针情况；

图2：以30节点为基点做右旋转，旋转后的指针情况；

图3：调整后的红黑树。

• 插入99

图1： 插入99节点到指定的位置；

图2： 对各个节点进行着色，循环查找红黑树节点，循环最后各个指针指向；

图3： 调整后的红黑树逻辑图；

• 插入8

图1： 插入节点8到指定的位置；

图2：各个指针指向情况；

图３：　调整后的红黑树逻辑图；

 

硬件设备： Intel(R) Xeon(R) CPU E31240 @ 3.30GHz， 8核    / 16GB

软件版本： Red Hat Enterprise Linux Server release 6.5 (Santiago)

节点数量	最终插入的节点数量	耗时
500000	316120	1.282145
1000000	632097	2.897626
2000000	1264239	6.672601
3000000	1895660	10.774129
4000000	2529317	14.982705
5000000	3161422	19.372358
6000000	3791715	23.919592
7000000	4424556	28.405057
8000000	5057952	33.098248