// Author : Saket Soni, MTech CS, 1st yr, roll - mtc0420
// Topic : Iterative implementation of Binary Search Red-Black tree
// Platform : Windos, VC++ 6.0
#include
#include
using namespace std;
#include
//#define DEBUG // to enable or disable dubuging
namespace RedBlack // AVL namespace for the whole structure
{
class RBTree // class for modelling the AVL tree
{
public:
enum Color_type { // color constants
Red,
Black
};
private:
class RBNode // class for modelling the AVL node
{
public:
static int mode; // for display mode
int nodeNo; // node number of the node
public:
int key; // key
Color_type color; // color of the node
RBNode *left; // pointer to left child
RBNode *right; // pointer to right child
RBNode *parent; // pointer to parent
void *ptrData;
public:
RBNode(int k, void * const pData, RBNode *aNull):key(k),color(Red),
nodeNo(0),left(aNull),right(aNull),parent(aNull),ptrData(pData)
{ } // default constructor
private:
RBNode(RBNode &a):key(a.key),color(Red),nodeNo(0),
left(NULL),right(NULL),parent(NULL),ptrData(NULL)
{ } // use of this constructor is PROHIBITED!!!
public:
friend ostream & operator<<( ostream & o, const RBNode *n)
{
if ( mode == 0 )
o << setw(3) << n->key << ":" << setw(3) << n->nodeNo << ", ";
else
{
o << setw(3) << n->key << ":";
if ( n->color == Red )
o << " Red, ";
else
o << " Blk, ";
}
return o;
}
private:
RBNode& operator = ( const RBNode & n ) {
key = n.key; // use of = operator is PROHIBITED!!!
if ( ptrData )
delete[] ptrData;
ptrData = n.ptrData;
return *this;
}
};
private:
RBNode *root; // root of the tree
private:
static RBNode RB_NullNode; // RB_NullNode
static RBNode *NullNode; // pointer to RB_NullNode
private:
void preorder ( RBNode *r ) { // preorder traversal of the tree
if ( r != NullNode ) {
cout << r;
preorder(r->left);
preorder(r->right);
}
}
void inorder ( RBNode *r ) { // inorder traversal of the tree
if ( r != NullNode ) {
inorder(r->left);
cout << r;
inorder(r->right);
}
}
private:
void clear( RBNode *r ) { // for deleting all the nodes in
if ( r != NullNode ) { // the tree, it does not deletes
clear(r->left); // the data pointed to by pointer
clear(r->right); // ptrData within the nodes
delete r;
}
}
private:
void reCalNodeNo( RBNode *r ) // for calculating the node numbers
{ // of the childrens of r, r must not
if ( r->left != NullNode ) { // be null
r->left->nodeNo = r->nodeNo * 2;
reCalNodeNo(r->left);
}
if ( r->right != NullNode ) {
r->right->nodeNo = r->nodeNo * 2 + 1;
reCalNodeNo(r->right);
}
}
public:
RBTree():root(NullNode) // tree constructor
{
RB_NullNode.left = NullNode;
RB_NullNode.right = NullNode;
RB_NullNode.parent = NullNode;
RB_NullNode.color = Black;
}
public:
void show() { // prints the tree
cout << "Tree :" << endl;
cout << "preorder with color ..." << endl; RBNode::mode = 1;
preorder(root); cout << endl;
cout << "inorder with node numbers ... " << endl; RBNode::mode = 0;
inorder (root); cout << endl;
}
private:
bool check( RBNode *ptr ) // to check the validity of the tree
{ // rooted at ptr
if ( ptr != NullNode )
{
if ( ptr->color == Red )
if ( ptr->left->color == Red || ptr->left->color == Red )
return false;
return check(ptr->left) && check(ptr->right);
}
return true;
}
RBNode* search(int key, RBNode *& ppfather)
{ // searches for a key and returns
RBNode *ptr=root, *fptr=NullNode; // a pointer to it, also stores the
while ( ptr != NullNode ) { // address of the father at location
fptr = ptr; // ppfather, the function is private
if ( ptr->key < key ) // because it is to be used only with
ptr = ptr->right; // in the class
else if ( ptr->key > key )
ptr = ptr->left;
else {
ppfather = fptr;
return ptr;
}
}
ppfather = fptr;
return NullNode;
}
RBNode* search(int key) // same as the previous function, except
{ // it dosen't tell the address of the
RBNode *ptr= root; // parent of the ptr, hence you can not
while ( ptr != NullNode ) { // use this function to find the location
if ( ptr->key < key ) // where the new node is to be inserted!
ptr = ptr->right;
else if ( ptr->key > key )
ptr = ptr->left;
else
return ptr;
}
return NullNode;
}
void linkWithParent(RBNode *ptr, RBNode *optr )// links the parent of ptr with ptr, ptr
{ // must have the address of its parent and ptr
if ( ptr->parent != NullNode ) // must not be null, if parent of ptr is null,
{ // then root is set to ptr. Here 'optr' is the
if ( ptr->parent->left == optr ) { // previous child of the now parent of ptr
ptr->parent->left = ptr;
ptr->nodeNo = ptr->parent->nodeNo * 2; // if left child
}
else {
ptr->parent->right = ptr;
ptr->nodeNo = ptr->parent->nodeNo * 2 + 1; // if right child
}
}
else {
root = ptr;
ptr->nodeNo = 1;
}
}
void rotateLeft( RBNode *fptr ) // rotates fptr left
{
RBNode *ptr = fptr->right;
ptr->parent = fptr->parent;
fptr->right = ptr->left;
ptr->left = fptr;
fptr->right->parent = fptr;
fptr->parent = ptr;
linkWithParent(ptr,fptr); // to link with the parent
}
void rotateRight( RBNode *fptr ) // rotates fptr right
{
RBNode *ptr = fptr->left;
ptr->parent = fptr->parent;
fptr->left = ptr->right;
ptr->right = fptr;
fptr->left->parent = fptr;
fptr->parent = ptr;
linkWithParent(ptr,fptr); // to link with the parent
}
private:
void makeRedBlkAfterInsertion( RBNode* ptr )
{
RBNode *fptr = ptr->parent;
RBNode *gptr;
while ( fptr != NullNode ) // stop climbing if root is reached
{
if ( fptr->color == Black )
return;
else if ( fptr->right == ptr ) // if ptr is right child of fptr
{
gptr = fptr->parent;
if ( gptr->left == fptr ) // if fptr is left child of gptr
{
if ( gptr->right->color == Black ) // if gptr's right child is black
{
rotateLeft(fptr);
rotateRight(gptr); // double rotate right
gptr->color = Red;
ptr->color = Black;
if ( root == ptr ) // if root then set color to black
root->color = Black;
reCalNodeNo(ptr);
return; // root of subtree is black so return
}
else { // if gptr's right child is red
gptr->right->color = Black; // just swap color
fptr->color = Black;
gptr->color = Red;
ptr = gptr; // climb up the tree
}
}
else // if fptr is right child of gptr
{
if ( gptr->left->color == Black ) // gptr's left child is black
{
rotateLeft(gptr); // rotate left
gptr->color = Red;
fptr->color = Black;
reCalNodeNo(fptr);
return; // root of subtree is black so return
}
else { // gptr's left child is red
gptr->left->color = Black;
fptr->color = Black; // just swap colors
gptr->color = Red;
ptr = gptr;
}
}
}
else // if ptr is left child of fptr
{
gptr = fptr->parent;
if ( gptr->right == fptr ) // if fptr is right child of gptr
{
if ( gptr->left->color == Black ) // if gptr's left child is black
{
rotateRight(fptr);
rotateLeft(gptr); // double rotate left
gptr->color = Red;
ptr->color = Black;
if ( root == ptr ) // if root then set color to black
root->color = Black;
reCalNodeNo(ptr);
return; // root of subtree is black so return
}
else { // if gptr's left child is red
gptr->left->color = Black; // just swap color
fptr->color = Black;
gptr->color = Red;
ptr = gptr; // climb up the tree
}
}
else // if fptr is left child of gptr
{
if ( gptr->right->color == Black ) // gptr's right child is black
{
rotateRight(gptr); // rotate right
gptr->color = Red;
fptr->color = Black;
reCalNodeNo(fptr);
return; // root of subtree is black so return
}
else { // gptr's right child is red
gptr->right->color = Black;
fptr->color = Black; // just swap colors
gptr->color = Red;
ptr = gptr;
}
}
}
fptr = ptr->parent; // find new father after climbing
} // end of while
root->color = Black; // if control reaches here, then it means
reCalNodeNo(root); // that ptr is root, and fptr is NullNode,
// and root must always be black
}
void makeRedBlkHeightDecreased( RBNode *ptr )
{
RBNode *fptr = ptr->parent;
RBNode *tptr;
while ( ptr != root && ptr->color == Black ) // if ptr is not root and ptr is not black
{
if ( ptr == fptr->left ) // if ptr is left child of fptr
{
tptr = fptr->right; // tptr is uncle of ptr
if ( tptr->color == Red ) // if tptr is red
{
tptr->color = Black;
fptr->color = Red;
rotateLeft(fptr); // rotate left
tptr = fptr->right;
}
if ( tptr->left->color == Black // if both children of tptr are black
&& tptr->right->color == Black ) // then set tptr to red
{
tptr->color = Red;
ptr = fptr;
}
else // if atleast one non black child of tptr
{
if ( tptr->right->color == Black ) // if right child of tptr is black
{
tptr->left->color = Black;
tptr->color = Red;
rotateRight(tptr); // rotate right
tptr = fptr->right;
}
tptr->color = fptr->color;
fptr->color = Black;
tptr->right->color = Black;
rotateLeft(fptr); // rotate left
ptr = root; // new ptr is now root, i.e. to break
}
}
else // if ptr is right child of fptr
{
tptr = fptr->left; // tptr is uncle of ptr
if ( tptr->color == Red ) // if tptr is red
{
tptr->color = Black;
fptr->color = Red;
rotateRight(fptr); // rotate right
tptr = fptr->left;
}
if ( tptr->right->color == Black // if both children of tptr are black
&& tptr->left->color == Black ) // then set tptr to red
{
tptr->color = Red;
ptr = fptr;
}
else // if atleast one non black child of tptr
{
if ( tptr->left->color == Black ) // if left child of tptr is black
{
tptr->right->color = Black;
tptr->color = Red;
rotateLeft(tptr); // rotate left
tptr = fptr->left;
}
tptr->color = fptr->color;
fptr->color = Black;
tptr->left->color = Black;
rotateRight(fptr); // rotate right
ptr = root; // new ptr is now root, i.e. to brak
}
}
} // end of while
reCalNodeNo(ptr); // recalculate node nubmers
ptr->color = Black; // root must be black
}
public:
bool searchKey(int key, void *& ptrData ) // searches for a key and returns
{ // a reference to its data
RBNode *ptr;
if ( (ptr=search(key)) != NullNode ) { // search for key
ptrData = ptr->ptrData; // return reference to data
return true;
}
return false;
}
void * replaceData(int key, void* const ptrData)
{ // replaces old data of a key with new data,
RBNode *ptr; // a reference to old data is returned
void *ptrOldData = NULL;
if ( !ptrData ) // why replace with NULL DATA?
return NULL;
if ( (ptr=search(key)) != NullNode ) { // search for key
ptrOldData = ptr->ptrData; // return old data
ptr->ptrData = ptrData; // replace with new data
}
return ptrOldData;
}
bool insertKey(int key, void * const ptrData )
{ // returns false if key already exits
RBNode *ptr, *fptr;
if ( !ptrData ) // why insert NULL DATA?
return false;
if ( search(key,fptr) != NullNode ) // search for new key and find
return false; // where to insert it
ptr = new RBNode(key,ptrData,NullNode); // create new node
ptr->parent = fptr; // and insert as a left or
if ( fptr != NullNode ) // right child of the father
{
if ( fptr->key < key )
{
fptr->right = ptr;
ptr->nodeNo = fptr->nodeNo * 2 + 1;
}
else {
fptr->left = ptr;
ptr->nodeNo = fptr->nodeNo * 2;
}
}
else { // if father is null
root = ptr; // then the new node is the root
root->nodeNo = 1;
root->color = Black; // because root must always be black
return true;
}
ptr->color = Red; // because new node is inserted as red
makeRedBlkAfterInsertion(ptr); // make the disformed tree Red Black
return true;
}
bool deleteKey(int key, void *& ptrOldData)
{
RBNode *ptr, *tptr;
if ( (ptr = search(key)) == NullNode ) // if key dosn't exits return false
return false;
ptrOldData = ptr->ptrData;
if ( ptr->left != NullNode && ptr->right != NullNode )// if ptr has two children
{
tptr = ptr->right;
while ( tptr->left != NullNode ) // then search for its inorder successor
tptr = tptr->left;
ptr->key = tptr->key; // replace contents of ptr with
ptr->ptrData = tptr->ptrData; // that of its inorder successor,
ptr = tptr; // now node to be deleted is tptr
}
tptr = ( ptr->left != NullNode ) ? // now tptr points to the either of the
ptr->left : ptr->right; // left or the right child, or is null
// if both left and right are null
tptr->parent = ptr->parent; // delete ptr from the tree
if ( ptr == root ) {
root = tptr; // ptr is root, then root must be set
root->nodeNo = 1; // to tptr
reCalNodeNo(root);
root->color = Black;
}
else
{
if ( tptr->parent->left == ptr ) { // if ptr was left child
tptr->parent->left = tptr;
tptr->nodeNo = tptr->parent->nodeNo * 2;
}
else { // else if ptr was right child
tptr->parent->right = tptr;
tptr->nodeNo = tptr->parent->nodeNo * 2 + 1;
}
if ( ptr->color == Black ) // if not red then black height has decreased
makeRedBlkHeightDecreased(tptr); // make the disformed tree Red Black
}
delete ptr;
return true;
}
bool checkValidity() { // to check the validity of the red Black tree
return check(root);
}
public:
~RBTree() { // Tree destructor, deletes the
clear(root); // tree structure, but retains the
} // data pointed to by the tree
};
int RBTree::RBNode::mode = 0;
RBTree::RBNode RBTree::RB_NullNode(0,NULL,NULL);
RBTree::RBNode* RBTree::NullNode = &RBTree::RB_NullNode;
}
int menu() // to present a menu to the user
{ // and to read his option
int option;
while ( true )
{
cout << "Menu" << endl
<< "1. Insert elements randomly" << endl
<< "2. Insert elements manualy" << endl
<< "3. Delete elements" << endl
<< "4. Show Tree" << endl
<< "5. Check Validity" << endl
<< "6. Exit" << endl
<< "Enter option : ";
if ( cin >> option )
break;
else {
cin.clear(); // for typographical errors
while ( cin.get() != '\n' );
}
}
return option;
}
int main()
{
RedBlack::RBTree tree; // tree object
int dummy = 0; // dummy data
int n, k, key;
void *ptr; // pointer to dummy data
srand(time(0)); // initializing randomizer
while ( true )
{
switch( menu() ) // read from menu
{
case 1: // for random insertion
while ( true ) {
cout << "Enter number of elements to enter : ";
cin >> n;
if ( cin.fail() ) { // for typographical errors
cin.clear();
while ( cin.get() != '\n' );
}
else break;
}
cout << "Inserting ..." << endl;
for ( k = 0 ; k < n ; ) {
key = (rand()*1000.0)/RAND_MAX; // generate random number
if ( tree.insertKey(key,(void*)&dummy) ) {
cout << setw(8) << key;
k++; // increment only if insert succeeds,
} // i.e. key does not already exist
}
cout << endl;
break;
case 2: // for manual insertion
cout << "Enter elements (quit input with \'x\') : " << endl;
while ( cin >> key ) {
#ifdef DEBUG
cout << "Inserting ... " << key << endl;
#endif
if ( !tree.insertKey(key,(void*)&dummy) )
cout << "Error : Cannot insert element : " << key
<< ", element already exist!" << endl;
#ifdef DEBUG
tree.show();
#endif
}
cin.clear(); // for typographical errors
while ( cin.get() != '\n' );
break;
case 3: // for deletion
cout << "Enter elements (quit input with \'x\') : " << endl;
while ( cin >> key ) {
#ifdef DEBUG
cout << "Deleting ... " << key << endl;
#endif
if ( !tree.deleteKey(key,ptr) ) // if key dosen't exist show error
cout << "Error : Cannot delete element : " << key
<< ", element dosen't exist!" << endl;
#ifdef DEBUG
tree.show();
#endif
}
cin.clear(); // for typographical errors
while ( cin.get() != '\n' );
break;
case 4:
tree.show(); // for displaying tree
break;
case 5: // for validity check
if ( tree.checkValidity() )
cout << "The tree is Red Black." << endl;
else
cout << "The tree is not Red Black." << endl;
break;
case 6: // for exiting program
return 0;
default:
cout << "Incorrect Input!!" << endl; // for incorrect option
break;
}
}
return 0;
}