Red Black Tree Insertion & Deletion - Revision history

Arjun Suresh at 16:41, 22 February 2014

2014-02-22T16:41:48Z

Arjun Suresh at 12:24, 6 January 2014

2014-01-06T12:24:09Z

Arjun Suresh at 22:30, 18 December 2013

2013-12-18T22:30:08Z

Arjun Suresh at 21:07, 13 December 2013

2013-12-13T21:07:44Z

Show changes

Arjun Suresh at 20:54, 13 December 2013

2013-12-13T20:54:07Z

Arjun Suresh at 20:53, 13 December 2013

2013-12-13T20:53:32Z

Arjun Suresh at 20:53, 13 December 2013

2013-12-13T20:53:02Z

Arjun Suresh at 20:51, 13 December 2013

2013-12-13T20:51:29Z

Arjun Suresh: Created page with " #include #include struct nod { int x; int color; struct nod left; struct nod p; struct nod *right; }; ty..."

2013-12-13T20:51:14Z

Created page with " <syntaxhighlight code="c"> #include<stdio.h> #include<stdlib.h> struct nod { int x; int color; struct nod *left; struct nod *p; struct nod *right; }; ty..."

New page

<syntaxhighlight code="c">

#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);
node* make()
{
node*a;
a=(node*)malloc(sizeof(node));
a->left=nil;
a->right=nil;
return a;
};
int inorder(node *t);
int x;
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);
cleardevice();
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;
}
cleardevice();
x=0;
printf("Deleted!!!\n");
inorder(root);
}
getch();
}

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>

{{Template:FB}}

<disqus/>

[[Category:Trees]]

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

← Older revision		Revision as of 12:24, 6 January 2014
Line 346:		Line 346:


−	{{Template:FB}}	+	{{Template:FBD}}
−
−
−	~~<disqus/>~~



	[[Category:Trees]]		[[Category:Trees]]

← Older revision		Revision as of 22:30, 18 December 2013
Line 1:		Line 1:
−		+	<metadesc>Red Black Tree Insertion & Deletion implementation in C/C++ </metadesc>
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">

← Older revision		Revision as of 20:51, 13 December 2013
Line 1:		Line 1:

−	<syntaxhighlight ~~code~~="c">	+	<syntaxhighlight lang="c">

	#include<stdio.h>		#include<stdio.h>

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

@@ Line 14: / Line 14: @@
 };
 typedef struct nod node;
 void insertfix(node* z);
 node* delet(node*);
@@ Line 21: / Line 22: @@
 node *root,*nil;
 int preorder(node *t);
 node* make()
+{

@@ Line 81: / Line 81: @@
 		trav->right->color=0;
 		insertfix(trav->right);
 		x=0;
 		inorder(root);
@@ Line 101: / Line 100: @@
 	    continue;
+	}
 	x=0;
 	printf("Deleted!!!\n");
 	inorder(root);
+     }
+}
@@ Line 136: / Line 133: @@
+     }
+}
 void leftrotate(node*x)
+{
@@ Line 227: / Line 225: @@
      nil->color=1;
+}
 node* delet(node*z)
+{
@@ Line 255: / Line 254: @@
      return y;
+}
 node* treesucc(node *z)
+{
@@ Line 262: / Line 262: @@
      return t;
+}
 void deletefix(node *x)
+{
@@ Line 335: / Line 336: @@
 </syntaxhighlight>
 {{Template:FB}}

Red Black Tree Insertion & Deletion - Revision history

Arjun Suresh at 16:41, 22 February 2014

Arjun Suresh at 12:24, 6 January 2014

Arjun Suresh at 22:30, 18 December 2013

Arjun Suresh at 21:07, 13 December 2013

Arjun Suresh at 20:54, 13 December 2013

Arjun Suresh at 20:53, 13 December 2013

Arjun Suresh at 20:53, 13 December 2013

Arjun Suresh at 20:51, 13 December 2013

Arjun Suresh: Created page with " #include #include struct nod { int x; int color; struct nod *left; struct nod *p; struct nod *right; }; ty..."

Arjun Suresh: Created page with " #include #include struct nod { int x; int color; struct nod left; struct nod p; struct nod *right; }; ty..."