#include <stdio.h>
#include <stdlib.h>
#define COUNT 10000
#define RAND (4*COUNT)
int error_label=0;
#pragma pack(1)
typedef enum _color
{
RED,
BLACK
}color;
typedef struct _data
{
int value;
}data;
typedef struct _redblack
{
color m_color;
int m_data;
struct _redblack *parent;
struct _redblack *left;
struct _redblack *right;
}redblack;
typedef struct _wrapredblack
{
struct _wrapredblack *next;
redblack real;
}wrapredblack;
typedef struct _wrapdata
{
redblack *root;
int size;
}wrapdata;
#pragma pack()
wrapredblack global[2*RAND];
wrapredblack *head;
wrapredblack *tail;
wrapdata *global_node;
void init( )
{
int i,j;
for(i=0;i<RAND-1;i++)
{
global[i].next=&global[i+1];
}
head=&global[0];
tail=&global[RAND-1];
}
redblack *mycalloc ( )
{
redblack *temp=&head->real;
head=head->next;
return temp;
// return (redblack *) calloc (1 ,sizeof (redblack));
}
int checkvalid ( redblack *del,redblack *root)
{
if(!root)
{
return 0;
}
else
{
if(checkvalid(del,root->left))
{
return 1;
}
if(checkvalid (del,root->right))
{
return 1;
}
if (root==del)
{
return 1;
}
else
{
return 0;
}
}
}
void myfree (redblack *node)
{
wrapredblack *temp = (wrapredblack *)( (int)node-4);
temp->next=0;
node->left=node->right=node->parent=0;
tail->next=temp;
tail=temp;
if(checkvalid (node,global_node->root))
{
exit(0);
}
return ;
}
int compare ( int data ,redblack *right)
{
if(data > right->m_data)
{
return 1;
}
else if(data == right->m_data)
{
return -1;
}
else
{
return 0;
}
}
redblack * newstruct ( int value)
{
redblack *newnode;
newnode=(redblack *)mycalloc ();
newnode->m_color=RED;
newnode->m_data =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;
}
int mid_print (redblack *root,int level)
{
int left,right;
if(level>40)
{
printf("error\n");
error_label=1;
return 100000 ;
}
if (!root)
{
return 0;
}
else
{
left=mid_print (root ->left,level+1);
printf("{address=%x color=%s,level=%d ,value=%d} ",root ,root->m_color==RED?"red":"black",level ,root->m_data);
// printf(" %d ",root->m_data->value);
right= mid_print (root ->right,level+1);
return left+right+1;
}
}
int check (redblack *root)
{
int left,right;
if (!root)
{
return 0;
}
else
{
left=check (root ->left);
right= check (root ->right);
if(left||right)
{
return 1;
}
if( root->left && ( root->left->m_data > root->m_data || root->left->parent!=root) )
{
return 1;
}
if( root->right && ( root->right->m_data < root->m_data || root->right->parent!=root))
{
return 1;
}
else
{
return 0;
}
}
}
void left_print (redblack *root)
{
if (!root)
{
return;
}
else
{
printf("%d ",root->m_data);
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);
}
}
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 );
tmp=parent;
parent=curnode;
curnode=tmp;
curnode->m_color=BLACK;
rotate_left (grandparent ,parent );
curnode=parent;
parent=curnode->parent;
if(!parent )
{
node->root=curnode;
break;
}
}
}
else
{
if ( parent== grandparent->right)
{
curnode->m_color=BLACK;
rotate_left (grandparent,parent );
curnode=parent;
parent=curnode->parent;
if(!parent )
{
node->root=curnode;
break;
}
}
else
{
// printf("nothing");
rotate_left ( parent ,curnode);
tmp=parent;
parent=curnode;
curnode=tmp;
curnode->m_color=BLACK;
rotate_right (parent,grandparent );
curnode=parent;
parent=curnode->parent;
if(!parent )
{
node->root=curnode;
break;
}
}
}
}
}
redblack * find(redblack *root ,int data)
{
if (! root)
{
return NULL;
}
else
{
if ( data == root->m_data)
{
return root;
}
else if ( data > root->m_data)
{
return find (root ->right ,data);
}
else
{
return find (root->left ,data );
}
}
}
redblack * next (redblack * mostleft)
{
// if
if(! mostleft->left)
{
return mostleft;
}
else
{
return next ( mostleft->left);
}
}
void delete_fixup (wrapdata *node, redblack *curnode ,int mode)
{
redblack *parent;
redblack *uncle;
redblack *uncle_left;
redblack *uncle_right;
while(1)
{
if (curnode->m_color==RED)
{
curnode->m_color=BLACK;
parent=curnode->parent;
if(!parent)
{
node->root=curnode;
}
return ;
}
else
{
parent=curnode->parent;
if(!parent)
{
node->root=curnode;
return ;
}
if(0==mode)
{
uncle=parent->right;
if(!uncle)
{
return ;
}
if (uncle->m_color== RED)
{
uncle->m_color=BLACK;
parent->m_color=RED;
rotate_left (parent,uncle );
if (!uncle->parent)
{
node->root=uncle;
}
}
else
{
uncle_left=uncle->left;
uncle_right=uncle->right;
if( (!uncle_left || uncle_left->m_color==BLACK )
&&
(!uncle_right || uncle_right->m_color==BLACK))
{
uncle->m_color=RED;
curnode=parent;
}
else
{
if( !uncle_right || (uncle_right&& uncle_right->m_color==RED))
{
uncle->m_color=parent->m_color;
parent->m_color=BLACK;
if(uncle_right)
{
uncle_right->m_color=BLACK;
}
rotate_left( parent,uncle);
if (!uncle->parent)
{
node->root=uncle;
}
return ;
}
else
{
uncle_left->m_color=BLACK;
uncle->m_color=RED;
rotate_right(uncle_left,uncle);
uncle=parent->right;
uncle->right=uncle->right;
uncle->m_color=parent->m_color;
parent->m_color=BLACK;
uncle_right->m_color=BLACK;
rotate_left( parent,uncle);
if (!uncle->parent)
{
node->root=uncle;
}
return ;
}
}
}
}
else
{
uncle=parent->left;
if(!uncle)
{
return ;
}
if (uncle->m_color== RED)
{
uncle->m_color=BLACK;
parent->m_color=RED;
rotate_right (uncle ,parent);
if (!uncle->parent)
{
node->root=uncle;
}
}
else
{
uncle_left=uncle->left;
uncle_right=uncle->right;
if( (!uncle_left || uncle_left->m_color==BLACK )
&&
(!uncle_right || uncle_right->m_color==BLACK))
{
uncle->m_color=RED;
curnode=parent;
}
else
{
if( !uncle_left || ( uncle_left && uncle_left->m_color==RED))
{
uncle->m_color=parent->m_color;
parent->m_color=BLACK;
if(uncle_left)
{
uncle_left->m_color=BLACK;
}
rotate_right( uncle , parent);
if (!uncle->parent)
{
node->root=uncle;
}
return ;
}
else
{
uncle->m_color=RED;
uncle_right->m_color=BLACK;
rotate_left( uncle ,uncle_right);
uncle=parent->left;
uncle_left=uncle->left;
uncle->m_color=parent->m_color;
parent->m_color=BLACK;
uncle_left->m_color=BLACK;
rotate_right( uncle , parent);
if (!uncle->parent)
{
node->root=uncle;
}
return ;
}
}
}
}
}
}
}
void delete (wrapdata *node ,int data)
{
redblack * drop;
redblack *suc;
redblack *curnode;
int value;
int mode;
if ( drop=find ( node->root ,data))
{
printf("will delete %d \n",data);
if(!drop->left && !drop->right )
{
if (!drop->parent)
{
myfree(drop);
node->root=0;
}
else
{
if (drop->parent->left==drop)
{
drop->parent->left=0;
}
else
{
drop->parent->right=0;
}
myfree (drop);
}
}
else if (!drop->right )
{
if(!drop ->parent)
{
node->root=drop->left;
}
else
{
if (drop->parent->left==drop)
{
drop->parent->left=drop->left;
mode=0;
}
else
{
drop->parent->right=drop->left;
mode=1;
}
}
curnode=drop->left;
curnode->parent=drop->parent;
myfree (drop);
delete_fixup (node, curnode,mode);
}
else
{
suc=next ( drop->right);
value=drop->m_data;
drop->m_data=suc->m_data;
suc->m_data=value;
if(suc->parent->left==suc)
{
mode=0;
}
else
{
mode=1;
}
if(!suc->right)
{
if(0==mode)
{
suc->parent->left=0;
}
else
{
suc->parent->right=0;
}
myfree(suc);
}
else
{
if(0==mode)
{
suc->parent->left=suc->right;
}
else
{
suc->parent->right=suc->right;
}
curnode=suc->right;
curnode->parent=suc->parent;
myfree(suc);
delete_fixup (node ,curnode,mode);
}
}
node->size--;
}
else
{
}
node->root->m_color=BLACK;
}
void insert ( wrapdata *node , int data )
{
redblack *newnode;
redblack *curnode;
int relation;
node->size++;
newnode=newstruct (data);
printf("will insert %x %d \n",newnode,data);
if ( ! node->root)
{
node->root= newnode;
}
else
{
curnode=node->root;
while(1)
{
relation=compare(data,curnode);
if(relation==-1)
{
node->size--;
myfree(newnode);
return ;
}
else
{
if ( relation==1)
{
if (!curnode->right)
{
curnode->right=newnode;
newnode->parent=curnode;
break;
}
else
{
curnode=curnode->right;
}
}
else
{
if (!curnode->left)
{
curnode->left=newnode;
newnode->parent=curnode;
break;
}
else
{
curnode=curnode->left;
}
}
}
}
insert_fixup ( node , newnode);
}
node->root->m_color=BLACK;
}
int main()
{
int i;
wrapdata *node;
data *newdata;
int count;
init();
srand(time(NULL));
node=(wrapdata*)calloc (1 ,sizeof (wrapdata));
global_node=node;
/*
int value[]={12,24,25,9,4,91,2,100,98,95,93,96,99,120,13};
// int value[]={12,24,25,9,4,91,2};
node=(wrapdata*)calloc (1 ,sizeof (wrapdata));
for (i=0;i<sizeof (value)/sizeof(int );i++)
{
insert (node ,value[i]);
}
printf("%d \n",depth (node->root));
mid_print (node->root,0);
printf("\n");
while(1)
{
printf("into delete mode\n");
while( scanf("%d",&i) && i)
{
delete (node ,i);
printf("%d \n",depth (node->root));
mid_print (node->root,0);
printf("\n");
}
printf("into insert mode\n");
while( scanf("%d",&i) && i)
{
insert (node ,i);
printf("%d \n",depth (node->root));
mid_print (node->root,0);
printf("\n");
}
}
*/
while(1)
{
// printf("into insert mode\n");
while( node->size< COUNT)
{
i=rand()%RAND;
insert (node ,i);
count=check(node->root);
if(count)
{
// printf("\ncheck error\n");
mid_print(node->root,0);
return ;
}
count=mid_print (node->root,0);
if(count!=node->size)
{
// printf("\n %d %d \n",count ,node->size);
return ;
}
if(error_label)
{
return ;
}
if(node->size==COUNT*2/3)
{
printf("%d %d \n",node->size,depth (node->root));
}
}
// printf("into delete mode\n");
while( node->size> COUNT/2)
{
i=rand()%RAND;
delete (node ,i);
count=check(node->root);
if(count)
{
// printf("\ncheck error\n");
return ;
}
count=mid_print (node->root,0);
if(count!=node->size)
{
// printf("\n delete error %d %d \n",count ,node->size);
return ;
}
if(error_label)
{
return ;
}
if(node->size==COUNT*2/3)
{
printf("%d %d \n",node->size,depth (node->root));
}
}
}
return 0;
}
摘自 chenbingchenbing的專欄
