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->value)
{
return root;
}
else if ( data > root->m_data->value )
{
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 www.2cto.com
{
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 );
}
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->m_color==RED)
{
uncle->m_color=parent->m_color;
parent->m_color=BLACK;
uncle_right->m_color=BLACK;
rotate_left( parent,uncle);
curnode=uncle;
}
}
}
}
else
{
uncle=parent->left;
if(!uncle)
{
return ;
}
if (uncle->m_color== RED)
{
uncle->m_color=BLACK;
parent->m_color=RED;
rotate_right (uncle ,parent);
}
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->m_color==RED)