ntf("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
{
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 (