#include<stdio.h>
#include<stdlib.h>
 
struct nod
{
    int x;
    int color;
    struct nod *left;
    struct nod *p;
    struct nod *right;
};
typedef struct nod node;
 
void insertfix(node *z);
node* delet(node *);
node* treesucc(node *);
void deletefix(node *);
node* find(node *t,int);
node *root,*nil;
int preorder(node *t);
int inorder(node *t);
int x;
 
 
node* make()
{
    node *a;
    a = (node *)malloc(sizeof(node));
    a->left = nil;
    a->right = nil;
    return a;
};
 
 
 
int main()
{
    node *trav;
    int n = 0,*a,i;
 
    nil = make();
    nil->x = 0;
    nil->color = 1;
    root = make();
    printf("Enter the root: ");
    scanf("%d",&root->x);
    root->p = nil;
    root->color = 1;
    inorder(root);
    printf("Enter  numbers\n-1 to stop\n");
    for(;;)
    {
	scanf("%d",&n);
	if(n == -1)
	    break;
	trav = root;
	for(;;)
	{
	    if(n < trav->x && trav->left != nil)
		trav=trav->left;
	    if(n > trav->x && trav->right != nil)
		trav = trav->right;
	    if(n == trav->x)
	    {
		printf("\nThis is not insertable ");
		break;
	    }
	    if(trav->left == nil && n < trav->x)
	    {
		trav->left = make();
		trav->left->x = n;
		trav->left->p = trav;
		trav->left->color = 0;
		insertfix(trav->left);
		x = 0;
		inorder(root);
		break;
	    }
	    if(trav->right == nil && n > trav->x)
	    {
		trav->right = make();
		trav->right->x = n;
		trav->right->p = trav;
		trav->right->color = 0;
		insertfix(trav->right);
		x = 0;
		inorder(root);
		break;
	    }
	}
    }
    printf("Enter the numbers to delete: \n0 to stop: ");
    while(1)
    {
	scanf("%d",&n);
	if(n == 0)
	    break;
	if((trav=find(root,n)) != nil)
	    delet(trav);
	else
	{
	    printf("Entered element not in tree\n");
	    continue;
	}
	x = 0;
	printf("Deleted!!!\n");
	inorder(root);
    }
}
 
node* find(node *t,int x)
{
    int flag = 1;
    node *temp;
    if(t != nil)
    {
	temp = find(t->left,x);
	if(temp != nil)
	    return temp;
	if(t->x == x)	     
	    return t;
	temp = find(t->right,x);
	if(temp != nil)
	    return temp;
    }
    return nil;
}
 
int inorder(node *t)
{
    if(t != nil)
    {
	inorder(t->left);
	printf("%d \t",t->x);
	inorder(t->right);
    }
}
 
void leftrotate(node *x)
{
    node* y = x->right;
    x->right = y->left;
    y->left->p = x;
    y->p = x->p;
    if(x->p == nil)
	root = y;
    else if(x == x->p->left)
	x->p->left = y;
    else
	x->p->right = y;
    y->left = x;
    x->p = y;
}
 
void rightrotate(node *x)
{
    node* y = x->left;
    x->left = y->right;
    y->right->p = x;
    y->p = x->p;
    if(x->p == nil)
	root = y;
    else if(x == x->p->right)
	x->p->right = y;
    else
	x->p->left = y;
    y->right = x;
    x->p = y;
}
 
void insertfix(node *z)
{
    node* y;
    while(z->p->color == 0 && z != nil)
    {
	if(z->p == z->p->p->left)
	{
	    y = z->p->p->right;
	    if(y->color == 0 && y != nil)
	    {
		z->p->color = 1;
		y->color = 1;
		z->p->p->color = 0;
		z = z->p->p;
	    }
	    else
	    {
		if(z == z->p->right)
		{
		    z = z->p;
		    leftrotate(z);
		}
		if(z != root && z->p != root)
		{
		    z->p->color = 1;
		    z->p->p->color = 0;
		    rightrotate(z->p->p);
		}
	    }
	}
	else
	{
	    y = z->p->p->left;
	    if(y->color == 0)
	    {
		z->p->color = 1;
		y->color = 1;
		z->p->p->color = 0;
		z = z->p->p;
	    }
	    else
	    {
		if(z == z->p->left)
		{
		    z = z->p;
		    rightrotate(z);
		}
		if(z != root && z->p != root)
		{
		    z->p->color = 1;
		    z->p->p->color = 0;
		    leftrotate(z->p->p);
		}
	    }
	}
    }
    root->color = 1;
    nil->color = 1;
}
 
node* delet(node *z)
{
    node *y,*x;
      if(z->left == nil || z->right == nil)
	y = z;
    else
	y = treesucc(z);
    if(y->left != nil || y->right != nil)
    {
	if(y->left != nil)
	    x = y->left;
	else
	    x = y->right;
    }
     else x = nil;
	x->p = y->p;
    if(y->p == nil)
	root = x;
    else if(y == y->p->left)
	y->p->left = x;
    else
	y->p->right = x;
    if(y != z)
	z->x = y->x;
    if(y->color == 1 && x != nil)
	deletefix(x);
    return y;
}
 
node* treesucc(node *z)
{
    node *t = z->right;
    while(t->left != nil)
	t = t->left;
    return t;
}
 
void deletefix(node *x)
{
    node *w;
    while(x! = root && x->color == 1)
    {
	if(x == x->p->left)
	{    
	    w = x->p->right;
	    if(w->color == 0)
	    {
		w->color = 1;
		leftrotate(x->p);
		w = x->p->right;
	    }
	    if(w != nil && w->left->color == 1 && w->right->color == 1)
	    {
		w->color = 0;
		x = x->p;
	    }
	    else
	    {
		if(w != nil && w->right->color == 1)
		{
		    w->left->color = 1;
		    w->color = 0;
		    rightrotate(w);
		    w = x->p->right;
		    inorder(root);
		}
		w->color = x->p->color;
		x->p->color = 1;
		if(w != nil)
		    w->right->color = 1;
		leftrotate(x->p);
		x = root;
	    }
	}
	else
	{
	    w = x->p->left;
	    if(w->color == 0)
	    { 
		w->color = 1;
		rightrotate(x->p);
		w = x->p->left;
	    }
	    if(w != nil && w->right->color == 1 && w->left->color == 1)
	    {
		w->color = 0;
		x = x->p;
	    }
	    else
	    {
		if(w != nil && w->left->color == 1)
		{
		    w->right->color = 1;
		    w->color = 0;
		    leftrotate(w);
		    w = x->p->left;
		}
		w->color = x->p->color;
		x->p->color = 1;
		if(w != nil)
		    w->left->color = 1;
		rightrotate(x->p);
		x = root;
	    }
	}
	x->color = 1;
    }
}




blog comments powered by Disqus

Sister Sites: GATE Overflow, GATE CSE Wiki, GATE CSE, Aptitude Overflow

This work is licensed under the CC By-SA 3.0 , without all the cruft that would otherwise be put at the bottom of the page.