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();
}

MINIMUM SPANNING TREE

FLOYD’S WARSHALL ALGORITHM

#include"iostream.h"
#include"conio.h"
#include"stdlib.h"
#define max 20
class warshall
{
int n,w[max][max],d[max][max],p[max][max];
public:
void getinit();
void floyd();
void path(int,int);
void viewpath();
void dispmat(int);
};

void warshall::getinit()
{
int i,j;
cout<<"enter the no vertices";
cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
w[i][j]=0;
cout<<"enter the weight of edges";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j && w[i][j]==0)
{
cout<<"edge"<<>"< cin>>w[i][j];
if(w[i][j]!=99)
w[j][i]=99;
}
}

void warshall::floyd()
{
int i,j,k,d1[max][max],p1[max][max];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=w[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(d[i][j]==0d[i][j]==99)
p[i][j]=0;
else
p[i][j]=i;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
d1[i][j]=d[i][j];
p1[i][j]=p[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(d1[i][j]>(d1[i][k]+d1[k][j]))
{
d[i][j]=d1[i][k]+d1[k][j];
p[i][j]=p1[k][j];
}
else
d[i][j]=d1[i][j];
}
}
}

void warshall::path(int i,int j)
{
if(i==j)
cout< else
{
path(i,p[i][j]);
cout<<"-->"< }
}

void warshall::dispmat(int c)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(c==2)
cout<<"\t"< else if(c==3)
cout<<"\t"< else if(c==4)
cout<<"\t"< }
cout< }
}

void warshall::viewpath()
{
int v1,v2;
cout<<"\nFINDING SHORTEST PATH BETWEEN VERTICES\n";
cout<<"Enter the vertex 1&2 to find shortest path & distance";
cin>>v1>>v2;
cout<<"\nShortest path from"< path(v1,v2);
cout<<"\n The distance of the path is: "<}

void main()
{
int ch;
clrscr();
warshall fw;
do
{
cout<<"\n1-Input 2-weight matrix 3-Distance mat 4-path mat 5- view path\n";
cin>>ch;
switch(ch)
{
case 1: fw.getinit();
fw.floyd();
break;
case 2: cout<<"\tTHE WEIGHT MATRIX\n\n";
fw.dispmat(ch);
break;
case 3: cout<<"\tTHE DISTANCE MATRIX\n\n";
fw.dispmat(ch);
break;
case 4: cout<<"\tTHE PATH MATRIX\n\n";
fw.dispmat(ch);
break;
case 5: fw.viewpath();
break;
case 6: exit(0);
break;
}
}while(ch<=6);
getch();
}