Simple Red Black-Tree(RB-Tree) implementation in C++

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:

  1. Every node is either red or black.
  2. Every leaf (NULL) is black.
  3. If a node is red, then both its children are black.
  4. Every simple path from a node to a descendant leaf contains the same number of black nodes.

rb-tree

 

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++

8 thoughts on “Simple Red Black-Tree(RB-Tree) implementation in C++”

    • #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;
      }

      Reply
  1. 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.

    Reply

Leave a Reply to Harin Cancel reply