RED BLACK TREES

RED BLACK TREES

#include”iostream.h”
#include”stdlib.h”
#include”conio.h”
//#define NULL 0
typedef struct bintree
{
int data,c;
struct bintree *l,*r,*p;
}node;
class rbtree
{
public:
node *root,*t;
rbtree()
{
root=NULL;
root->p=NULL;
}
node *insert(node *,node *);
node *rbfix(node *,node *);
void leftrot(node *,node *);
void rightrot(node *,node *);
void inorder(node *);
};
node *rbtree::insert(node *t,node *z)
{
node *y=NULL,*x=root;
while(x!=NULL)
{
y=x;
if(z->datadata)
x=x->l;
else
x=x->r;
}
z->p=y;
if(y==NULL)
root=z;
else if(z->datadata)
y->l=z;
else
y->r=z;
z->l=z->r=NULL;
z->c=1;
rbfix(t,z);
return(root);
}

/*node *rbtree::insert(node *rt,node *pt,int x)
{
if(rt==NULL)
{
rt=(node*)malloc(sizeof(node));
rt->data=x;
rt->p=pt;
rt->c=1;
rt->l=rt->r=NULL;
root=rbfix(root,rt);
}
else if(x<>data)
rt->l=insert(rt->l,rt,x);
else if(x> rt->data)
rt->r=insert(rt->r,rt,x);
else
cout<<"duplicate value"; return(rt); } */ void rbtree::inorder(node *rt) { if(rt!=NULL) { inorder(rt->l);
cout<<"-->"<data<<"\t"; if(rt->c==1)
cout<<"RED"; else cout<<"BLACK"; cout<<"\t"<<(rt->p)->data<<"\n"; inorder(rt->r);
}
}

node *rbtree::rbfix(node *t,node *z)
{
node *y;
while(z->p->c==1)
{
if(z->p==z->p->p->l)
{
y=z->p->p->r;


if(y->c==1)
{
z->p->c=0;
y->c=0;
z->p->p->c=1;
z=z->p->p;
}
else if(z==z->p->r)
{
z=z->p;
leftrot(t,z);
z->p->c=0;
z->p->p->c=1;
rightrot(t,z->p->p);
}
}
else if(z->p==z->p->p->r)
{
y=z->p->p->l;
if(y->c==1)
{
z->p->c=0;
y->c=0;
z->p->p->c=1;
z=z->p->p;
}
else if(z==z->p->l)
{
z=z->p;
rightrot(t,z);
z->p->c=0;
z->p->p->c=1;
leftrot(t,z->p->p);
}
}
}
root->c=0;
return t;
}
void rbtree::leftrot(node *t,node *x)
{
node *y;
y=x->r;
x->r=y->l;
y->l->p=x;
y->p=x->p;
if(x->p==NULL)
root=y;
else if(x==x->p->l)
x->p->l=y;
else
x->p->r=y;
y->l=x;
x->p=y;
}

void rbtree::rightrot(node *t,node *x)
{
node *y;
y=x->l;
x->l=y->r;
y->r->p=x;
y->p=x->p;
if(x->p==NULL)
root=y;
else if(x==x->p->l)
x->p->l=y;
else
x->p->r=y;
y->r=x;
x->p=y;
}
void main()
{
int x,i,n;
node *rt;
rbtree rb;
clrscr();
cout<<"Enter the no of nodes"; cin>>n;
for(i=1;i<=n;i++) { cout<<"Enter node "< cout<<" NODE\tCOLOR\tPARENT\n";
rb.inorder(rb.root);
getch();
}