rnode->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;
}
}
}
}
}
void insert ( wrapdata *node , data *newdata )
{
redblack *newnode;
redblack *curnode;
newnode=newstruct (newdata);
node->size++;
if ( ! node->root)
{
node->root= newnode;
}
else
{
curnode=node->root;
while(1)
{
if ( compare ( newnode ,curnode))
{
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 value[]={12,24,25,9,4,91,2,100,29,888,10,22,5,11,111,7,13,1,99,222,98,17,8,55,44,33,21,77,199,2345,46,49,51,53,54,52,50,48,47,45,43,42,41,40,39,38,37,78,79,80,81,82,83,84,85};
node=(wrapdata*)calloc (1 ,sizeof (wrapdata));
for (i=0;i
{
newdata=(data *)calloc (1 ,sizeof (data));
newdata->value=value[i];
insert (node ,newdata);
} www.2cto.com
printf("%d \n",depth (node->root));
mid_print (node->root);
printf("\n");
left_print (node->root);
printf("\n");
right_print (node->root);
printf("\n");
return 0;
}
摘自 chenbingchenbing的专栏