My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
RBT Implementation without deletion in C++
Posted Date:
Total Responses: 0
Posted By: Vikram Narayan C Member Level: Silver Points/Cash: 5
|
//...VIKKI...
#include //iostream.h
#include //conio.h
#include //string.h
#include //dos.h
#include //graphics.h
#include //stdlib.h
struct node
{
node * left;
node * right;
node * parent;
int info;
int x,y;
int color;
};
node * par = (node*)NULL;
int x = 20,x1 = 20;
int y = 10,y1 = 10;
int index = 0;
int m = 0;
node * t;
node* successor(node* curr)
{
if(curr->right==NULL)
return curr;
curr = curr->right;
while(curr->left !=NULL)
curr = curr->left;
return curr;
}
void findval(node **curr,int val,node **del)
{
if((*curr)!=NULL)
{
findval(&(*curr)->left,val,&(*del));
if((*curr)->info==val)
{
(*del) = (*curr);
}
findval(&(*curr)->right,val,&(*del));
}
}
void height(node *curr,int &max)
{
static int cnt = 0;
if(max max = cnt;
if(curr!=NULL)
{
cnt++;
height(curr->left,max);
height(curr->right,max);
cnt--;
}
}
void printtree(node* curr,int &max)
{
static int cnt = 0;
char temp[20] = "";
if(max<=cnt)
{
max = cnt;
}
if(curr!=NULL)
{
y+=50;
if((curr->left!=NULL)||(curr->right!=NULL))
cnt++;
printtree(curr->left,max);
itoa(curr->info,temp,10);
setcolor(BLUE);
if(curr->color==1)
setfillstyle(1,RED);
else
setfillstyle(1,DARKGRAY);
if((curr->left==NULL)||(curr->right==NULL))
bar(x+5,y-3,x+15,y+3);
else
{
fillellipse(x+10,y,15,15);
setcolor(YELLOW);
outtextxy(x,y,temp);
}
curr->x = x+10;
curr->y = y;
x1 = x+10;
y1 = y;
x+=20;
printtree(curr->right,max);
if((curr->left!=NULL)||(curr->right!=NULL))
cnt--;
y-=50;
}
}
void drawlines(node *curr)
{
if(curr!=NULL)
{
drawlines(curr->left);
setcolor(GREEN);
if(curr->parent!=NULL)
line(curr->x,curr->y,curr->parent->x,curr->parent->y);
drawlines(curr->right);
}
}
void print(node *root)
{
int gd = DETECT,gm;
initgraph(&gd,&gm,"i:\\tcpp\\bgi");
cleardevice();
m = 0;
setbkcolor(WHITE);
printtree(root,m);
char *maxs = "";
strcpy(maxs,"");
itoa(m,maxs,10);
setcolor(RED);
outtextxy(150,400,"The height of tree is:");
outtextxy(350,400,maxs);
drawlines(root);
getch();
closegraph();
x = x1 = 20;
y = y1 = 10;
}
node* LLrotate(node **root,node *curr)
{
node *child = curr->left;
child->parent = curr->parent;
if(curr->info!=(*root)->info);
{
if(curr==curr->parent->left)
{
curr->parent->left = child;
child->parent = curr->parent;
}
else if(curr==curr->parent->right)
{
curr->parent->right = child;
child->parent = curr->parent;
}
}
curr->parent = child;
curr->left = child->right;
child->right->parent = curr;
child->right = curr;
if(curr->info==(*root)->info)
(*root) = child;
return child;
}
node* RRrotate(node **root,node *curr)
{
node *child = curr->right;
child->parent = curr->parent;
if(curr->info!=(*root)->info);
{
if(curr==curr->parent->left)
{
curr->parent->left = child;
child->parent = curr->parent;
}
else if(curr==curr->parent->right)
{
curr->parent->right = child;
child->parent = curr->parent;
}
}
curr->parent = child;
curr->right = child->left;
child->left->parent = curr;
child->left = curr;
if(curr->info==(*root)->info)
(*root) = child;
return child;
}
void LLR(node **curr)
{
(*curr)->parent->parent->color = 1;
(*curr)->parent->color = 0;
(*curr)->parent->parent->right->color = 0;
}
void LLB(node **curr,node **root)
{
(*curr)->parent->parent->color = 1;
(*curr)->parent->color = 0;
LLrotate(&(*root),(*curr)->parent->parent);
}
void RLR(node **curr)
{
(*curr)->parent->parent->color = 1;
(*curr)->parent->color = 0;
(*curr)->parent->parent->left->color = 0;
}
void RLB(node **curr,node **root)
{
(*curr)->color = 0;
(*curr)->parent->parent->color = 1;
node *t;
t = (*curr)->parent->parent;
LLrotate(&(*root),(*curr)->parent);
t = RRrotate(&(*root),t);
(*curr)->parent->parent = t;
}
void RRR(node **curr)
{
(*curr)->parent->parent->color = 1;
(*curr)->parent->color = 0;
(*curr)->parent->parent->left->color = 0;
}
void RRB(node **curr,node **root)
{
(*curr)->parent->parent->color = 1;
(*curr)->parent->color = 0;
RRrotate(&(*root),(*curr)->parent->parent);
}
void LRR(node **curr)
{
(*curr)->parent->parent->color = 1;
(*curr)->parent->color = 0;
(*curr)->parent->parent->right->color = 0;
}
void LRB(node **curr,node **root)
{
(*curr)->color = 0;
(*curr)->parent->parent->color = 1;
node *t;
t = (*curr)->parent->parent;
RRrotate(&(*root),(*curr)->parent);
t = LLrotate(&(*root),t);
(*curr)->parent->parent = t;
}
void RBTInsertAdjust(node **curr,node **root)
{
if((*curr)->color==1)
{
if((*curr)->parent == NULL)
{
(*curr)->color = 0;
}
else if((*curr)->parent->color == 1)
{
if((*curr)==(*curr)->parent->left)
{
if((*curr)->parent==(*curr)->parent->parent->left)
{
if((*curr)->parent->parent->right->color==1)
{
cout<<"LLR";
LLR(&(*curr));
// print(*root);
// getch();
RBTInsertAdjust(&((*curr)->parent->parent),&(*root));
}
else if((*curr)->parent->parent->right->color==0)
{
cout<<"LLB";
LLB(&(*curr),&(*root));
// print(*root);
// getch();
}
}
else if((*curr)->parent==(*curr)->parent->parent->right)
{
if((*curr)->parent->parent->left->color==1)
{
cout<<"RLR";
RLR(&(*curr));
// print(*root);
// getch();
RBTInsertAdjust(&((*curr)->parent->parent),&(*root));
}
else if((*curr)->parent->parent->left->color==0)
{
cout<<"RLB";
RLB(&(*curr),&(*root));
// print(*root);
// getch();
}
}
}
else if((*curr)==(*curr)->parent->right)
{
if((*curr)->parent==(*curr)->parent->parent->left)
{
if((*curr)->parent->parent->right->color==1)
{
cout<<"LRR";
LRR(&(*curr));
// print(*root);
// getch();
RBTInsertAdjust(&((*curr)->parent->parent),&(*root));
}
else if((*curr)->parent->parent->right->color==0)
{
cout<<"LRB";
LRB(&(*curr),&(*root));
// print(*root);
// getch();
}
}
else if((*curr)->parent==(*curr)->parent->parent->right)
{
if((*curr)->parent->parent->left->color==1)
{
cout<<"RRR";
RRR(&(*curr));
// print(*root);
// getch();
RBTInsertAdjust(&((*curr)->parent->parent),&(*root));
}
else if((*curr)->parent->parent->left->color==0)
{
cout<<"RRB";
RRB(&(*curr),&(*root));
// print(*root);
// getch();
}
}
}
}
}
}
void insertval(node **root,node **curr,int val,node *par)
{
if((*curr)->left==NULL||(*curr)->right==NULL)
{
node* temp = new node;
node* lnill = new node;
node* rnill = new node;
lnill->info = NULL;
lnill->left = (node*)NULL;
lnill->right = (node*)NULL;
lnill->parent = temp;
lnill->color = 0;
rnill->info = NULL;
rnill->left = (node*)NULL;
rnill->right = (node*)NULL;
rnill->parent = temp;
rnill->color = 0;
temp->info = val;
temp->left = (node*)lnill;
temp->right = (node*)rnill;
temp->parent = (node*)NULL;
temp->color = 1;
(*curr) = temp;
if(par!=NULL)
(*curr)->parent = par;
else
{
(*curr)->parent = (node*)NULL;
(*root) = (*curr);
(*root)->color=0;
}
RBTInsertAdjust(&(*curr),&(*root));
cout<<"Node inserted\n";
}
else if(((*curr)->info>val))
{
insertval(&(*root),&(*curr)->left,val,*curr);
}
else if((*curr)->info {
insertval(&(*root),&(*curr)->right,val,*curr);
}
else
cout<<"\nNode already Exists...";
}
void search(node * curr,int val)
{
static int flag = 0;
if(curr!=NULL)
{
search(curr->left,val);
if(val==curr->info)
{
setcolor(BLUE);
circle(curr->x,curr->y,15);
t=curr;
while(t->parent!=NULL)
{
line(t->x,t->y,t->parent->x,t->parent->y);
t=t->parent;
}
flag = 1;
}
search(curr->right,val);
}
}
void deleteval(node **root,node **curr)
{
node *temp = (*curr)->parent;
if((*curr)->info==(*root)->info)
temp = (node*)NULL;
node *y,*x;
if(((*curr)->left==NULL)||((*curr)->right==NULL))
y = (*curr);
else
y = successor((*curr));
if(y->left != NULL)
x = y->left;
else
x = y->right;
if(x != NULL)
x->parent = y->parent;
if(y->parent == NULL)
(*root) = x;
else if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
if(y != (*curr))
(*curr)->info = y->info;
}
void print1(node* curr)
{
if(curr!=NULL)
{
print1(curr->left);
cout<info<<" ";
print1(curr->right);
}
}
void main()
{
node* root;
root = (node*)NULL;
clrscr();
int ch;
int cnt = 0;
do
{
clrscr();
cout<<"\t\t\tRBT TREE\n";
cout<<"\n1.Insert element:";
cout<<"\n2.Print tree:";
cout<<"\n3.Delete element:";
cout<<"\n4.Search";
cout<<"\n5.Exit";
cout<<"\n\nEnter ur choice:";
// cin>>ch;
ch = 1;
cnt++;
if(cnt%500==0)
ch = 2;
int value;
int gd = DETECT,gm;
node *temp = NULL;
switch(ch)
{
case 1:
// cout<<"\nEnter the value to insert:";
// cin>>value;
value = cnt;
insertval(&root,&root,value,NULL);
break;
case 2:
clrscr();
// print(root);
print1(root);
getch();
break;
case 3:
cout<<"\nEnter the value to delete:";
cin>>value;
temp = NULL;
findval(&root,value,&temp);
if(temp == NULL)
{
cout<<"\nThe value does not exist:";
getch();
break;
}
deleteval(&root,&temp);
break;
case 4:
cout<<"\nEnter the element to search:";
int val;
cin>>val;
initgraph(&gd,&gm,"w:\\compiler\\tcpp\\bgi\\");
m = 0;
printtree(root,m);
drawlines(root);
search(root,val);
x = x1 = 20;
y = y1 = 10;
getch();
closegraph();
break;
case 5:
break;
default:
cout<<"\nEnter a valid choice:";
break;
}
// getch();
}while(cnt!=20000);
getch();
}
|
Project Feedbacks
|
No feedbacks found. Be the first to respond and make money from revenue sharing program.
|
|
|
| Post Feedback |
|
|
You must Sign In to post a feedback.
|
|
|
|
|
Advertise Here
|