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

 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
 
+
<metadesc>Red Black Tree Insertion & Deletion implementation in C/C++  </metadesc>
−
<syntaxhighlight lang="c">
+
<syntaxhighlight lang="c" name="redblacktree">
  
 
#include<stdio.h>
 
#include<stdio.h>
Line 346: Line 346:
  
  
−
{{Template:FB}}
+
{{Template:FBD}}
−
 
 
−
 
 
−
<disqus/>
 
  
  
  
 
[[Category:Trees]]
 
[[Category:Trees]]

Latest revision as of 16:41, 22 February 2014

<syntaxhighlight lang="c" name="redblacktree">

  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>





blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=Red_Black_Tree_Insertion_%26_Deletion&oldid=2512"

<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>






blog comments powered by Disqus