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);