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

Revision as of 20:53, 13 December 2013 (view source) Arjun Suresh (talk | contribs) ← Older edit		Latest revision as of 16:41, 22 February 2014 (view source) Arjun Suresh (talk | contribs)
(5 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>
	#include<stdlib.h>		#include<stdlib.h>
−		+
	struct nod		struct nod
	{		{
Line 14:		Line 14:
	};		};
	typedef struct nod node;		typedef struct nod node;
−	void insertfix(node* z);	+
−	node* delet(node*);	+	void insertfix(node *z);
−	node* treesucc(node*);	+	node* delet(node *);
−	void deletefix(node*);	+	node* treesucc(node *);
		+	void deletefix(node *);
	node* find(node *t,int);		node* find(node *t,int);
	node *root,*nil;		node *root,*nil;
	int preorder(node *t);		int preorder(node *t);
		+	int inorder(node *t);
		+	int x;
		+
		+
	node* make()		node* make()
	{		{
−	node*a;	+	node *a;
−	a=(node*)malloc(sizeof(node));	+	a = (node *)malloc(sizeof(node));
−	a->left=nil;	+	a->left = nil;
−	a->right=nil;	+	a->right = nil;
	return a;		return a;
	};		};
−	int inorder(node *t);	+
−	int x;	+
		+
	int main()		int main()
	{		{
	node *trav;		node *trav;
−	int n=0,*a,i;	+	int n = 0,*a,i;
−		+
−	nil=make();	+	nil = make();
−	nil->x=0;	+	nil->x = 0;
−	nil->color=1;	+	nil->color = 1;
−	root= make();	+	root = make();
	printf("Enter the root: ");		printf("Enter the root: ");
	scanf("%d",&root->x);		scanf("%d",&root->x);
−	root->p=nil;	+	root->p = nil;
−	root->color=1;	+	root->color = 1;
	inorder(root);		inorder(root);
	printf("Enter  numbers\n-1 to stop\n");		printf("Enter  numbers\n-1 to stop\n");
Line 49:		Line 55:
	{		{
	scanf("%d",&n);		scanf("%d",&n);
−	if(n==-1)	+	if(n == -1)
	break;		break;
−	trav=root;	+	trav = root;
	for(;;)		for(;;)
	{		{
−	if(n<trav->x&&trav->left!=nil)	+	if(n < trav->x && trav->left != nil)
	trav=trav->left;		trav=trav->left;
−	if(n>trav->x&&trav->right!=nil)	+	if(n > trav->x && trav->right != nil)
−	trav=trav->right;	+	trav = trav->right;
−	if(n==trav->x)	+	if(n == trav->x)
	{		{
	printf("\nThis is not insertable ");		printf("\nThis is not insertable ");
	break;		break;
	}		}
−	if(trav->left==nil&&n<trav->x)	+	if(trav->left == nil && n < trav->x)
	{		{
−	trav->left=make();	+	trav->left = make();
−	trav->left->x=n;	+	trav->left->x = n;
−	trav->left->p=trav;	+	trav->left->p = trav;
−	trav->left->color=0;	+	trav->left->color = 0;
	insertfix(trav->left);		insertfix(trav->left);
−	x=0;	+	x = 0;
	inorder(root);		inorder(root);
	break;		break;
	}		}
−	if(trav->right==nil&&n>trav->x)	+	if(trav->right == nil && n > trav->x)
	{		{
−	trav->right=make();	+	trav->right = make();
−	trav->right->x=n;	+	trav->right->x = n;
−	trav->right->p=trav;	+	trav->right->p = trav;
−	trav->right->color=0;	+	trav->right->color = 0;
	insertfix(trav->right);		insertfix(trav->right);
−	x=0;	+	x = 0;
	inorder(root);		inorder(root);
	break;		break;
Line 91:		Line 97:
	{		{
	scanf("%d",&n);		scanf("%d",&n);
−	if(n==0)	+	if(n == 0)
	break;		break;
−	if((trav=find(root,n))!=nil)	+	if((trav=find(root,n)) != nil)
	delet(trav);		delet(trav);
	else		else
Line 100:		Line 106:
	continue;		continue;
	}		}
−	x=0;	+	x = 0;
	printf("Deleted!!!\n");		printf("Deleted!!!\n");
	inorder(root);		inorder(root);
	}		}
	}		}
−		+
	node* find(node *t,int x)		node* find(node *t,int x)
	{		{
−	int flag=1;	+	int flag = 1;
	node *temp;		node *temp;
−	if(t!=nil)	+	if(t != nil)
	{		{
−	temp=find(t->left,x);	+	temp = find(t->left,x);
−	if(temp!=nil)	+	if(temp != nil)
	return temp;		return temp;
−	if(t->x==x)	+	if(t->x == x)
	return t;		return t;
−	temp=find(t->right,x);	+	temp = find(t->right,x);
−	if(temp!=nil)	+	if(temp != nil)
	return temp;		return temp;
	}		}
	return nil;		return nil;
	}		}
−		+
	int inorder(node *t)		int inorder(node *t)
	{		{
−	if(t!=nil)	+	if(t != nil)
	{		{
	inorder(t->left);		inorder(t->left);
Line 133:		Line 139:
	}		}
	}		}
−		+
−	void leftrotate(node*x)	+	void leftrotate(node *x)
	{		{
−	node* y=x->right;	+	node* y = x->right;
−	x->right=y->left;	+	x->right = y->left;
−	y->left->p=x;	+	y->left->p = x;
−	y->p=x->p;	+	y->p = x->p;
−	if(x->p==nil)	+	if(x->p == nil)
−	root=y;	+	root = y;
−	else if(x==x->p->left)	+	else if(x == x->p->left)
−	x->p->left=y;	+	x->p->left = y;
	else		else
−	x->p->right=y;	+	x->p->right = y;
−	y->left=x;	+	y->left = x;
−	x->p=y;	+	x->p = y;
	}		}
−		+
−	void rightrotate(node*x)	+	void rightrotate(node *x)
	{		{
−	node* y=x->left;	+	node* y = x->left;
−	x->left=y->right;	+	x->left = y->right;
−	y->right->p=x;	+	y->right->p = x;
−	y->p=x->p;	+	y->p = x->p;
−	if(x->p==nil)	+	if(x->p == nil)
−	root=y;	+	root = y;
−	else if(x==x->p->right)	+	else if(x == x->p->right)
−	x->p->right=y;	+	x->p->right = y;
	else		else
−	x->p->left=y;	+	x->p->left = y;
−	y->right=x;	+	y->right = x;
−	x->p=y;	+	x->p = y;
	}		}
−		+
−	void insertfix(node* z)	+	void insertfix(node *z)
	{		{
−	node*y;	+	node* y;
−	while(z->p->color==0&&z!=nil)	+	while(z->p->color == 0 && z != nil)
	{		{
−	if(z->p==z->p->p->left)	+	if(z->p == z->p->p->left)
	{		{
−	y=z->p->p->right;	+	y = z->p->p->right;
−	if(y->color==0&&y!=nil)	+	if(y->color == 0 && y != nil)
	{		{
−	z->p->color=1;	+	z->p->color = 1;
−	y->color=1;	+	y->color = 1;
−	z->p->p->color=0;	+	z->p->p->color = 0;
−	z=z->p->p;	+	z = z->p->p;
	}		}
	else		else
	{		{
−	if(z==z->p->right)	+	if(z == z->p->right)
	{		{
−	z=z->p;	+	z = z->p;
	leftrotate(z);		leftrotate(z);
	}		}
−	if(z!=root&&z->p!=root)	+	if(z != root && z->p != root)
	{		{
−	z->p->color=1;	+	z->p->color = 1;
−	z->p->p->color=0;	+	z->p->p->color = 0;
	rightrotate(z->p->p);		rightrotate(z->p->p);
	}		}
Line 198:		Line 204:
	else		else
	{		{
−	y=z->p->p->left;	+	y = z->p->p->left;
−	if(y->color==0)	+	if(y->color == 0)
	{		{
−	z->p->color=1;	+	z->p->color = 1;
−	y->color=1;	+	y->color = 1;
−	z->p->p->color=0;	+	z->p->p->color = 0;
−	z=z->p->p;	+	z = z->p->p;
	}		}
	else		else
	{		{
−	if(z==z->p->left)	+	if(z == z->p->left)
	{		{
−	z=z->p;	+	z = z->p;
	rightrotate(z);		rightrotate(z);
	}		}
−	if(z!=root&&z->p!=root)	+	if(z != root && z->p != root)
	{		{
−	z->p->color=1;	+	z->p->color = 1;
−	z->p->p->color=0;	+	z->p->p->color = 0;
	leftrotate(z->p->p);		leftrotate(z->p->p);
	}		}
Line 222:		Line 228:
	}		}
	}		}
−	root->color=1;	+	root->color = 1;
−	nil->color=1;	+	nil->color = 1;
	}		}
−		+
−	node* delet(node*z)	+	node* delet(node *z)
	{		{
−	node*y,*x;	+	node *y,*x;
−	if(z->left==nil||z->right==nil)	+	if(z->left == nil || z->right == nil)
−	y=z;	+	y = z;
	else		else
−	y=treesucc(z);	+	y = treesucc(z);
−	if(y->left!=nil||y->right!=nil)	+	if(y->left != nil || y->right != nil)
	{		{
−	if(y->left!=nil)	+	if(y->left != nil)
−	x=y->left;	+	x = y->left;
	else		else
−	x=y->right;	+	x = y->right;
	}		}
−	else x=nil;	+	else x = nil;
−	x->p=y->p;	+	x->p = y->p;
−	if(y->p==nil)	+	if(y->p == nil)
−	root=x;	+	root = x;
−	else if(y==y->p->left)	+	else if(y == y->p->left)
−	y->p->left=x;	+	y->p->left = x;
	else		else
−	y->p->right=x;	+	y->p->right = x;
−	if(y!=z)	+	if(y != z)
−	z->x=y->x;	+	z->x = y->x;
−	if(y->color==1&&x!=nil)	+	if(y->color == 1 && x != nil)
	deletefix(x);		deletefix(x);
	return y;		return y;
	}		}
−		+
	node* treesucc(node *z)		node* treesucc(node *z)
	{		{
−	node *t=z->right;	+	node *t = z->right;
−	while(t->left!=nil)	+	while(t->left != nil)
−	t=t->left;	+	t = t->left;
	return t;		return t;
	}		}
−		+
	void deletefix(node *x)		void deletefix(node *x)
	{		{
	node *w;		node *w;
−	while(x!=root&&x->color==1)	+	while(x! = root && x->color == 1)
	{		{
−	if(x==x->p->left)	+	if(x == x->p->left)
	{		{
−	w=x->p->right;	+	w = x->p->right;
−	if(w->color==0)	+	if(w->color == 0)
	{		{
−	w->color=1;	+	w->color = 1;
	leftrotate(x->p);		leftrotate(x->p);
−	w=x->p->right;	+	w = x->p->right;
	}		}
−	if(w!=nil&&w->left->color==1&&w->right->color==1)	+	if(w != nil && w->left->color == 1 && w->right->color == 1)
	{		{
−	w->color=0;	+	w->color = 0;
−	x=x->p;	+	x = x->p;
	}		}
	else		else
	{		{
−	if(w!=nil&&w->right->color==1)	+	if(w != nil && w->right->color == 1)
	{		{
−	w->left->color=1;	+	w->left->color = 1;
−	w->color=0;	+	w->color = 0;
	rightrotate(w);		rightrotate(w);
−	w=x->p->right;	+	w = x->p->right;
	inorder(root);		inorder(root);
	}		}
−	w->color=x->p->color;	+	w->color = x->p->color;
−	x->p->color=1;	+	x->p->color = 1;
−	if(w!=nil)	+	if(w != nil)
−	w->right->color=1;	+	w->right->color = 1;
	leftrotate(x->p);		leftrotate(x->p);
−	x=root;	+	x = root;
	}		}
	}		}
	else		else
	{		{
−	w=x->p->left;	+	w = x->p->left;
−	if(w->color==0)	+	if(w->color == 0)
	{		{
−	w->color=1;	+	w->color = 1;
	rightrotate(x->p);		rightrotate(x->p);
−	w=x->p->left;	+	w = x->p->left;
	}		}
−	if(w!=nil&&w->right->color==1&&w->left->color==1)	+	if(w != nil && w->right->color == 1 && w->left->color == 1)
	{		{
−	w->color=0;	+	w->color = 0;
−	x=x->p;	+	x = x->p;
	}		}
	else		else
	{		{
−	if(w!=nil&&w->left->color==1)	+	if(w != nil && w->left->color == 1)
	{		{
−	w->right->color=1;	+	w->right->color = 1;
−	w->color=0;	+	w->color = 0;
	leftrotate(w);		leftrotate(w);
−	w=x->p->left;	+	w = x->p->left;
	}		}
−	w->color=x->p->color;	+	w->color = x->p->color;
−	x->p->color=1;	+	x->p->color = 1;
−	if(w!=nil)	+	if(w != nil)
−	w->left->color=1;	+	w->left->color = 1;
	rightrotate(x->p);		rightrotate(x->p);
−	x=root;	+	x = root;
	}		}
	}		}
−	x->color=1;	+	x->color = 1;
	}		}
	}		}
		+
	</syntaxhighlight>		</syntaxhighlight>
Line 339:		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>