Red Black-Tree (RB-Tree):
A red-black tree(RB-Tree) is a binary search tree with one extra attribute for each node: the colour, which is either red or black. It has following properties:
- Every node is either red or black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
C++ program to implement Red Black-Tree (RB-Tree):
#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<<"\nEnter 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<<"\nEmpty Tree." ; return ; } int x; cout<<"\nEnter 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<<"\nElement Not Found."; return ; } else { cout<<"\nDeleted Element: "<<p->key; cout<<"\nColour: "; if(p->color=='b') cout<<"Black\n"; else cout<<"Red\n"; if(p->parent!=NULL) cout<<"\nParent: "<<p->parent->key; else cout<<"\nThere is no parent of the node. "; if(p->right!=NULL) cout<<"\nRight Child: "<<p->right->key; else cout<<"\nThere is no right child of the node. "; if(p->left!=NULL) cout<<"\nLeft Child: "<<p->left->key; else cout<<"\nThere is no left child of the node. "; cout<<"\nNode 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<<"\nEmpty Tree."; return ; } if(p!=NULL) { cout<<"\n\t NODE: "; cout<<"\n Key: "<<p->key; cout<<"\n Colour: "; if(p->color=='b') cout<<"Black"; else cout<<"Red"; if(p->parent!=NULL) cout<<"\n Parent: "<<p->parent->key; else cout<<"\n There is no parent of the node. "; if(p->right!=NULL) cout<<"\n Right Child: "<<p->right->key; else cout<<"\n There is no right child of the node. "; if(p->left!=NULL) cout<<"\n Left Child: "<<p->left->key; else cout<<"\n There is no left child of the node. "; cout<<endl; if(p->left) { cout<<"\n\nLeft:\n"; display(p->left); } /*else cout<<"\nNo Left Child.\n";*/ if(p->right) { cout<<"\n\nRight:\n"; display(p->right); } /*else cout<<"\nNo Right Child.\n"*/ } } void RBtree::search() { if(root==NULL) { cout<<"\nEmpty Tree\n" ; return ; } int x; cout<<"\n 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<<"\nElement Not Found."; else { cout<<"\n\t FOUND NODE: "; cout<<"\n Key: "<<p->key; cout<<"\n Colour: "; if(p->color=='b') cout<<"Black"; else cout<<"Red"; if(p->parent!=NULL) cout<<"\n Parent: "<<p->parent->key; else cout<<"\n There is no parent of the node. "; if(p->right!=NULL) cout<<"\n Right Child: "<<p->right->key; else cout<<"\n There is no right child of the node. "; if(p->left!=NULL) cout<<"\n Left Child: "<<p->left->key; else cout<<"\n There is no left child of the node. "; cout<<endl; } } int main() { int ch,y=0; RBtree obj; do { cout<<"\n\t RED BLACK TREE " ; cout<<"\n 1. Insert in the tree "; cout<<"\n 2. Delete a node from the tree"; cout<<"\n 3. Search for an element in the tree"; cout<<"\n 4. Display the tree "; cout<<"\n 5. Exit " ; cout<<"\nEnter Your Choice: "; cin>>ch; switch(ch) { case 1 : obj.insert(); cout<<"\nNode Inserted.\n"; break; case 2 : obj.del(); break; case 3 : obj.search(); break; case 4 : obj.disp(); break; case 5 : y=1; break; default : cout<<"\nEnter a Valid Choice."; } cout<<endl; }while(y!=1); return 1; }
Sample Output for RB-Tree implementation:
RED BLACK TREE 1. Insert in the tree 2. Delete a node from the tree 3. Search for an element in the tree 4. Display the tree 5. Exit Enter Your Choice: 1 Enter key of the node to be inserted: 4 Node Inserted. RED BLACK TREE 1. Insert in the tree 2. Delete a node from the tree 3. Search for an element in the tree 4. Display the tree 5. Exit Enter Your Choice: 1 Enter key of the node to be inserted: 15 Node Inserted. RED BLACK TREE 1. Insert in the tree 2. Delete a node from the tree 3. Search for an element in the tree 4. Display the tree 5. Exit Enter Your Choice: 1 Enter key of the node to be inserted: 8 Node Inserted. RED BLACK TREE 1. Insert in the tree 2. Delete a node from the tree 3. Search for an element in the tree 4. Display the tree 5. Exit Enter Your Choice: 4 NODE: Key: 12 Colour: Black There is no parent of the node. Right Child: 15 Left Child: 4 Left: NODE: Key: 4 Colour: Black Parent: 12 Right Child: 8 There is no left child of the node. Right: NODE: Key: 8 Colour: Red Parent: 4 There is no right child of the node. There is no left child of the node. Right: NODE: Key: 15 Colour: Black Parent: 12 There is no right child of the node. There is no left child of the node. RED BLACK TREE 1. Insert in the tree 2. Delete a node from the tree 3. Search for an element in the tree 4. Display the tree 5. Exit Enter Your Choice: 5
Let is know in comments if you face any issue with the code and provide suggestions if any to improve the code regarding implementation of Red Black-Tree (RB-Tree) in C++ programming language.
Also Check: AVL Tree implementation in C++
I am trying to construct a tree with the following digits but it stuck @ 30
10,85,15,70,20,60,30,50,65,80,90,40,5 and 55
Same here
T-T I wanna cry .. I must write a Doc for this code but but T______T!!
what is wrong with this code !!!!
#include
using namespace std;
template
class RBtree
{
public:
struct node
{
T key;
node *parent;
char color;
node *left;
node *right;
};
node *root;
node *q;
RBtree()
{
q=NULL;
root=NULL;
}
void insert(T val);
void insertfix(node *);
void leftrotate(node *);
void rightrotate(node *);
void del(T val);
void delfix(node *);
void disp();
void display( node *);
void search(T val);
};
template
void RBtree::insert(T val)
{
node *p,*q;
node *t=new node;
t->key=val;
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->keykey)
p=p->right;
else
p=p->left;
}
t->parent=q;
if(q->keykey)
q->right=t;
else
q->left=t;
}
insertfix(t);
}
template
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!=NULL){
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{
t->parent->color=’b’;
g->color=’r’;
leftrotate(g);
}
}
else
{
if(t->parent->left==t)
{
t=t->parent;
rightrotate(t);
}
t->parent->color=’b’;
g->color=’r’;
leftrotate(g);
}
}
}
root->color=’b’;
}
}
template
void RBtree::del(T val)
{
if(root==NULL)
{
cout<key==val)
found=1;
if(found==0)
{
if(p->keyright;
else
p=p->left;
}
}
if(found==0)
{
cout<<"\nElement Not Found.";
return ;
}
else
{
cout<<"\nDeleted Element: "<key;
cout<color==’b’)
cout<<"Black\n";
else
cout<parent!=NULL)
cout<<"\nParent: "<parent->key;
else
cout<right!=NULL)
cout<<"\nRight Child: "<right->key;
else
cout<left!=NULL)
cout<<"\nLeft Child: "<left->key;
else
cout<<"\nThere is no left child of the node. ";
cout<left==NULL||p->right==NULL)
y=p;
else {
node *y1=NULL;
if(p->left!=NULL)
{
y1=p->left;
while(y1->right!=NULL)
y1=y1->right;
}
else
{
y1=p->right;
while(y1->left!=NULL)
y1=y1->left;
}
y=y1;
}
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’ and q!=NULL)
delfix(q);
}
}
template
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!=NULL && s->left!=NULL){
if(s->right->color==’b’&&s->left->color==’b’)
{
s->color=’r’;
p=p->parent;
//leftrotate(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);
}}
}
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->right!=NULL && s->left!=NULL){
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->color=’b’;
root->color=’b’;
p=root;
}
}
template
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->parent=NULL;
y->left=p;
p->parent=y;
}
}
template
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->parent=NULL;
y->right=p;
p->parent=y;
}
}
template
void RBtree::disp()
{
display(root);
}
template
void RBtree::display(node *p)
{
if(root==NULL)
{
cout<<"\nEmpty Tree.";
return ;
}
if(p!=NULL)
{
cout<<"\n\t NODE: ";
cout<<"\n Key: "<key;
cout<color==’b’)
cout<<"Black";
else
cout<parent!=NULL)
cout<<"\n Parent: "<parent->key;
else
cout<right!=NULL)
cout<<"\n Right Child: "<right->key;
else
cout<left!=NULL)
cout<<"\n Left Child: "<left->key;
else
cout<<"\n There is no left child of the node. ";
cout<left)
{
cout<left);
}
/*else
cout<right)
{
cout<right);
}
/*else
cout<<"\nNo Right Child.\n"*/
}
}
template
void RBtree::search(T val)
{
if(root==NULL)
{
cout<key==val)
found=1;
if(found==0)
{
if(p->keyright;
else
p=p->left;
}
}
if(found==0)
cout<<"\nElement Not Found.";
else
{
cout<<"\n\t FOUND NODE: ";
cout<<"\n Key: "<key;
cout<color==’b’)
cout<<"Black";
else
cout<parent!=NULL)
cout<<"\n Parent: "<parent->key;
else
cout<right!=NULL)
cout<<"\n Right Child: "<right->key;
else
cout<left!=NULL)
cout<<"\n Left Child: "<left->key;
else
cout<<"\n There is no left child of the node. ";
cout<<endl;
}
}
int main()
{
int ch,y=0, z;
RBtree obj;
do
{
cout<<"\n\t RED BLACK TREE " ;
cout<<"\n 1. Insert in the tree ";
cout<<"\n 2. Delete a node from the tree";
cout<<"\n 3. Search for an element in the tree";
cout<<"\n 4. Display the tree ";
cout<<"\n 5. Exit " ;
cout<>ch;
switch(ch)
{
case 1 :
cout<>z;
obj.insert(z);
cout<<"\nNode Inserted.\n";
break;
case 2 : cout<>z;
obj.del(z);
break;
case 3 : cout<>z;
obj.search(z);
break;
case 4 : obj.disp();
break;
case 5 : y=1;
break;
default : cout<<"\nEnter a Valid Choice.";
}
cout<<endl;
}while(y!=1);
return 1;
}
Just remove templates
its can only insert maximum 8 values.
Hi. I think something its wrong after left rotation function.
When i runn add 1,2,3 there is no node without the parent .
I think its need to check if you rotate the root you need to set his parent as NULL.