Red Black Tree

Red Black Tree

A red-black tree is referred as self-balancing binary search tree. The tree was invented by Rudolf Bayer in 1972. In red-black, each node stores an extra bit that determines the color of the node in red-black tree either red or black. These colors determine that the tree remains balanced or not, while performing insertions and deletions. The red-black tree is used to reduce the number of rotations while inserting and deleting the node and try to maintain the complexity around O(log n), where n is total number elements in the red-black tree.

Why Red-Black Trees

If we talk about Binary Search Tree, then its operations (e.g. insert, delete, search etc.) generally takes O(log n) time where n is the total number of nodes in binary search tree. if we are using skewed binary tree, then the cost of these operations may become O(n). To overcome this problem, we have another option which is called AVL trees, then we need of red-black trees. To answer this question, we need to consider the situation of AVL trees, the AVL trees don’t provide the guarantee that how many rotations are required to balance the height of AVL tree but in red-black trees, they provide guarantee that maximum two rotations are required to balance the height of red-black tree. So, we can say if your application involves more insertions and deletions, then Red-Black should be used and if searching is frequent operation and insertions and deletions are less frequent, then AVL trees should be used over Red-Black trees

Properties of Red-Black Trees

• Referred is a self-balancing Binary Search Tree
• Every node is either Red or Black
• Root is always Black
• Every leaf which is NILL is Black
• If node is Red then its children are Black
• Every path from a node to any of its descendent NILL node has same number of Black nodes.
• The height of the red-black if it has n node, is h<=2 log(n+1)

Operations on Red-Black Trees

• Insertion:

For inserting value in red-black tree, then we should follow some steps:

1. If the tree has no node or empty, then create new node as the root node with color black by the help of an extra bit.

2. If tree has some nodes or non-empty, then create new node as leaf node with color red.

3. If the parent of new node is black, then exit.

4. If the parent of new node is red, then check the color of parent’s sibling of new node.

a. If color is black or null, then do suitable rotation and recolor of that node.

b. If color is red, then recolor and also check if parent’s parent of new node is not root node, then recolor it and recheck.

• Deletion:

For deleting value from red-black tree, then we should follow some steps:

     1. If the node which you want to delete is red, then we simply delete it.

2. If the node that we are going to delete is root node and also it is double black (means color of it and its child is black called double black), then just delete it.

 3. If double black’s sibling is black, and both its children are black, then follow the steps:

• Remove double black
• Add black to its parent(P)
• If p is red it becomes black
• If p is black it becomes double black
• Make its sibling red
• if still double black exits, apply other cases

4. If double black’s sibling is red.

• Swap colors of parent and its sibling
• Rotate parent in double black direction
• re-apply cases

5.  Double black’s sibling is black, sibling’s child who is far from double black is black, but near child of double black is red, then follow the steps:

• Swap color of double black’s sibling and sibling’s child who is near to double black.
• Rotate sibling in opposite direction to double black
• apply case 6

6. Double black’s sibling is black and far child is red, then follow the steps:

• Swap color of parent and sibling
• Rotate Parent in double black’s direction
• Remove double black
• Change color of red child to black

• Searching:

Search in red-black tree is same as the binary tree because red-black a kind of binary search tree. Suppose ‘k’ be the key which we want to search in red-black Tree. In this, we start from the root node and traverse each internal or non-leaf node, if that internal node contains the key ‘k’ which we are searching, then we simply return the node. Otherwise, we compare ‘k’ with the root node and go down to the appropriate child of the node. Once we reach a leaf node and don’t get ‘k’ in the leaf node, then we will return NULL.

Implementation of Red-Black Tree in C language: -

#include <stdio.h>
 #include <stdlib.h>
 enum nodeColor {
   RED,
   BLACK
 };
 struct Node {
   int value, color;
   struct Node *ptr[2];
 };
 struct Node *root = NULL;
 // Create a red-black tree
 struct Node *create_Node(int value) {
   struct Node *temp;
   temp = (struct Node *)malloc(sizeof(struct Node));
   temp -> value = value;
   temp -> color = RED;
   temp -> ptr[0] = temp -> ptr[1] = NULL;
   return temp;
 }
 // Insert an node
 void insert_value(int value) {
   struct Node *st[98], *ptr, *temp, *Ptr1, *Ptr2;
   int arr[98], ht = 0, index;
   ptr = root;
   if (!root) {
     root = create_Node(value);
     return;
   }
   st[ht] = root;
   arr[ht++] = 0;
   while (ptr != NULL) {
     if (ptr -> value == value) {
       printf("Duplicates Not Allowed!!\n");
       return;
     }
     index = (value - ptr -> value) > 0 ? 1 : 0;
     st[ht] = ptr;
     ptr = ptr -> ptr[index];
     arr[ht++] = index;
   }
   st[ht - 1]->ptr[index] = temp = create_Node(value);
   while ((ht >= 3) && (st[ht - 1]->color == RED)) {
     if (arr[ht - 2] == 0) {
       Ptr2 = st[ht - 2]->ptr[1];
       if (Ptr2 != NULL && Ptr2 -> color == RED) {
         st[ht - 2]->color = RED;
         st[ht - 1]->color = Ptr2 -> color = BLACK;
         ht = ht - 2;
       } else {
         if (arr[ht - 1] == 0) {
           Ptr2 = st[ht - 1];
         } else {
           Ptr1 = st[ht - 1];
           Ptr2 = Ptr1 -> ptr[1];
           Ptr1 -> ptr[1] = Ptr2 -> ptr[0];
           Ptr2 -> ptr[0] = Ptr1;
           st[ht - 2]->ptr[0] = Ptr2;
         }
         Ptr1 = st[ht - 2];
         Ptr1 -> color = RED;
         Ptr2 -> color = BLACK;
         Ptr1 -> ptr[0] = Ptr2 -> ptr[1];
         Ptr2 -> ptr[1] = Ptr1;
         if (Ptr1 == root) {
           root = Ptr2;
         }
      else {
           st[ht - 3]->ptr[arr[ht - 3]] = Ptr2;
         }
         break;
       }
     }
    else
    {
       Ptr2 = st[ht - 2]->ptr[0];
       if ((Ptr2 != NULL) && (Ptr2 -> color == RED)) {
         st[ht - 2]->color = RED;
         st[ht - 1]->color = Ptr2 -> color = BLACK;
         ht = ht - 2;
       }
     else
    {
         if (arr[ht - 1] == 1)
       {
           Ptr2 = st[ht - 1];
         }
       else
      {
           Ptr1 = st[ht - 1];
           Ptr2 = Ptr1 -> ptr[0];
           Ptr1 -> ptr[0] = Ptr2 -> ptr[1];
           Ptr2 -> ptr[1] = Ptr1;
           st[ht - 2]->ptr[1] = Ptr2;
         }
         Ptr1 = st[ht - 2];
         Ptr2 -> color = BLACK;
         Ptr1 -> color = RED;
         Ptr1 -> ptr[1] = Ptr2 -> ptr[0];
         Ptr2 -> ptr[0] = Ptr1;
         if (Ptr1 == root) {
           root = Ptr2;
         } else {
           st[ht - 3]->ptr[arr[ht - 3]] = Ptr2;
         }
         break;
       }
     }
   }
   root -> color = BLACK;
 }
 // Delete a node
 void del_Data(int value) {
   struct Node *st[98], *ptr, *Ptr1, *Ptr2;
   struct Node *pPtr, *qPtr, *rPtr;
   int arr[98], ht = 0, diff, i;
   enum nodeColor color;
   if (!root) {
     printf("Tree not available\n");
     return;
   }
   ptr = root;
   while (ptr != NULL) {
     if ((value - ptr -> value) == 0)
       break;
     diff = (value - ptr -> value) > 0 ? 1 : 0;
     st[ht] = ptr;
     arr[ht++] = diff;
     ptr = ptr -> ptr[diff];
   }
   if (ptr -> ptr[1] == NULL) {
     if ((ptr == root) && (ptr -> ptr[0] == NULL)) {
       free(ptr);
       root = NULL;
     }
    else if (ptr == root)
    {
       root = ptr -> ptr[0];
       free(ptr);
     } else {
       st[ht - 1]->ptr[arr[ht - 1]] = ptr -> ptr[0];
     }
   }
    else
    {
     Ptr1 = ptr -> ptr[1];
     if (Ptr1 -> ptr[0] == NULL)
    {
       Ptr1 -> ptr[0] = ptr -> ptr[0];
       color = Ptr1 -> color;
       Ptr1 -> color = ptr -> color;
       ptr -> color = color;
       if (ptr == root) {
         root = Ptr1;
       } else {
         st[ht - 1]->ptr[arr[ht - 1]] = Ptr1;
       }
       arr[ht] = 1;
       st[ht++] = Ptr1;
     }
    else
    {
       i = ht++;
       while (1) {
         arr[ht] = 0;
         st[ht++] = Ptr1;
         Ptr2 = Ptr1 -> ptr[0];
         if (!Ptr2 -> ptr[0])
           break;
         Ptr1 = Ptr2;
       }
       arr[i] = 1;
       st[i] = Ptr2;
       if (i > 0)
         st[i - 1]->ptr[arr[i - 1]] = Ptr2;
       Ptr2 -> ptr[0] = ptr -> ptr[0];
       Ptr1 -> ptr[0] = Ptr2 -> ptr[1];
       Ptr2 -> ptr[1] = ptr -> ptr[1];
       if (ptr == root)
    {
         root = Ptr2;
       }
       color = Ptr2 -> color;
       Ptr2 -> color = ptr -> color;
       ptr -> color = color;
     }
   }
   if (ht < 1)
     return;
   if (ptr -> color == BLACK)
   {
     while (1)
   {
       pPtr = st[ht - 1]->ptr[arr[ht - 1]];
       if (pPtr && pPtr -> color == RED) {
         pPtr -> color = BLACK;
         break;
       }
       if (ht < 2)
         break;
       if (arr[ht - 2] == 0)
    {
         rPtr = st[ht - 1]->ptr[1];
         if (!rPtr)
           break;
         if (rPtr -> color == RED)
      {
           st[ht - 1]->color = RED;
           rPtr -> color = BLACK;
           st[ht - 1]->ptr[1] = rPtr -> ptr[0];
           rPtr -> ptr[0] = st[ht - 1];
           if (st[ht - 1] == root)
         {
             root = rPtr;
           }
         else {
             st[ht - 2]->ptr[arr[ht - 2]] = rPtr;
           }
           arr[ht] = 0;
           st[ht] = st[ht - 1];
           st[ht - 1] = rPtr;
           ht++;
           rPtr = st[ht - 1]->ptr[1];
         }
         if ((!rPtr -> ptr[0] || rPtr -> ptr[0]->color == BLACK) && (!rPtr -> ptr[1] || rPtr -> ptr[1]->color == BLACK))
       {
           rPtr -> color = RED;
         }
       else
      {
           if (!rPtr -> ptr[1] || rPtr -> ptr[1]->color == BLACK)
            {
             qPtr = rPtr -> ptr[0];
             rPtr -> color = RED;
             qPtr -> color = BLACK;
             rPtr -> ptr[0] = qPtr -> ptr[1];
             qPtr -> ptr[1] = rPtr;
             rPtr = st[ht - 1]->ptr[1] = qPtr;
           }
           rPtr -> color = st[ht - 1]->color;
           st[ht - 1]->color = BLACK;
           rPtr -> ptr[1]->color = BLACK;
           st[ht - 1]->ptr[1] = rPtr -> ptr[0];
           rPtr -> ptr[0] = st[ht - 1];
           if (st[ht - 1] == root) {
             root = rPtr;
           } else {
             st[ht - 2]->ptr[arr[ht - 2]] = rPtr;
           }
           break;
         }
       }
    else
    {
         rPtr = st[ht - 1]->ptr[0];
         if (!rPtr)
           break;
         if (rPtr -> color == RED)
        {
           st[ht - 1]->color = RED;
           rPtr -> color = BLACK;
           st[ht - 1]->ptr[0] = rPtr -> ptr[1];
           rPtr -> ptr[1] = st[ht - 1];
           if (st[ht - 1] == root)
         {
             root = rPtr;
           }
          else
          {
             st[ht - 2]->ptr[arr[ht - 2]] = rPtr;
           }
           arr[ht] = 1;
           st[ht] = st[ht - 1];
           st[ht - 1] = rPtr;
           ht++;
           rPtr = st[ht - 1]->ptr[0];
         }
         if ((!rPtr -> ptr[0] || rPtr -> ptr[0]->color == BLACK) && (!rPtr -> ptr[1] || rPtr -> ptr[1]->color == BLACK))
      {
           rPtr -> color = RED;
         } else {
           if (!rPtr -> ptr[0] || rPtr -> ptr[0]->color == BLACK) {
             qPtr = rPtr -> ptr[1];
             rPtr -> color = RED;
             qPtr -> color = BLACK;
             rPtr -> ptr[1] = qPtr -> ptr[0];
             qPtr -> ptr[0] = rPtr;
             rPtr = st[ht - 1]->ptr[0] = qPtr;
           }
           rPtr -> color = st[ht - 1] -> color;
           st[ht - 1]->color = BLACK;
           rPtr -> ptr[0]->color = BLACK;
           st[ht - 1]->ptr[0] = rPtr -> ptr[1];
           rPtr -> ptr[1] = st[ht - 1];
           if (st[ht - 1] == root) {
             root = rPtr;
           } else {
             st[ht - 2]->ptr[arr[ht - 2]] = rPtr;
           }
           break;
         }
       }
       ht--;
     }
   }
 }
 // Print the inorder traversal of the tree
 void inorder_Traversal(struct Node *node) {
   if (node) {
     inorder_Traversal(node -> ptr[0]);
     printf("%d  ", node -> value);
     inorder_Traversal(node -> ptr[1]);
   }
   return;
 }
 // Driver code
 int main() {
   int choice, value;
   while (1) {
     printf("1. Insertion\t2. Deletion\n");
     printf("3. Traverse\t4. Exit");
     printf("\nEnter your choice:");
     scanf("%d", &choice);
     switch (choice) {
       case 1:
         printf("Enter the element  which you want to insert:");
         scanf("%d", &value);
         insert_value(value);
         break;
       case 2:
         printf("Enter the element which you want to delete:");
         scanf("%d", &value);
         del_Data(value);
         break;
       case 3:
         inorder_Traversal(root);
         printf("\n");
         break;
       case 4:
         exit(0);
       default:
         printf("Invalid Input \n");
         break;
     }
     printf("\n");
   }
   return 0;
 } 

Output: -

Complexity of Red-Black Trees: -

The time complexity of red-black in all operations (e.g. insertion, deletion, searching) is O(log n).

Applications of Red-Black Trees: -

• Red-black trees is used to implement finite maps.
  • It is used to implement package in java like java.util.TreeMap and java.util.TreeSet
  • Used in C++ to implement its libraries like map, multimap
  • Used in the kernel of linux.