一般情况下还没有发现bug.
#include
#include
typedef enum _color
{
RED,
BLACK
}color;
typedef struct _data
{
int value;
}data;
typedef struct _redblack
{
color m_color;
data *m_data;
struct _redblack *parent;
struct _redblack *left;
struct _redblack *right;
}redblack;
typedef struct _wrapdata
{
redblack *root;
int size;
}wrapdata;
int compare ( redblack *left ,redblack *right)
{
if(left->m_data->value > right->m_data->value)
{
return 1;
}
else
{
return 0;
}
}
redblack * newstruct ( int value)
{
redblack *newnode;
newnode=(redblack *)calloc (1 ,sizeof (redblack));
newnode->m_color=RED;
newnode->m_data =(data *)calloc ( 1 ,sizeof (data ) );
newnode->m_data->value=value;
return newnode;
}
void rotate_right ( redblack * left ,redblack *right )
{
right->left=left->right;
if(left->right)
{
left->right->parent=right;
}
left->right=right;
left->parent=right->parent;
if(right->parent)
{
if(right->parent->left==right)
{
right->parent->left=left;
}
else
{
right->parent->right=left;
}
}
right->parent=left;
}
void rotate_left ( redblack * left ,redblack *right )
{
left->right=right->left;
if (right->left)
{
right->left->parent=left;
}
right->left=left;
right->parent=left->parent;
if(left->parent)
{
if(left->parent->right==left)
{
left->parent->right=right;
}
else
{
left->parent->left=right;
}
}
left->parent=right;
}
void mid_print (redblack *root,int level)
{
if (!root)
{
return;
}
else
{
mid_print (root ->left,level+1);
printf("{color=%s,level=%d ,value=%d} ",root->m_color==RED "red":"black",level ,root->m_data->value);
// printf(" %d ",root->m_data->value);
mid_print (root ->right,level+1);
}
}
void left_print (redblack *root)
{
if (!root)
{
return;
}
else
{
printf("%d ",root->m_data->value);
left_print (root ->left);
left_print (root ->right);
}
}
void right_print (redblack *root)
{
if (!root)
{
return;
}
else
{
right_print (root ->left);
right_print (root ->right);
printf("%d ",root->m_data->value);
}
}
int depth(redblack *root)
{
int left,right;
if (!root)
{
return 0;
}
else
{
left=depth(root->left);
right=depth(root->right);
return left>right ( left+1):(right+1);
}
}
void insert_fixup (wrapdata *node , redblack *newnode)
{
redblack *curnode;
redblack *parent;
redblack *grandparent;
redblack *tmp;
curnode=newnode;
parent=curnode->parent;
while( curnode->m_color==RED && parent ->m_color==RED)
{
grandparent=parent->parent;
if ( curnode == parent->left)
{
if ( parent == grandparent->left)
{
curnode->m_color=BLACK;
rotate_right ( parent , grandparent);
curnode=parent;
parent=curnode->parent;
if(!parent )
{
node->root=curnode;
break;
}
}
else
{
// printf("nothing");
rotate_right (curnode, parent );