R-B tree

R-B TREE
Program

#include
#include
#include
#include
#include
#include
#include

#define originX 320
#define originY 50
#define lineLength 145
#define circleRadius 10

struct treenode
{
int data;
char col;
int mX,mY;
int Level;
struct treenode *rlink;
struct treenode *llink;
struct treenode *parent;
}*p,*curr,*root,*temp,*father,*succ,*uncle=NULL;

int l=0,c,d,ctr=0,top=0;
char ch;

void insert();
void del();
void traverse();
void deallocate();
void check(struct treenode *);
void tredis(struct treenode *ptr, int blanks);
void insertfix(struct treenode *);
void leftrotate(struct treenode*);
void rightrotate(struct treenode*);
void drawTree( struct treenode* Current);
void preOrder(struct treenode* myRoot);

void main()
{
int code;
clrscr();
int gDriver = DETECT,gMode,Data;
initgraph(&gDriver,&gMode,"f:\\tc\\bgi");
if(ctr==0)
{
printf("\n----------------------\n");
printf("\n RED BLACK Tree");
printf("\n----------------------\n");
ctr++;
}
printf("\nWhat do u want to do\n");
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Exit\n");
printf("\nEnter ur choice:\t");
scanf("%d",&code);

switch(code)
{
case 1:insert();
break;
case 2: del();
break;
case 3: traverse();
preOrder(root);
break;
case 4: exit(0);
break;
default: printf("WRONG CHOICE");
break;
}
printf("\nDo you want to continue(y/n)");
ch=getch();
if(ch=='y')
main();
else
exit(0);
}


void insert()
{
l++;
if(l==1)
{
root=(struct treenode *)malloc(sizeof(struct treenode));
printf("\nEnter data:\t");
scanf("%d",&root->data);
root->llink=NULL;
root->rlink=NULL;
root->col='b';
root->parent=NULL;
root->mX=originX;
root->mY=originY;
main();
}
else
{
c=0;
temp=(struct treenode *)malloc(sizeof(struct treenode));
printf("\nEnter data:\t");
scanf("%d",&temp->data);
d=temp->data;
temp->col='r';
temp->parent=NULL;
check(root);
if(c==1)
{
printf("\n /**WARNING**\\Data already present cannot enter \n");
printf("\nDo you want to continue(y/n)");
ch=getch();
if(ch=='y')
{
free(temp);
main();
}
else
exit(0);
}
else
{
temp->llink=NULL;
temp->rlink=NULL;
curr=root;
while(curr!=NULL)
{
if(temp->data < curr->data)
{
if(curr->llink!=NULL)
{
curr=curr->llink;
}
else
{
curr->llink=temp;
temp->parent=curr;
insertfix(temp);
main();
}
}
else if(temp->data > curr->data)
{
if(curr->rlink!=NULL)
{
curr=curr->rlink;
}
else
{
curr->rlink=temp;
temp->parent=curr;
insertfix(temp);
main();
}
}
}
}
}
}

void del()
{
int item;
printf("\nEnter item to be deleted\t");
scanf("%d",&item);
if(root==NULL)
{
printf("EMPTY TREE");
getch();
main();
}
curr=root;
father=NULL;
while(curr!=NULL && curr->data!=item)
{
father = curr;
if(itemdata)
curr=curr->llink;
else
curr=curr->rlink;
}

if(curr==NULL)
{
printf("Item does not exist");
main();
}

if(curr->llink!=NULL && curr->rlink!=NULL)
{
father = curr;
succ=curr->rlink;
while(succ->llink!=NULL)
{
father=succ;
succ=succ->llink;
}
curr->data=succ->data;
curr=succ;
if(father->rlink==succ)
father->rlink=NULL;
else
father->llink=NULL;
}

else if(curr->llink!=NULL)
{
if(father!=NULL)
{
if(father->llink==curr)
{
father->llink=curr->llink;
}
else
father->rlink=curr->rlink;
}
else
root=curr->rlink;
}

else if(curr->rlink==NULL)
{
if(father->llink==curr)
father->llink=curr->llink;
else
father->rlink=curr->llink;
}
else
root=curr->llink;
free(curr);
main();
}

void traverse()
{
clrscr();
cleardevice();
tredis(root,0);

}


void check(struct treenode *p)
{
if(p!=NULL)
{
if(p->data==d)
c=1;
check(p->llink);
check(p->rlink);
}
}
void tredis(struct treenode *ptr,int levels)
{
int i;
if ( ptr!=NULL )
{
ptr->Level=levels;
tredis(ptr->llink, levels+1);
tredis(ptr->rlink, levels+1);
}
}

void insertfix(struct treenode* x)
{
while(x->parent->col=='r')
{
if(x->parent==x->parent->parent->llink)
{
uncle=x->parent->parent->rlink;

/*case 1*/

if(uncle->col=='r')
{
x->parent->col='b';
uncle->col='b';
x->parent->parent->col='r';
x=x->parent->parent;
}

/*case 2*/

else if(x==x->parent->llink)
{
x=x->parent;
leftrotate(x);

/*case 3*/

x->parent->col='b';
x->parent->parent->col='r';
rightrotate(x);
}
}
else if(x->parent==x->parent->parent->rlink)
{
uncle=x->parent->parent->llink;

/*case 1*/

if(uncle->col=='r')
{
x->parent->col='b';
uncle->col='b';
x->parent->parent->col='r';
x=x->parent->parent;
}

/*case 2*/

else if(x==x->parent->rlink)
{
x=x->parent;
rightrotate(x);

/*case 3*/

x->parent->col='b';
x->parent->parent->col='r';
leftrotate(x);
}
}
root->col='b';
}
main();
}

void leftrotate(struct treenode *x)
{
struct treenode *y;
y=x->rlink;
x->rlink=y->llink;
y->llink->parent=x;
y->parent=x->parent;
if(x->parent==NULL)
{
root=y;
}
else if(x==x->llink->parent)
{
x->llink->parent=y;
}
else
{
x->rlink->parent=y;
}
y->llink=x;
x->parent=y;
}

void rightrotate(struct treenode *x)
{
struct treenode *y;
y=x->llink;
x->llink=y->rlink;
y->rlink->parent=x;
y->parent=x->parent;
if(x->parent==NULL)
{
root=y;
}
else if(x==x->rlink->parent)
{
x->rlink->parent=y;
}
else
{
x->llink->parent=y;
}
y->rlink=x;
x->parent=y;
}

void drawTree( struct treenode* Current)
{
int pX,pY,newlineLength,textColor=WHITE,nodeColor=RED;
int offsetX,offsetY,Angle,newAngle,color;
char *Buffer;
double radianAngle;

if(Current->Level==1)
Angle=80;
else if(Current->Level>1)
Angle=45;

if(Current->Level==0)
newlineLength=160;
else
newlineLength = lineLength-15*Current->Level;

if(newlineLength<=45)
newlineLength=45;

newAngle = Angle-10*Current->Level;

if(newAngle<=10)
newAngle=12;

setcolor(RED);
setfillstyle(SOLID_FILL,RED);

if(Current->col=='r')
{
setcolor(RED);
setfillstyle(1,RED);
color=RED;
}
else
{
setcolor(WHITE);
setfillstyle(1,BLACK);
color=WHITE;
}

if(Current->parent==NULL)
{
circle(originX,originY,circleRadius);
floodfill(originX+3,originY+3,color);
itoa(Current->data,Buffer,10);
setcolor(textColor);
outtextxy(originX-7,originY-3,Buffer);
setcolor(nodeColor);
}
else
{
pX=Current->parent->mX;
pY=Current->parent->mY;

if(Current->data < Current->parent->data)
{
radianAngle = (3.14285/180)*newAngle;

offsetX = pX - newlineLength * sin(radianAngle);
offsetY = pY + newlineLength * cos(radianAngle);


circle(offsetX,offsetY,circleRadius);
floodfill(offsetX+3,offsetY+3,color);
setcolor(BLUE);
line(pX,pY,offsetX,offsetY);
itoa(Current->data,Buffer,10);
setcolor(textColor);
outtextxy(offsetX-7,offsetY-3,Buffer);
setcolor(nodeColor);
Current->mX=offsetX;
Current->mY=offsetY;
}
else if(Current->data > Current->parent->data)
{
radianAngle = (3.14285/180)*newAngle;

offsetX = pX + newlineLength * sin(radianAngle);
offsetY = pY + newlineLength * cos(radianAngle);

circle(offsetX,offsetY,circleRadius);
floodfill(offsetX+3,offsetY+3,color);
setcolor(BLUE);
line(pX,pY,offsetX,offsetY);
itoa(Current->data,Buffer,10);
setcolor(textColor);
outtextxy(offsetX-7,offsetY-3,Buffer);
setcolor(nodeColor);
Current->mX=offsetX;
Current->mY=offsetY;
}

}//ELSE

}

void preOrder(struct treenode* myRoot)
{
if(myRoot!=NULL)
{
drawTree(myRoot);
preOrder(myRoot->llink);
preOrder(myRoot->rlink);
}

}