Red black Tree in c++
Red black tree in c++ are an evolution of binary search trees that aim to keep the tree balanced without affecting the complexity of the primitive operations. It is done by colouring each node in the tree with either red or black and preserving a set of properties that guarantee that the deepest path in the tree is not longer than twice the shortest one.
A red black tree is a binary search tree with the following properties:
Every node is coloured with either red or black colour.
All leaf (nil) nodes are coloured with black; if a node’s child is missing then we will assume that it has a nil child in that place and this nil child is always coloured black.
Both children of a red node must be black nodes.
Every path from a node n to a descendent leaf has the same number of black nodes (not counting node n). We call this number the black height of n, which is denoted by bh(n).
Using these properties, we can show in two steps that a red black tree which contains n nodes has a height of O(log n), thus all primitive operations on the tree will be of O(log n) since their order is a function of tree height.
First, notice that for a red black tree with height h, bh(root) is at least h/2 by property 3 above (as each red node strictly requires black children).
The next step is to use the following lemma:Lemma: A subtree rooted at node v has at least 2^bh(v) – 1 internal nodes
Proof by induction: The basis is when h(v) = 0, which means that v is a leaf node and therefore bh(v) = 0 and the subtree rooted at node v has 2^bh(v)-1 = 2^0-1 = 1-1 = 0 nodes.
Inductive hypothesis: if node v1 with height x has 2^bh(v1)-1 internal nodes then node v2 with height x+1 has 2^bh(v2)-1
For any non-leaf node v (height > 0) we can see that the black height of any of its two children is at least equal to bh(v)-1 — if the child is black, that is, otherwise it is equal to bh(v) . By applying the hypothesis above we conclude that each child has at least 2^[bh(v)-1]-1 internal nodes, accordingly node v has at least
2^[bh(v)-1]-1 + 2^[bh(v)-1]-1 + 1 = 2^bh(v)-1
internal nodes, which ends the proof.
By applying the lemma to the root node (with bh of at least h/2, as shown above) we get
n >= 2^(h/2) – 1
where n is the number of internal nodes of a red-black tree (the subtree rooted at the root). Playing with the equation a little bit we get h <= 2 log (n+1), which guarantees the logarithmic bound of red-black trees in c++.
Rotations :
How does inserting or deleting nodes affect a red-black tree in c++ ? To ensure that its color scheme and properties don’t get thrown off, red-black trees employe a key operation known as rotation. Rotation is a binary operation, between a parent node and one of its children, that swaps nodes and modify their pointers while preserving the in order traversal of the tree (so that elements are still sorted).
There are two types of rotations: left rotation and right rotation. Left rotation swaps the parent node with its right child, while right rotation swaps the parent node with its left child. Here are the steps involved in for left rotation (for right rotations just change “left” to “right” below):
Assume node x is the parent and node y is a non-leaf right child.
Let y be the parent and x be its left child.
Let y’s left child be x’s right child.
Operations on red-black tree (insertion, deletion and retrieval)
Red-black tree operations are a modified version of BST( binary search tree ) operations, with the modifications aiming to preserve the properties of red-black trees in c++ while keeping the operations complexity a function of tree height.
Red black tree insertion:
Inserting a node in a red-black tree in c++ is a two step process:
A BST insertion, which takes O(log n) as shown before.
Fixing any violations to red-black tree properties that may occur after applying step 1. This step is O(log n) also, as we start by fixing the newly inserted node, continuing up along the path to the root node and fixing nodes along that path. Fixing a node is done in constant time and involves re-coloring some nodes and doing rotations.
Accordingly the total running time of the insertion process is O(log n). Figure 7 shows the red-black tree in figure 5 before and after insertion of a node with value 4. You can see how the swap operations modified the tree structure to keep it balanced.
Red black tree deletion:
The same concept behind red-black tree insertions applies here. Removing a node from a red-black tree makes use of the BST deletion procedure and then restores the red-black tree properties in O(log n). The total running time for the deletion process takes O(log n) time, then, which meets the complexity requirements for the primitive operations.
Red-black tree retrieval:
Retrieving a node from a red-black tree doesn’t require more than the use of the BST procedure, which takes O(log n) time.
Program for red black tree in c++ :
#include<iostream>
using namespace std;
typedef enum {RED, BLACK} nodecolor ;
struct node
{
node * left;
node * right;
node * parent;
node * nil;
node * root;
node * key;
int data;
nodecolor color;
};
node *root=NULL;
int choice;
void PrintMenu()
{
cout<<"\t\tR E D B L A C K T R E E"
<<endl<<endl;
cout<<"\t\t [1] INSERT "<<endl;
cout<<"\t\t [2] DELETE "<<endl;
cout<<"\t\t [3] DISPLAY "<<endl;
cout<<"\t\t [4] INORDER TREE WALK "
<<endl;
cout<<"\t\t [5] EXIT"<<endl;
}
void LeftRotate(node* &tree, node* x)
{
node* y;
node* nil=tree->nil;
y=x->right;
x->right=y->left;
if (y->left != nil)
y->left->parent=x;
y->parent=x->parent;
if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
}
void RightRotate(node* &tree, node* y)
{
node* x;
node* nil=tree->nil;
x=y->left;
y->left=x->right;
if (nil != x->right)
x->right->parent=y;
x->parent=y->parent;
if( y == y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
x->right=y;
y->parent=x;
}
void InsertFixUp(node * &tree, node *z)
{
node *nil=tree->nil;
node *y;
while (z->parent->color==RED)
{
if(z->parent==z->parent->parent->left)
{
y=z->parent->parent->right;
if(y->color==RED)
{
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;
}
else if(z=z->parent->right)
{
z=z->parent;
LeftRotate(tree,z);
}
z->parent->color=BLACK;
z->parent->parent->color=RED;
RightRotate(tree,z->parent->parent);
}
else
{
y=z->parent->parent->left;
if(y->color==RED)
{
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;
}
else if(z=z->parent->left)
{
z=z->parent;
LeftRotate(tree,z);
}
z->parent->color=BLACK;
z->parent->parent->color=RED;
RightRotate(tree,z->parent->parent);
}
}
}
void Insert(node * &tree, node *&z)
{
node* nil=tree->nil;
node* root=tree->root;
node *y;
node *x;
y=tree->nil;
x=tree->root;
while(x!=tree->nil)
{
y=x;
if((z->key)<(x->key))
x=x->left;
else
x=x->right;
}
y=z->parent;
if(y=tree->nil)
z=tree->root;
else if((z->key)<(y->key))
z=y->left;
else
z=y->right;
z->left=tree->nil;
z->right=tree->nil;
z->color=RED;
InsertFixUp(tree,z);
}
void DeleteFixUp(node * &tree, node *x)
{
node *nil=tree->nil;
node *root=tree->nil;
node *w;
while(x!=tree->root&&x->color==BLACK)
{
if(x==x->parent->left)
{
w=x->parent->right;
if(w->color==RED)
{
w->color=BLACK;
x->parent->color=RED;
LeftRotate(tree,x->parent);
w=x->parent->right;
}
if((w->left->color==BLACK)&&(w->right->
color==BLACK))
{
w->color=RED;
x=x->parent;
}
else if(w->right->color==BLACK)
{
w->left->color=BLACK;
w->color=RED;
RightRotate(tree,w);
w=x->parent->right;
}
w->color=x->parent->color;
x->parent->color=BLACK;
LeftRotate(tree,x->parent);
x=tree->root;
}
else
{
w=x->parent->left;
if(w->color==RED)
{
w->color=BLACK;
x->parent->color=RED;
LeftRotate(tree,x->parent);
w=x->parent->left;
}
if((w->right->color==BLACK)&&(w->left->
color==BLACK))
{
w->color=RED;
x=x->parent;
}
else if(w->left->color==BLACK)
{
w->right->color=BLACK;
w->color=RED;
RightRotate(tree,w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=BLACK;
LeftRotate(tree,x->parent);
x=tree->root;
}
}
}
node *Delete(node * &tree, node *z)
{
node *root=tree->root;
node *nil=tree->nil;
node *y;
node *x;
if((z->left==tree->nil)||(z->right==
tree->nil))
y=z;
else
//y=TreeSuccessor(z);
if(y->left!=tree->nil)
x=y->left;
else
x=y->right;
x->parent=y->parent;
if(y->parent=tree->nil)
tree->root=x;
else if(y=y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
if(y!=z)
z->key=y->key;
if(y->color==BLACK)
DeleteFixUp(tree,x);
return y;
}
void GetChoice()
{
cout<<"Enter your choice:";
cin>>choice;
switch(choice)
{
case 1:
int again;
do
{
cout<<"Enter data to be inserted:";
int data;
cin>>data;
cout<<"Insert again?[0 if no]:";
cin>>again;
}while(again!=0);
break;
case 2:
break;
case 3:
break;
case 4:
break;
case 5:
break;
}
}
int main()
{
do
{
PrintMenu();
GetChoice();
}while(choice!=5);
return 0;
}
