return 0;
}
else
{
left=check (root ->left);
right= check (root ->right);
if(left||right)
{
return 1;
}
if( root->left && ( root->left->m_data > root->m_data || root->left->parent!=root) )
{
return 1;
}
if( root->right && ( root->right->m_data < root->m_data || root->right->parent!=root))
{
return 1;
}
else
{
return 0;
}
}
}
void left_print (redblack *root)
{
if (!root)
{
return;
}
else
{
printf("%d ",root->m_data);
left_print (root ->left);
left_print (root ->right);
}
}
void right_print (redblack *root)
{
if (!root)
{
return;
}
else
{
right_print (root ->left);
right_print (root ->right);
printf("%d ",root->m_data);
}
}
int depth(redblack *root)
{
int left,right;
if (!root)
{
return 0;
}
else
{
left=depth(root->left);
right=depth(root->right);
return left>right ( left+1):(right+1);
}
}
void insert_fixup (wrapdata *node , redblack *newnode)
{
redblack *curnode;
redblack *parent;
redblack *grandparent;
redblack *tmp;
curnode=newnode;
parent=curnode->parent;
while( curnode->m_color==RED && parent ->m_color==RED)
{
grandparent=parent->parent;
if ( curnode == parent->left)
{
if ( parent == grandparent->left)
{
curnode->m_color=BLACK;
rotate_right ( parent , grandparent);
curnode=parent;
parent=curnode->parent;
if(!parent )
{
node->root=curnode;
break;
}
}
else
{
// printf("nothing");
rotate_right (curnode, parent );
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)
{
return root;
}
else if ( data > root->m_data)
{
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