红黑树的创建+线索化+性质检验+笔画输入法(二)
void right_rotate(RedBlackTree *t, RedBlackNode *x)
{
RedBlackNode * y = NULL;
y = x->left;
x->left = y->right;
if(y->right != NULL)
{
y->right->p = x;
}
y->p = x->p;
if(x->p == NULL)
{
*t = y;
}
else if(x == x->p->left)
{
x->p->left = y;
}
else
{
x->p->right = y;
}
y->right = x;
x->p = y;
}
void makeEmpty(RedBlackNode *t){
if(t != NULL){
makeEmpty(t->left);
makeEmpty(t->right);
free(t);
}
t = NULL;
}
void rb_insert(RedBlackTree *root, RedBlackNode *z)
{
RedBlackNode *x = NULL, *y = NULL;
y = NULL;
x = *root;
while(x != NULL)
{
y = x;
if(compare(x, z) == 0)
{
return;
}
else if(compare(x, z) > 0)
{
x = x->left;
}
else if(compare(x, z) < 0)
{
x = x->right;
}
}
z->p = y;
if(y == NULL)
{
*root = z;
}
else if(compare(y, z) == 0)
{
return;
}
else if(compare(y, z) > 0)
{
y->left = z;
}
else if(compare(y, z) < 0)
{
y->right = z;
}
z->left = NULL;
z->right = NULL;
z->color = Red;
rb_insert_fixup(root, z);
}
void pprint(RedBlackTree root, int i){
if(root){
if(root->p != NULL)
{
num = num > i num : i;}
pprint(root->left, i+1);
pprint(root->right, i+1);
}
}
int compare(RedBlackNode *y, RedBlackNode *z)
{
if(strlen(y->data.bihua) == strlen(z->data.bihua))
{
return strcmp(y->data.bihua, z->data.bihua);
}
return strlen(y->data.bihua) - strlen(z->data.bihua);
}
void rb_insert_fixup(RedBlackTree *root, RedBlackNode *z)
{
RedBlackNode *y = NULL;
while(z->p != NULL && z->p->color == Red)
{
if(z->p == z->p->p->left)
{
y = z->p->p->right;
if(y == NULL)
{
if( z == z->p->right)
{
z = z->p;
left_rotate(root, z);
z->p->color = Black;
z->p->p->color = Red;
right_rotate(root, z->p->p);
}
else if( z == z->p->left)
{
z->p->color = Black;
z->p->p->color = Red;
right_rotate(root, z->p->p);
return;
}
}
else
{
if(y->color == Red)
{
z->p->color = Black;
y->color = Black;
z->p->p->color = Red;
z = z->p->p;
}
else
{
if( z == z->p->right)
{
z = z->p;
left_rotate(root, z);
}
z->p->color = Black;
z->p->p->color = Red;
right_rotate(root, z->p->p);
}
}
}
else
{
y = z->p->p->left;
if(y == NULL)
{
if( z == z->p->right)
{
z->p->color = Black;
z->p->p->color = Red;