红黑树(RBTree)

经典的红黑树代码，插入的新节点为红色。然后再从父节点到根做颜色调整。先给出代码，我再做几张形象的图。

//红黑树的定义

struct  rb_node
{
    struct rb_node *rb_parent;
    int rb_color;
#define RB_RED 0
#define RB_BLACK 1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
};

//红黑树的旋转
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
    /*设置right*/
    struct rb_node *right = node->rb_right;
    /*把right的左子树赋给node的右子树*/
    if ((node->rb_right = right->rb_left))
    {
        right->rb_left->rb_parent = node;
    }
    right>rb_left = node;
    /*把node的父亲节点赋给right的父节点，并且判断是否为0*/
    if ((right->rb_parent = node->rb_parent))
    {
        if (node == node->rb_parent->rb_left)
        {
            node->rb_parent->rb_left = right;
        }
        else
        {
            node->rb_parent->rb_right = right;
        }
    }
    else
    {
        root->rb_node = right;
    }
    node->rb_parent = right
}

//红黑树的颜色调整
//红黑树的颜色插入函数主要完成红黑树的颜色调整，从而保持红黑树的原始特性，这些特性是保持红黑树为平衡树的基础
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *parent, *gparent;
    /*检查父节点的颜色是否为红色*/
    while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
    {
        gparent = parent->rb_parent;
        /*判断父节点是否是祖父节点的左节点*/
        if (parent == gparent->rb_left)
        {
            {
                register struct rb_node *uncle = gparent->rb_right;
                /*判断uncle节点是否为红色，并相应调整颜色*/
                if (uncle && uncle->rb_color == RB_RED)
                {
                    uncle->rb_color = RB_BLACK;
                    parent->rb_color = RB_BLACK;
                    gparent->rb_color = RB_RED;
                    node = gparent;
                    continue;
                }
            }
            if (parent->rb_right == node)
            {
                register struct rb_node *tmp;
                /*左旋*/
                __rb_rotate_left(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }
            parent->rb_color = RB_BLACK;
            gparent->rb_color = RB_RED;
            /*右旋*/
            __rb_rotate_right(gparent, root);
        }
        else /*else部分与前面对称*/
        {
            {
                register struct rb_node *uncle = gparent->rb_left;
                if (uncle && uncle->rb_color == RB_RED)
                {
                    uncle->rb_color = RB_BLACK;
                    parent->rb_color = RB_BLACK;
                    gparent->rb_color = RB_RED;
                    node = gparent;
                    continue;
                }
            }
            if (parent->rb_left == node)
            {
                register struct rb_node *tmp;
                /*右旋*/
                __rb_rotate_right(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }
            parent->rb_color = RB_BLACK;
            gparent->rb_color = RB_RED;
            /*左旋*/
            __rb_rotate_left(gparent, root);
        }
    }
    root->rb_node->rb_color = RB_BLACK;
}

2010-11-29 22:41 发表于百度空间，今搬至CU。