#include
#include
#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 { 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) {