Difference between revisions of "Red Black Tree Insertion & Deletion"

Revision as of 20:54, 13 December 2013

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;

}

</syntaxhighlight>

@@ Line 22: / Line 22: @@
 node *root,*nil;
 int preorder(node *t);
+int inorder(node *t);
+int x;
 node* make()
@@ Line 31: / Line 34: @@
      return a;
 };
-int inorder(node *t);
-int x;
 int main()
 {