#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20
int j=0;
char na[MAX][MAX];
int r[MAX];
struct node
{
char name[MAX];
int runs,bf;
struct node *lchild,*rchild,*par;
}*start;
void inorder(struct node *t)
{
if(t!=NULL)
{
inorder(t->lchild);
printf("%d\t%s\t%d\t%d\t%d\t%d\n",t,t->name,t->runs,t->lchild,t->rchild,t->bf);
inorder(t->rchild);
}
}
int balance(struct node *p,struct node *ch)
{ while(p!=NULL&&ch->bf!=0)
{
if(ch==p->lchild)
p->bf=p->bf+1;
else if(ch==p->rchild )
p->bf=p->bf-1;
p=p->par;
ch=ch->par;
}
return 1;
}
void LL(struct node *pi)
{
struct node *a;
a=pi->lchild;
if(pi==start)
start=a;
else
pi->par->lchild=a;
a->par=pi->par;
pi->lchild=a->rchild;
a->rchild=pi;
pi->par=a;
pi->bf=0;
a->bf=0;
while(a->par->bf>1&&a!=NULL)
{
a->par->bf--;
a=a->par;
}
}
void RR(struct node *pi)
{
struct node *b;
b=pi->rchild;
if(pi==start)
start=b;
else
pi->par->rchild=b;
b->lchild->par=pi;
pi->rchild=b->lchild;
b->par=pi->par;
b->lchild=pi;
b->par=pi->par;
pi->par=b;
pi->bf=0;
b->bf=0;
while(b->par->bf<-1&&b!=NULL)
{
b->par->bf++;
b=b->par;
}
}
void LR(struct node *pi)
{
struct node *a,*ar;
a=pi->lchild;
ar=a->rchild;
if(pi==start)
start=ar;
else
pi->par->lchild=ar;
ar->par=pi->par;
a->rchild=ar->lchild;
a->par=ar;
ar->lchild=a;
pi->lchild=ar->rchild;
ar->rchild=pi;
pi->par=ar;
if((pi->lchild!=NULL&&pi->rchild!=NULL)||(pi->lchild==NULL&&pi->rchild==NULL))
pi->bf=0;
else if(pi->lchild!=NULL)
pi->bf=1;
else if(pi->rchild==NULL)
pi->bf=-1;
if((a->lchild!=NULL&&a->rchild!=NULL)||(a->lchild==NULL&&a->rchild==NULL))
a->bf=0;
else if(a->lchild!=NULL)
a->bf=1;
else if(a->rchild==NULL)
a->bf=-1;
while(ar->par->bf>1&&ar!=NULL)
{
ar->par->bf--;
ar=ar->par;
}
}
void RL(struct node *pi)
{
struct node *b,*bl;
b=pi->rchild;
bl=b->lchild;
if(pi==start)
start=bl;
else
pi->par->rchild=bl;
bl->par=pi->par;
b->lchild=bl->rchild;
bl->rchild=b;
b->par=bl;
pi->rchild=bl->lchild;
bl->lchild=pi;
pi->par=bl;
if((pi->lchild!=NULL&&pi->rchild!=NULL)||(pi->lchild==NULL&&pi->rchild==NULL))
pi->bf=0;
else if(pi->lchild!=NULL)
pi->bf=1;
else if(pi->rchild==NULL)
pi->bf=-1;
if((b->lchild!=NULL&&b->rchild!=NULL)||(b->lchild==NULL&&b->rchild==NULL))
b->bf=0;
else if(b->lchild!=NULL)
b->bf=1;
else if(b->rchild==NULL)
b->bf=-1;
while(bl->par->bf<-1&&bl!=NULL)
{
bl->par->bf++;
bl=bl->par;
}
}
void rotate(struct node *n,struct node *pi)
{
if(n->runs<pi->runs)
{
if(n->runs < pi->lchild->runs)
{
printf("\n\nLL Rotation about %s\n\n",pi->name);
LL(pi);
}
else if(pi->lchild->runs < n->runs)
{
printf("\n\nLR Rotation about %s\n\n",pi->name);
LR(pi);
}
}
else
{
if(n->runs < pi->rchild->runs)
{
printf("\n\nRL Rotation about %s\n\n",pi->name);
RL(pi);
}
else if(n->runs > pi->rchild->runs)
{
printf("\n\nRR Rotation about %s\n\n",pi->name);
RR(pi);
}
}
/* printf("Root :- %s",start->name);
printf("\nAddress\tName\tRuns\tLeft\tRight\tBalancing Factor\n....................................\n");
inorder(start);
printf("\n"); */
}
int create(char na[MAX],int run)
{
int i,st=0;
struct node *tmp,*p,*q;
tmp=(struct node *)malloc(sizeof(struct node));
strcpy(tmp->name,na);
tmp->runs=run;
tmp->bf=0;
tmp->lchild=tmp->rchild=tmp->par=NULL;
if(start==NULL)
{
start=tmp;
return 1;
}
q=start;
while(q!=NULL)
{
if(run<q->runs)
{
p=q;
q=q->lchild;
st=1;
}
else if(run>q->runs)
{
p=q;
q=q->rchild;
st=2;
}
else
{
printf("DUPLICATE VALUE");
return 0;
}
}
if(st==1)
{
p->lchild=tmp;
tmp->par=p;
p->bf=p->bf+1;
}
else if(st==2)
{
p->rchild=tmp;
tmp->par=p;
p->bf=p->bf-1;
}
balance(p->par,p);
while(p!=NULL)
{
if(p->bf>1||p->bf<-1)
{
rotate(tmp,p);
p=p->par;
break;
}
else
p=p->par;
}
return 0;
}
void preorder(struct node *tmp)
{
if(tmp!=NULL)
{
strcpy( na[j],tmp->name);
r[j]=tmp->runs;
j++;
preorder(tmp->lchild);
preorder(tmp->rchild);
}
}
void main()
{
FILE *f;
int i,n=0,j,x=0,run,op;
char c,name[MAX][MAX],code[MAX][MAX],runs[MAX][MAX];
start=NULL;
clrscr();
f=fopen("C:/cricket.txt","r");
if(f==NULL)
{
printf("Invalid directory");
//return 0;
}
//---------------------------------------------------------------------------
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
{
name[i][j]='\0';
code[i][j]='\0';
runs[i][j]='\0';
}
i=0;x=0;n=0;
while((c=fgetc(f))!=EOF)
{
if(c==' ')
{
i=-1;
x++;
}
if(c=='\n')
{
i=-1;
x=0;
n++;
}
if(x==0)
name[n][i]+=c;
if(x==1)
code[n][i]+=c;
if(x==2)
runs[n][i]+=c;
i++;
}
//--------------------------------------------------------------------------------
for(i=0;i<=n;i++)
{
printf("Name: %s Code: %s Runs: %s\n",name[i],code[i],runs[i]);
run=atoi(runs[i]);
create(name[i],run);
}
printf("Root :- %s",start->name);
printf("\nAddress\tName\tRuns\tLeft\tRight\tBalancing Factor\n....................................\n");
inorder(start);
printf("\n");
while(1)
{
printf("\n\n1.INSERT ITEM\n2.DELETE ITEM\n3.EXIT\n");
scanf("%d",&op);
switch(op)
{
case 1:
i++;
printf("NAME: ");
scanf("%s",name[i]);
printf("RUNS: ");
scanf("%d",&run);
create(name[i],run);
break;
case 2:
preorder(start);
start=NULL;
start->lchild=start->rchild=start->par=NULL;
printf("RUNS:");
scanf("%d",&run);
for(i=0;r[i]!=0;i++)
{
if(run==r[i])
{
for(j=i;r[j]!=0;j++)
{
r[j]=r[j+1];
strcpy(na[j],na[j+1]);
}
}
//printf("%s\t%d\n",na[i],r[i]);
create(na[i],r[i]);
}
break;
case 3:
exit(0);
}
printf("Root :- %s",start->name);
printf("\nAddress\tName\tRuns\tLeft\tRight\tBalancing Factor\n....................................\n");
inorder(start);
printf("\n");
}
}
