Write a program in C++ that creates a Red Black tree. Your program should have a
ID: 3591440 • Letter: W
Question
Write a program in C++ that creates a Red Black tree. Your program should have a search, insert, delete and display operation. You should list these options in a menu to the user. Submit your source code.
For the display function you can print one node with its parent and children and their respective colors (given the key of the node), or you can print the entire tree.
For each insertion/deletion you must display the following:
- Initial position of the key into the Red-Black tree
- List of violated Red-black tree properties
- The necessary rotations and color assignments
Explanation / Answer
#include<iostream>
using namespace std;
struct node
{
int key;
node *parent;
char color;
node *left;
node *right;
};
class RBtree
{
node *root;
node *q;
public :
RBtree()
{
q=NULL;
root=NULL;
}
void insert();
void insertfix(node *);
void leftrotate(node *);
void rightrotate(node *);
void del();
node* successor(node *);
void delfix(node *);
void disp();
void display( node *);
void search();
};
void RBtree::insert()
{
int z,i=0;
cout<<" Enter key of the node to be inserted: ";
cin>>z;
node *p,*q;
node *t=new node;
t->key=z;
t->left=NULL;
t->right=NULL;
t->color='r';
p=root;
q=NULL;
if(root==NULL)
{
root=t;
t->parent=NULL;
}
else
{
while(p!=NULL)
{
q=p;
if(p->key<t->key)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->key<t->key)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
void RBtree::insertfix(node *t)
{
node *u;
if(root==t)
{
t->color='b';
return;
}
while(t->parent!=NULL&&t->
parent->color=='r')
{
node *g=t->parent->parent;
if(g->left==t->parent)
{
if(g->right!=NULL)
{
u=g->right;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->right==t)
{
t=t->parent;
leftrotate(t);
}
t->parent->color='b';
g->color='r';
rightrotate(g);
}
}
else
{
if(g->left!=NULL)
{
u=g->left;
if(u->color=='r')
{
t->parent->color='b';
u->color='b';
g->color='r';
t=g;
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
t->parent->color='b';
g->color='r';
leftrotate(g);
}
}
root->color='b';
}
}
void RBtree::del()
{
if(root==NULL)
{
cout<<" Empty Tree." ;
return ;
}
int x;
cout<<" Enter the key of the node to be deleted: ";
cin>>x;
node *p;
p=root;
node *y=NULL;
node *q=NULL;
int found=0;
while(p!=NULL&&found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
{
cout<<" Element Not Found.";
return ;
}
else
{
cout<<" Deleted Element: "<<p->key;
cout<<" Colour: ";
if(p->color=='b')
cout<<"Black ";
else
cout<<"Red ";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<" Node Deleted.";
if(p->left==NULL||p->right==NULL)
y=p;
else
y=successor(p);
if(y->left!=NULL)
q=y->left;
else
{
if(y->right!=NULL)
q=y->right;
else
q=NULL;
}
if(q!=NULL)
q->parent=y->parent;
if(y->parent==NULL)
root=q;
else
{
if(y==y->parent->left)
y->parent->left=q;
else
y->parent->right=q;
}
if(y!=p)
{
p->color=y->color;
p->key=y->key;
}
if(y->color=='b')
delfix(q);
}
}
void RBtree::delfix(node *p)
{
node *s;
while(p!=root&&p->color=='b')
{
if(p->parent->left==p)
{
s=p->parent->right;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
leftrotate(p->parent);
s=p->parent->right;
}
if(s->right->color=='b'&&s->left->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->right->color=='b')
{
s->left->color=='b';
s->color='r';
rightrotate(s);
s=p->parent->right;
}
s->color=p->parent->color;
p->parent->color='b';
s->right->color='b';
leftrotate(p->parent);
p=root;
}
}
else
{
s=p->parent->left;
if(s->color=='r')
{
s->color='b';
p->parent->color='r';
rightrotate(p->parent);
s=p->parent->left;
}
if(s->left->color=='b'&&s->right->color=='b')
{
s->color='r';
p=p->parent;
}
else
{
if(s->left->color=='b')
{
s->right->color='b';
s->color='r';
leftrotate(s);
s=p->parent->left;
}
s->color=p->parent->color;
p->parent->color='b';
s->left->color='b';
rightrotate(p->parent);
p=root;
}
}
p->color='b';
root->color='b';
}
}
void RBtree::leftrotate(node *p)
{
if(p->right==NULL)
return ;
else
{
node *y=p->right;
if(y->left!=NULL)
{
p->right=y->left;
y->left->parent=p;
}
else
p->right=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->left=p;
p->parent=y;
}
}
void RBtree::rightrotate(node *p)
{
if(p->left==NULL)
return ;
else
{
node *y=p->left;
if(y->right!=NULL)
{
p->left=y->right;
y->right->parent=p;
}
else
p->left=NULL;
if(p->parent!=NULL)
y->parent=p->parent;
if(p->parent==NULL)
root=y;
else
{
if(p==p->parent->left)
p->parent->left=y;
else
p->parent->right=y;
}
y->right=p;
p->parent=y;
}
}
node* RBtree::successor(node *p)
{
node *y=NULL;
if(p->left!=NULL)
{
y=p->left;
while(y->right!=NULL)
y=y->right;
}
else
{
y=p->right;
while(y->left!=NULL)
y=y->left;
}
return y;
}
void RBtree::disp()
{
display(root);
}
void RBtree::display(node *p)
{
if(root==NULL)
{
cout<<" Empty Tree.";
return ;
}
if(p!=NULL)
{
cout<<" NODE: ";
cout<<" Key: "<<p->key;
cout<<" Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<endl;
if(p->left)
{
cout<<" Left: ";
display(p->left);
}
/*else
cout<<" No Left Child. ";*/
if(p->right)
{
cout<<" Right: ";
display(p->right);
}
/*else
cout<<" No Right Child. "*/
}
}
void RBtree::search()
{
if(root==NULL)
{
cout<<" Empty Tree " ;
return ;
}
int x;
cout<<" Enter key of the node to be searched: ";
cin>>x;
node *p=root;
int found=0;
while(p!=NULL&& found==0)
{
if(p->key==x)
found=1;
if(found==0)
{
if(p->key<x)
p=p->right;
else
p=p->left;
}
}
if(found==0)
cout<<" Element Not Found.";
else
{
cout<<" FOUND NODE: ";
cout<<" Key: "<<p->key;
cout<<" Colour: ";
if(p->color=='b')
cout<<"Black";
else
cout<<"Red";
if(p->parent!=NULL)
cout<<" Parent: "<<p->parent->key;
else
cout<<" There is no parent of the node. ";
if(p->right!=NULL)
cout<<" Right Child: "<<p->right->key;
else
cout<<" There is no right child of the node. ";
if(p->left!=NULL)
cout<<" Left Child: "<<p->left->key;
else
cout<<" There is no left child of the node. ";
cout<<endl;
}
}
int main()
{
int ch,y=0;
RBtree obj;
do
{
cout<<" RED BLACK TREE " ;
cout<<" 1. Insert in the tree ";
cout<<" 2. Delete a node from the tree";
cout<<" 3. Search for an element in the tree";
cout<<" 4. Display the tree ";
cout<<" 5. Exit " ;
cout<<" Enter Your Choice: ";
cin>>ch;
switch(ch)
{
case 1 : obj.insert();
cout<<" Node Inserted. ";
break;
case 2 : obj.del();
break;
case 3 : obj.search();
break;
case 4 : obj.disp();
break;
case 5 : y=1;
break;
default : cout<<" Enter a Valid Choice.";
}
cout<<endl;
}while(y!=1);
return 1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.