C++ 技术中心

   :: 首页 :: 联系 ::  :: 管理
  160 Posts :: 0 Stories :: 87 Comments :: 0 Trackbacks

公告

郑重声明:本BLOG所发表的原创文章,作者保留一切权利。必须经过作者本人同意后方可转载,并注名作者(天空)和出处(CppBlog.com)。作者Email:coder@luckcoder.com

留言簿(27)

搜索

  •  

最新随笔

最新评论

评论排行榜

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

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<time.h>
#include 
<conio.h>
#include 
<map>
using namespace std;

typedef 
int key_t;
typedef 
int data_t;

typedef 
enum color_t
{
    RED 
= 0,
    BLACK 
= 1
}color_t;

typedef 
struct rb_node_t
{
    
struct rb_node_t *left, *right, *parent;
    key_t key;
    data_t data;
    color_t color;
}rb_node_t;

/* forward declaration */
rb_node_t
* rb_insert(key_t key, data_t data, rb_node_t* root);
rb_node_t
* rb_search(key_t key, rb_node_t* root);
rb_node_t
* rb_erase(key_t key, rb_node_t* root);

int tmpValue = 0;
int useCount = 0;


#define GetRdm(min, max) (rand()*((float)((max)-(min)))/(float)(RAND_MAX)+(min))

int main()
{
    
int i, count = 99999999;
    
int sizes = 10000000;
    key_t key;
    rb_node_t
* root = NULL, *node = NULL;
    
    map
<key_t,data_t> mapInfo;
    map
<key_t,data_t>::iterator iter;
    

    srand((unsigned 
int)time(NULL));
    
//插入测试
    for (i = 1; i < sizes; ++i)
    {
        key 
= GetRdm(0,10000)*GetRdm(0,10000)*GetRdm(0,10);
        
if(useCount==32768)
            srand((unsigned 
int)time(NULL));
        
        iter 
= mapInfo.find(key);
        root 
= rb_insert(key, i, root);
        
if(iter != mapInfo.end())
        {
            
if( tmpValue!= iter->second)
                printf(
"%d\n",i);
        }
        
else
        {
            mapInfo[key] 
= i;
        }
    }
    
    
//查找测试
    for(iter = mapInfo.begin();iter!=mapInfo.end();++iter)
    {
        node 
= rb_search(iter->first, root);
        
if(node==NULL )
        {
            printf(
"not find!\n");
        }
        
else if(node->data!=iter->second)
        {
            printf(
"value=%d!=%d\n",node->data,iter->second);
        }
    }
    
    
//删除测试
    for(iter = mapInfo.begin();iter!=mapInfo.end();++iter)
    {
        root 
= rb_erase(iter->first, root);
    }
    
    printf(
"[%d]end.\n",useCount);
    getch();
    
return 0;
}

static rb_node_t* rb_new_node(key_t key, data_t data)
{
    rb_node_t 
*node = (rb_node_t*)malloc(sizeof(struct rb_node_t));
    
++useCount;
    
if (!node)
    {
        printf(
"malloc error!\n");
        exit(
-1);
    }
    node
->key = key, node->data = data;

    
return node;
}

/*-----------------------------------------------------------
|   node           right
|   / \    ==>     / \
|   a  right     node  y
|       / \           / \
|       b  y         a   b
 -----------------------------------------------------------
*/
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root)
{
    rb_node_t
* right = node->right;

    
if ((node->right = right->left))
    {
        right
->left->parent = node;
    }
    right
->left = node;

    
if ((right->parent = node->parent))
    {
        
if (node == node->parent->right)
        {
            node
->parent->right = right;
        }
        
else
        {
            node
->parent->left = right;
        }
    }
    
else
    {
        root 
= right;
    }
    node
->parent = right;

    
return root;
}

/*-----------------------------------------------------------
|       node           left
|       / \            / \
|    left  y   ==>    a   node
|   / \               / \
|  a   b             b   y
-----------------------------------------------------------
*/
static rb_node_t* rb_rotate_right(rb_node_t* node, rb_node_t* root)
{
    rb_node_t
* left = node->left;

    
if ((node->left = left->right))
    {
        left
->right->parent = node;
    }
    left
->right = node;

    
if ((left->parent = node->parent))
    {
        
if (node == node->parent->right)
        {
            node
->parent->right = left;
        }
        
else
        {
            node
->parent->left = left;
        }
    }
    
else
    {
        root 
= left;
    }
    node
->parent = left;

    
return root;
}

static rb_node_t* rb_insert_rebalance(rb_node_t *node, rb_node_t *root)
{
    rb_node_t 
*parent, *gparent, *uncle, *tmp;

    
while ((parent = node->parent) && parent->color == RED)
    {
        gparent 
= parent->parent;

        
if (parent == gparent->left)
        {
            uncle 
= gparent->right;
            
if (uncle && uncle->color == RED)
            {
                uncle
->color = BLACK;
                parent
->color = BLACK;
                gparent
->color = RED;
                node 
= gparent;
            }
            
else
            {
                
if (parent->right == node)
                {
                    root 
= rb_rotate_left(parent, root);
                    tmp 
= parent;
                    parent 
= node;
                    node 
= tmp;
                }

                parent
->color = BLACK;
                gparent
->color = RED;
                root 
= rb_rotate_right(gparent, root);
            }
        }
        
else
        {
            uncle 
= gparent->left;
            
if (uncle && uncle->color == RED)
            {
                uncle
->color = BLACK;
                parent
->color = BLACK;
                gparent
->color = RED;
                node 
= gparent;
            }
            
else
            {
                
if (parent->left == node)
                {
                    root 
= rb_rotate_right(parent, root);
                    tmp 
= parent;
                    parent 
= node;
                    node 
= tmp;
                }

                parent
->color = BLACK;
                gparent
->color = RED;
                root 
= rb_rotate_left(gparent, root);
            }
        }
    }

    root
->color = BLACK;

    
return root;
}

static rb_node_t* rb_erase_rebalance(rb_node_t *node, rb_node_t *parent, rb_node_t *root)
{
    rb_node_t 
*other, *o_left, *o_right;

    
while ((!node || node->color == BLACK) && node != root)
    {
        
if (parent->left == node)
        {
            other 
= parent->right;
            
if (other->color == RED)
            {
                other
->color = BLACK;
                parent
->color = RED;
                root 
= rb_rotate_left(parent, root);
                other 
= parent->right;
            }
            
if ((!other->left || other->left->color == BLACK) &&
                (
!other->right || other->right->color == BLACK))
            {
                other
->color = RED;
                node 
= parent;
                parent 
= node->parent;
            }
            
else
            {
                
if (!other->right || other->right->color == BLACK)
                {
                    
if ((o_left = other->left))
                    {
                        o_left
->color = BLACK;
                    }
                    other
->color = RED;
                    root 
= rb_rotate_right(other, root);
                    other 
= parent->right;
                }
                other
->color = parent->color;
                parent
->color = BLACK;
                
if (other->right)
                {
                    other
->right->color = BLACK;
                }
                root 
= rb_rotate_left(parent, root);
                node 
= root;
                
break;
            }
        }
        
else
        {
            other 
= parent->left;
            
if (other->color == RED)
            {
                other
->color = BLACK;
                parent
->color = RED;
                root 
= rb_rotate_right(parent, root);
                other 
= parent->left;
            }
            
if ((!other->left || other->left->color == BLACK) &&
                (
!other->right || other->right->color == BLACK))
            {
                other
->color = RED;
                node 
= parent;
                parent 
= node->parent;
            }
            
else
            {
                
if (!other->left || other->left->color == BLACK)
                {
                    
if ((o_right = other->right))
                    {
                        o_right
->color = BLACK;
                    }
                    other
->color = RED;
                    root 
= rb_rotate_left(other, root);
                    other 
= parent->left;
                }
                other
->color = parent->color;
                parent
->color = BLACK;
                
if (other->left)
                {
                    other
->left->color = BLACK;
                }
                root 
= rb_rotate_right(parent, root);
                node 
= root;
                
break;
            }
        }
    }

    
if (node)
    {
        node
->color = BLACK;
    }

    
return root;
}

static rb_node_t* rb_search_auxiliary(key_t key, rb_node_t* root, rb_node_t** save)
{
    rb_node_t 
*node = root, *parent = NULL;
    
int ret;

    
while (node)
    {
        parent 
= node;
        ret 
= node->key - key;
        
if (0 < ret)
        {
            node 
= node->left;
        }
        
else if (0 > ret)
        {
            node 
= node->right;
        }
        
else
        {
            
return node;
        }
    }

    
if (save)
    {
        
*save = parent;
    }

    
return NULL;
}

rb_node_t
* rb_insert(key_t key, data_t data, rb_node_t* root)
{
    rb_node_t 
*parent = NULL, *node;

    parent 
= NULL;
    
if ((node = rb_search_auxiliary(key, root, &parent)))
    {
        tmpValue 
= node->data;
        
return root;
    }

    node 
= rb_new_node(key, data);
    node
->parent = parent;
    node
->left = node->right = NULL;
    node
->color = RED;

    
if (parent)
    {
        
if (parent->key > key)
        {
            parent
->left = node;
        }
        
else
        {
            parent
->right = node;
        }
    }
    
else
    {
        root 
= node;
    }

    
return rb_insert_rebalance(node, root);
}

rb_node_t
* rb_search(key_t key, rb_node_t* root)
 {
    
return rb_search_auxiliary(key, root, NULL);
}

rb_node_t
* rb_erase(key_t key, rb_node_t *root)
{
    rb_node_t 
*child, *parent, *old, *left, *node;
    color_t color;

    
if (!(node = rb_search_auxiliary(key, root, NULL)))
    {
        printf(
"key %d is not exist!\n");
        
return root;
    }

    old 
= node;

    
if (node->left && node->right)
    {
        node 
= node->right;
        
while ((left = node->left) != NULL)
        {
            node 
= left;
        }
        child 
= node->right;
        parent 
= node->parent;
        color 
= node->color;

        
if (child)
        {
            child
->parent = parent;
        }
        
if (parent)
        {
            
if (parent->left == node)
            {
                parent
->left = child;
            }
            
else
            {
                parent
->right = child;
            }
        }
        
else
        {
            root 
= child;
        }

        
if (node->parent == old)
        {
            parent 
= node;
        }

        node
->parent = old->parent;
        node
->color = old->color;
        node
->right = old->right;
        node
->left = old->left;

        
if (old->parent)
        {
            
if (old->parent->left == old)
            {
                old
->parent->left = node;
            }
            
else
            {
                old
->parent->right = node;
            }
        }
        
else
        {
            root 
= node;
        }

        old
->left->parent = node;
        
if (old->right)
        {
            old
->right->parent = node;
        }
    }
    
else
    {
        
if (!node->left)
        {
            child 
= node->right;
        }
        
else if (!node->right)
        {
            child 
= node->left;
        }
        parent 
= node->parent;
        color 
= node->color;

        
if (child)
        {
            child
->parent = parent;
        }
        
if (parent)
        {
            
if (parent->left == node)
            {
                parent
->left = child;
            }
            
else
            {
                parent
->right = child;
            }
        }
        
else
        {
            root 
= child;
        }
    }

    free(old);
    
--useCount;
    
if (color == BLACK)
    {
        root 
= rb_erase_rebalance(child, parent, root);
    }

    
return root;
}
posted on 2011-12-11 17:44 C++技术中心 阅读(1796) 评论(0)  编辑 收藏 引用 所属分类: C++ 基础

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