Red Black Tree Insertion & Deletion Revision as of 22:30, 18 December 2013 by Arjun Suresh (talk | contribs) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

<syntaxhighlight lang="c">

1. include<stdio.h>
2. 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>

Tweet