基于树的查找--------------红黑树(1)

         红黑树是平衡树的一种，在查找，插入，删除方面的性能都是

O(log(n))，所以应用也很广泛，比如说在linux内核中，内存管理中的vm_area_struct的组织就有一种红黑树的组织，还有普通进程的CFS调

度，该CFS运行队列就是一棵红黑树，可以很快找到要运行哪个进程。
-------------------------------------------------------------------------------------------
以下代码多数来自于2.6内核的include/linux/rbtree.h和/lib/rbtree.c文件。
 红黑树节点的定义：

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

内核中每个红黑树节点均包含5个域:
rb_right :右孩子节点指针。
rb_left  :左孩子节点指针。
rb_parent_color：该字段包含两个域，一个是parent，一个是color，

这点用的技巧就是内存对齐，此结构体的对齐系数是sizeof(long)=4，

故结构体的地址后两位均是0，故就可以使用这两位来标识该节点的颜色，

其实只需要一位即可。
数据域：内核中的一些数据结构都喜欢把数据域放在外面，

这样可以将结构封装和拓展。比如说链表，struct list_head {};也是把

数据域放在外面
--------------------------------------------------------------------------------------------

#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))

这个宏函数，就是从r这个节点中“解析”出r节点的父节点。使用的&运算，

将r节点中rb_parent_color中的前30位(后两位有一位是用来标识颜色的)

解析出来。

#define rb_color(r) ((r)->rb_parent_color & 1)

该宏函数，就是从r这个节点中“解析”出r节点的颜色，只有红和黑两种，

故只需要用一位来表示即可，这儿使用的是最后一位，故只需将最后一位

&出即可。
----------------------------------------------------------------------------------------------

#define rb_is_red(r) (!rb_color(r))
#define rb_is_black(r) rb_color(r)

此处两个宏用来判别该节点是红节点孩是黑节点。该信息在rb_parent_color

最后一位标识出，如果最后一位是1则表示是黑节点，最后一位是0则表示是

红节点。

#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)

该处两个宏函数，用来设置r节点为红节点还是黑节点。设置的方法就是

修改字段rb_parent_color的最后1位。
----------------------------------------------------------------------------------------------

123 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
124 {
125 rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
126 }

该函数将rb节点的父节点设置为p,设置起来也比较容易，将rb节点中的rb_parent_color字段的前30位赋值为p节点的前30位即可。
----------------------------------------------------------------------------------------------

354 /*
355 * This function returns the first node (in sort order) of the tree.
356 */
357 struct rb_node *rb_first(const struct rb_root *root)
358 {
359 struct rb_node *n;
360
361 n = root->rb_node;
362 if (!n)
363 return NULL;
364 while (n->rb_left)
365 n = n->rb_left;
366 return n;
367 }

该函数比较容易理解，就是求红黑树中最左边的一个节点，红黑树也是一

个排序树，最左节点也就是key值最小的一个节点。原理就是不断地往左往左。

370 struct rb_node *rb_last(const struct rb_root *root)
371 {
372 struct rb_node *n;
373
374 n = root->rb_node;
375 if (!n)
376 return NULL;
377 while (n->rb_right)
378 n = n->rb_right;
379 return n;
380 }

该函数与rb_first是对称的，该函数就是求红黑树最右节点，key值

最大的一个节点。不断往右往右即可。
----------------------------------------------------------------------------------------------
在红黑树的插入和删除中都要用到调整，其中调整就用到了旋转

(分左旋和右旋)。下面分析下原理。


左旋，以Y为轴，x逆时针旋转，Y的左子树交给X，作为X的右子树，

然后就是Y取代X的位置。

右旋，以X为轴，Y顺时针旋转，X的右子树交给Y，作为Y的左子树，

然后就是X取代Y的位置。
----------------------------------------------------------------------------------------------
左旋的代码实现：

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{   //node为要旋转的节点，就是下图中的X节点。
    struct rb_node *right = node->rb_right;//由node节点获取右节点
    struct rb_node *parent = rb_parent(node);//由node节点获取node节点的父节点，即图中的parent

    if ((node->rb_right = right->rb_left))//将right节点的左子树交给node节点，并判断左子树是否
        rb_set_parent(right->rb_left, node);//为空，注意这儿是赋值操作，不是判断相等。
       //然后把node设置为right->left的父节点。这地方有点“双向链表”的意思。父指向子，子也指向父。
    right->rb_left = node;//将node这整个子树作为right的左子树，这样就实现了旋转。
//--------------------------------------------------------------------------------------
    rb_set_parent(right, parent);//将right的父指针指向parent。取代node的位置。

    if (parent)//如果X不是根节点
    {
        if (node == parent->rb_left)//如果node原来是parent的左孩子
            parent->rb_left = right;//则将right设置为parent的左孩子。
        else
            parent->rb_right = right;//否则将right设置为parent的右孩子。
    }
    else //如果parent指针为空，说明X是根节点。
        root->rb_node = right;//然后就把right设置为根节点。
//----------------------------------------------------------------------------------------
    rb_set_parent(node, right);//让node的父指针指向right。
}

上面的没一次建立两个节点之间的连接都是双向的。比如要建立X-B之间的

连接，建立X-Y之间的连接，建立Y-P之间的连接。将其看做链表的话，都

是双向链表。

建立X-B之间的连接：

if ((node->rb_right = right->rb_left))

      rb_set_parent(right->rb_left, node); 

这个赋值操作node->rb_right = right->rb_left就建立了一次，如果左子树不为空，则再建立一次 

rb_set_parent(right->rb_left, node)

建立X-Y之间的连接：

right->rb_left = node; 

rb_set_parent(node, right);

建立Y-P之间的连接：

rb_set_parent(right, parent);

parent->rb_left = right;（或：parent->rb_right = right;或：root->rb_node = right;）

------------------------------------------------------------------------------------

右旋，和左旋是对称的，所有的思想和代码和左旋都差不多，所以不再详

细分析了。

static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *left = node->rb_left;
    struct rb_node *parent = rb_parent(node);

    if ((node->rb_left = left->rb_right))
        rb_set_parent(left->rb_right, node);
    left->rb_right = node;

    rb_set_parent(left, parent);

    if (parent)
    {
        if (node == parent->rb_right)
            parent->rb_right = left;
        else
            parent->rb_left = left;
    }
    else
        root->rb_node = left;
    rb_set_parent(node, left);
}

--------------------------------------------------------------------------------------
参考：http://wangcong.org/blog/archives/12