那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

[算法]红黑树的实现代码(修订版)

2008-11-10补充---这份代码仍然是有问题的, 再次的修正版本在这里:
http://www.cppblog.com/converse/archive/2008/11/10/66530.html

在之前，我曾经给出过一份红黑树的实现代码，很多人提出异议，说是代码有问题，我曾经做过一些测试，貌似都没有出错，因为这份代码是在我学习红黑树之后很久才贴出来的，所以后来没有再仔细看这份代码。

最近，因为工作上的原因，我需要使用红黑树结构，本以为拿来那份代码稍加改动就可以了，没想到代码调试了很久都还有问题，于是，我决定重新补习红黑树的知识，仔细查看了原有的代码，才发现是有问题的，在这里，给出修正版本的代码，希望这次是没有错误:) 请大家原谅我的疏忽。

我就不在原来的页面修改那份代码了，只是在上面加上说明那份代码是有错误的。

/*-----------------------------------------------------------
    RB-Tree的插入和删除操作的实现算法
    参考资料:
    1) <<Introduction to algorithm>>
    2) <<STL源码剖析>>
    3) sgi-stl中stl_tree.h中的实现算法
    4) http://epaperpress.com/sortsearch/index.html
    5) http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html

    作者：李创 (http://www.cppblog.com/converse/)
    您可以自由的传播，修改这份代码，转载处请注明原作者

    红黑树的几个性质:
    1) 每个结点只有红和黑两种颜色
    2) 根结点是黑色的
    3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。 
    4) 如果一个结点是红色的,那么它的左右两个子结点的颜色是黑色的
    5) 对于每个结点而言,从这个结点到叶子结点的任何路径上的黑色结点
    的数目相同
-------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int KEY;

enum NODECOLOR
{
    BLACK        = 0,
    RED          = 1
};

typedef struct RBTree
{
    struct        RBTree *parent;
    struct      RBTree *left, *right;
    KEY            key;
    NODECOLOR   color;
}RBTree, *PRBTree;

PRBTree RB_InsertNode(PRBTree root, KEY key);
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z);

PRBTree RB_DeleteNode(PRBTree root, KEY key);
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x , PRBTree x_parent);

PRBTree Find_Node(PRBTree root, KEY key);
void    Left_Rotate(PRBTree A, PRBTree& root);
void    Right_Rotate(PRBTree A, PRBTree& root);
void    Mid_Visit(PRBTree T);
void    Mid_DeleteTree(PRBTree T);
void    Print_Node(PRBTree node);

/*-----------------------------------------------------------
|   A              B
|  / \    ==>     / \
| a   B           A  y
|    / \         / \
|    b  y        a  b
 -----------------------------------------------------------*/
void Left_Rotate(PRBTree A, PRBTree& root)
{       
    PRBTree B;
    B = A->right;

    A->right  = B->left;
    if (NULL != B->left)
        B->left->parent = A;
    B->parent = A->parent;

    // 这样三个判断连在一起避免了A->parent = NULL的情况
    if (A == root)
    {
        root = B;
    }
    else if (A == A->parent->left)
    {
        A->parent->left = B;
    }
    else
    {
        A->parent->right = B;
    }
    B->left          = A;
    A->parent = B;
}

/*-----------------------------------------------------------
|    A              B
|   / \            / \
|  B   y   ==>    a   A
| / \                / \
|a   b              b   y
-----------------------------------------------------------*/
void Right_Rotate(PRBTree A, PRBTree& root)
{
    PRBTree B;
    B = A->left;

    A->left   = B->right;
    if (NULL != B->right)
        B->right->parent = A;

    B->parent = A->parent;
    // 这样三个判断连在一起避免了A->parent = NULL的情况
    if (A == root)
    {
        root = B;
    }
    else if (A == A->parent->left)
    {
        A->parent->left = B;
    }
    else
    {
        A->parent->right = B;
    }
    A->parent = B;
    B->right  = A;
}

/*-----------------------------------------------------------
|        函数作用:查找key值对应的结点指针
|        输入参数:根节点root,待查找关键值key
|        返回参数:如果找到返回结点指针,否则返回NULL
-------------------------------------------------------------*/
PRBTree Find_Node(PRBTree root, KEY key)
{
    PRBTree x;

    // 找到key所在的node
    x = root;
    do
    {
        if (key == x->key)
            break;
        if (key < x->key)
        {
            if (NULL != x->left)
                x = x->left;
            else
                break;
        }
        else
        {
            if (NULL != x->right)
                x = x->right;
            else
                break;
        }
    } while (NULL != x);

    return x;
}

/*-----------------------------------------------------------
|        函数作用:在树中插入key值
|        输入参数:根节点root,待插入结点的关键值key
|        返回参数:根节点root
-------------------------------------------------------------*/
PRBTree RB_InsertNode(PRBTree root, KEY key)
{
    PRBTree x, y;

    PRBTree z;
    if (NULL == (z = (PRBTree)malloc(sizeof(RBTree))))
    {
        printf("Memory alloc error\n");
        return NULL;
    }
    z->key = key;

    // 得到z的父节点, 如果KEY已经存在就直接返回
    x = root, y = NULL;
    while (NULL != x)
    {
        y = x;
        if (key < x->key)
        {
            if (NULL != x->left)
            {
                x = x->left;
            }
            else
            {
                break;
            }
        }
        else if (key > x->key)
        {
            if (NULL != x->right)
            {
                x = x->right;
            }
            else
            {
                break;
            }
        }
        else
        {
            return root;   
        }
    }

    if (NULL == y || y->key > key)
    {
        if (NULL == y)
            root = z;
        else
            y->left = z;
    }
    else
    {
        y->right = z;
    }

    // 设置z的左右子树为空并且颜色是red，注意新插入的节点颜色都是red
    z->parent = y;   
    z->left = z->right = NULL;
    z->color = RED;

    // 对红黑树进行修正
    return RB_InsertNode_Fixup(root, z);
}

/*-----------------------------------------------------------
|        函数作用:对插入key值之后的树进行修正
|        输入参数:根节点root,插入的结点z
|        返回参数:根节点root
-------------------------------------------------------------*/
PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z)
{
    PRBTree y;
    while (root != z && RED == z->parent->color)        // 当z不是根同时父节点的颜色是red
    {
        if (z->parent == z->parent->parent->left)        // 父节点是祖父节点的左子树
        {
            y = z->parent->parent->right;                        // y为z的伯父节点
            if (NULL != y && RED == y->color)                // 伯父节点存在且颜色是red
            {
                z->parent->color = BLACK;                        // 更改z的父节点颜色是B
                y->color = BLACK;                                        // 更改z的伯父节点颜色是B
                z->parent->parent->color = RED;                // 更改z的祖父节点颜色是B
                z = z->parent->parent;                                // 更新z为它的祖父节点
            }
            else                                                                        // 无伯父节点或者伯父节点颜色是b
            {
                if (z == z->parent->right)                        // 如果新节点是父节点的右子树
                {
                    z = z->parent;
                    Left_Rotate(z, root);
                }
                z->parent->color = BLACK;                        // 改变父节点颜色是B
                z->parent->parent->color = RED;                // 改变祖父节点颜色是R
                Right_Rotate(z->parent->parent, root);
            }
        }
        else                                                                                // 父节点为祖父节点的右子树
        {
            y = z->parent->parent->left;                        // y为z的伯父节点
            if (NULL != y && RED == y->color)                // 如果y的颜色是red
            {
                z->parent->color = BLACK;                        // 更改父节点的颜色为B
                y->color = BLACK;                                        // 更改伯父节点的颜色是B
                z->parent->parent->color = RED;                // 更改祖父节点颜色是R
                z = z->parent->parent;                                // 更改z指向祖父节点
            }               
            else                                                                        // y不存在或者颜色是B
            {
                if (z == z->parent->left)                        // 如果是父节点的左子树
                {
                    z = z->parent;
                    Right_Rotate(z, root);
                }
                z->parent->color = BLACK;                        // 改变父节点的颜色是B
                z->parent->parent->color = RED;                // 改变祖父节点的颜色是RED
                Left_Rotate(z->parent->parent, root);
            }
        }
    } // while(RED == z->parent->color)

    // 根节点的颜色始终都是B
    root->color = BLACK;

    return root;
}

/*-----------------------------------------------------------
|        函数作用:在树中删除key值
|        输入参数:根节点root,待插入结点的关键值key
|        返回参数:根节点root
-------------------------------------------------------------*/
PRBTree RB_DeleteNode(PRBTree root, KEY key)
{
    PRBTree x, y, z, x_parent;

    // 首先查找需要删除的节点
    z = Find_Node(root, key);
    if (NULL == z)
        return root;

    y = z, x = NULL, x_parent = NULL;

    // y是x按照中序遍历树的后继
    if (NULL == y->left)
    {
        x = y->right;
    }
    else
    {
        if (NULL == y->right)
        {
            x = y->left;
        }
        else
        {
            y = y->right;
            while (NULL != y->left)
                y = y->left;
            x = y->right;
        }
    }

    if (y != z)
    {
        z->left->parent = y;
        y->left = z->left;
        if (y != z->right)
        {
            x_parent = y->parent;
            if (NULL != x)
                x->parent = y->parent;
            y->parent->left = x;
            y->right = z->right;
            z->right->parent = y;
        }
        else
        {
            x_parent = y;
        }
        if (root == z)
        {
            root = y;
        }
        else if (z == z->parent->left)
        {
            z->parent->left = y;
        }
        else
        {
            z->parent->right = y;
        }
        y->parent = z->parent;
        NODECOLOR color = y->color;
        y->color = z->color;
        z->color = color;
        y = z;
    }
    else
    {
        x_parent = y->parent;
        if (NULL != x)
            x->parent = y->parent;
        if (root == z)
        {
            root = y;
        }
        else if (z == z->parent->left)
        {
            z->parent->left = x;
        }
        else
        {
            z->parent->right = x;
        }

    }

    if (BLACK == y->color)
    {
        root = RB_DeleteNode_Fixup(root, x, x_parent);
    }
    free(y);

    return root;
}

/*-----------------------------------------------------------
|        函数作用:对删除key值之后的树进行修正
|        输入参数:根节点root,删除的结点的子结点x
|        返回参数:根节点root
-------------------------------------------------------------*/
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x, PRBTree x_parent)
{
    PRBTree w;

    while (x != root && (NULL == x || BLACK == x->color))
    {
        if (x == x_parent->left)                                                                // 如果x是左子树
        {
            w = x_parent->right;                                                                // w是x的兄弟结点
            if (RED == w->color)                                                                // 如果w的颜色是红色
            {
                w->color = BLACK;
                x_parent->color = RED;
                Left_Rotate(x_parent, root);
                w = x_parent->right;
            }
            if ((NULL == w->left  || BLACK == w->left->color) &&
                (NULL == w->right || BLACK == w->right->color))
            {
                w->color = RED;
                x = x_parent;
                x_parent = x_parent->parent;
            }
            else
            {
                if (NULL == w->right || BLACK == w->right->color)
                {
                    if (NULL != w->left)
                        w->left->color = BLACK;

                    w->color = RED;
                    Right_Rotate(w, root);
                    w = x_parent->right;
                }

                w->color = x_parent->color;
                x_parent->color = BLACK;
                if (NULL != w->right)
                    w->right->color  = BLACK;
                Left_Rotate(x->parent, root);
                break;
            }
        }
        else
        {
            w = x_parent->left;                                                                // w是x的兄弟结点

            if (RED == w->color)                                                                // 如果w的颜色是红色                                               
            {
                w->color = BLACK;
                x_parent->color = RED;
                Right_Rotate(x_parent, root);
                w = x_parent->left;
            }
            if ((NULL == w->left  || BLACK == w->left->color) &&
                (NULL == w->right || BLACK == w->right->color))
            {
                w->color = RED;
                x = x_parent;
                x_parent = x_parent->parent;
            }
            else
            {
                if (NULL == w->left || BLACK == w->left->color)
                {
                    if (NULL != w->right)
                        w->right->color = BLACK;

                    w->color = RED;
                    Left_Rotate(w, root);
                    w = x_parent->left;
                }

                w->color = x_parent->color;
                x_parent->color = BLACK;
                if (NULL != w->left)
                    w->left->color  = BLACK;
                Right_Rotate(x->parent, root);
                break;
            }
        }
    }

    x->color = BLACK;

    return root;
}

void Print_Node(PRBTree node)
{
    char* color[] = {"BLACK", "RED"};
    printf("Key = %d,\tcolor = %s", node->key, color[node->color]);
    if (NULL != node->parent)
        printf(",\tparent = %d", node->parent->key);
    if (NULL != node->left)
        printf(",\tleft = %d", node->left->key);
    if (NULL != node->right)
        printf(",\tright = %d", node->right->key);
    printf("\n");
}

// 中序遍历树, 加了一个判断, 如果输出的数据不满足序列关系就报错退出
void Mid_Visit(PRBTree T)
{
    if (NULL != T)
    {
        if (NULL != T->left)
        {
            if (T->left->key > T->key)
            {
                printf("wrong!\n");
                exit(-1);
            }
            Mid_Visit(T->left);
        }
        Print_Node(T);
        if (NULL != T->right)
        {
            if (T->right->key < T->key)
            {
                printf("wrong\n");
                exit(-1);
            }
            Mid_Visit(T->right);
        }
    }
}

// 中序删除树的各个节点
void Mid_DeleteTree(PRBTree T)
{
    if (NULL != T)
    {
        if (NULL != T->left)
            Mid_DeleteTree(T->left);
        PRBTree temp = T->right;
        free(T);
        T = NULL;
        if (NULL != temp)
            Mid_DeleteTree(temp);
    }
}

void Create_New_Array(int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        array[i] = rand() % 256;
    }
}

int main(int argc, char *argv[])
{
    srand(time(NULL));
    PRBTree root = NULL;
    int i;
    for (i = 0; i < 100000; i++)
    {
        root = RB_InsertNode(root, rand() % 10000);
    }

    Mid_Visit(root);

    // 删除整颗树
    Mid_DeleteTree(root);

    return 0;
}

posted on 2007-11-28 14:29 那谁 阅读(8479) 评论(10)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

pretty code, you can take reference of linux kernel rbtree:
http://lxr.linux.no/source/include/linux/rbtree.h
http://lxr.linux.no/source/lib/rbtree.c
2007-11-28 19:34 | 补考少年

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

不要抱着教科书上的经典不放了
去看看现在新的BBST吧
GOOGLE下“size balanced tree”
效率高 代码好写
2007-11-28 21:03 | winsty

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

怎么看代码都有问题,Find_Node,当找不到key的时候根本不能返回NULL值.
2008-02-06 00:24 | vvvvy

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

本人没测试过,不过怎么看都有错,建议改为:
PRBTree Find_Node(PRBTree root, KEY key)
{
PRBTree x;

// 找到key所在的node
x = root;
do
{
if (key == x->key)
break;
if (key < x->key)
{
x = x->left;
}
else
{
x = x->right;
}
} while (NULL != x);

return x;
}
2008-02-06 00:46 | vvvvy

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

为了自己学习实现red-black-tree, 我仔细研究过你这份代码.
经过调试发现里面还是有错误.
PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x, PRBTree x_parent)里传进来的参数x可能是NULL, 基于这一点,显然函数进去后
while (x != root && BLACK == x->color)的是有错误的.
参考了SGI STL,应改成while(x != root &&
(NULL ==x || BLACK ==x->color) ).
2008-08-01 10:39 | 何日丧

#  [算法]红黑树的实现代码(修订版)  回复  更多评论   

还是有错误的。
2008-09-28 17:33 | hello

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

@何日丧
感谢指出错误,已经修改,不过这个判断我改写成了:
while (x != root && (NULL == x || BLACK == x->color))
因为根据rbtree的定义,空结点的颜色也是黑色的,我在
http://lxr.linux.no/linux/lib/rbtree.c
中看里面的函数__rb_erase_color就是这么判断的.

2008-10-06 14:53 | 创

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

代码还是有问题，当插入几个树时构成的红黑树结构是不对的，还望指点！
2008-11-03 01:03 | rw

# re: [算法]红黑树的实现代码(修订版)[未登录]  回复  更多评论   

删除的时候有问题
2009-10-03 23:02 | noname

# re: [算法]红黑树的实现代码(修订版)  回复  更多评论   

@winsty
cqf神牛的那个?orz........
2009-10-06 21:02 | Vincent

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理