Red Black Tree – Deletion

Deletion of a node from a red black tree is very difficult. During insertion we selected the color of a new node as red to make it easier. We forced a red violation and fixed it. Red violations are easy to fix, and we took full advantage of that to produce a truly elegant recursive algorithm. When you want to delete a node, you don’t have the option of choosing its color. If it’s red, that’s good. Red nodes can be removed without any violations. Because there will be no red violation by removing a red node from a valid tree. Since a red node doesn’t participate in the black height, removing a red node has no effect on the black height. Therefore, removing a red node cannot violate the rules of a red black tree.
If the node is black, that’s a problem. Removing a black node is sure to cause a black violation just like inserting a black node, which is why we avoided that during insertion, and it could very likely cause a red violation too. Now we are going to delete red node, always since deleting a red node can’t violate any of the rules of a red black tree. How can delete a red node, always? first we force a red node into the tree at the top. Then we push down that red node down using colour flips and rotations. Hence we can ensure that a red node will be deleted, always.
There are only four cases for pushing a red node down the tree without a black violation. I am going to explain how to handle each case using examples. In each example we can see a node is deleted from the tree  given below. Before that first look at the deletion function. This delete function will use a sneaky deletion by copying technique that saves the node to be deleted, and just keeps on going through the loop until the inorder predecessor is found. At that point the walk down loop terminates, the data items are copied and the external node is spliced out of the tree.
The delete function look like this:
 struct tnode *p, *g, *p;
void delete(struct tree *tree, int data)
{
       if (tree->root != NULL) {
              struct tnode head = {0};
              struct tnode *f = NULL;
              struct tnode *child1, *child2, *sib, *next;
              int dir = 1;
              q = &head;
              g = p = NULL;
              q->right = tree->root;
              next = q->right;
              while (next != NULL ){
                    int last = dir;
                    g = p, p = q;
                    q = next;
                    dir = q->data < data;
                    if (dir == 1){
                         next = q->right;
                         if (q->data == data) {
                                child1 = q->left;
                                child2 = q->right;
                         }else {
                                child1 = q->right;
                                child2 = q->left;
                         }
                    } else if (dir == 0) {
                         next = q->left;
                         child1 = q->left;
                         child2 = q->right;
                    }
                    if (data == q->data )
                         f = q;
                  /*code for push down the red node down*/
           }
           if (f != NULL)
                  removal(f);
           tree->root = head.right;
           if ( tree->root != NULL )
                  tree->root->color = BLACK;
      }

}

In this function we used a dummy root to avoid special cases, and a few helper variables to point up the tree. The head is the dummy root, f points to target node. The child1 and child2 points to the two childs of current node. The sib points to sibling of the current node and next points to next node to be examined. The q points to the current node ang g and p are the grand parent and parent of the q respectively. Now we initialize q to points to dummy root and right child of dummy root as real root of tree. The variable dir indicates which subtree should be searched for the target node. Suppose the target node is in the right subtree, if it reaches target node dir become 0 and loop keeps on going through the left subtree of target node inorder to find inorder predecessor. On the way down we look and handle all the four cases for pushing red node down. After the deletion of target node root of the tree should be updated and its colour should be black.
The code for handling four cases are given below:
if (!is_red(q) && !is_red(child1)){
       if(is_red(child2)) {
              case2(dir, last);
       }else  if (!is_red(child2)){
               if (last == 0)
                       sib = p->right;
               else if(last == 1)
                       sib = p->left;
               if ( sib != NULL ) {
                       if ( !is_red ( sib->left ) && !is_red ( sib->right ) ) {
                              case1(sib);
                       }else {
                              int dir2 = g->right == p;
                              case3_4(sib, dir2, last);
                              proper_coloring(dir2);
                        }
               }
         }
}


First we check the whether the current node and one of its child is black or not. If both are black then we check the other child is black or not. if  other child is red then it is case2 that is dreaded red sibling case. Then we call the function case2 to handle it. If other child is black then we check the colour of the children of sibling of the current node. If both the sibling’s children are black then it is case1 that is simple reverse colour flip and we call function case1 to handle it. if one of the children of sibling is red then it is case3 or case 4. If right child is red we perform double rotation(case3) and if left child is red then we perform a single rotation(case4). The function case3_4 is called for handling it. Next we look at each cases. Consider the tree given below:

 Case 1:
The first case is a simple reverse color flip. If a node and it’s sibling are black, and all four of their children are black, make the parent black and both children red:
void case1(struct tnode *sib)
{
       p->color = BLACK;
       sib->color = RED;
       q->color = RED;
}


Let’s delete the node 25 from above red black tree. Since node 25 is red and it’s left child 22 and right child 27 is black, that is case1. After handling case1 now the f points to node 25 and  current node, q points to node 22 (inorder predecessor of node 25). Now we replace the data of node pointed by f with data of node pointed by q. After the deletion of node 25 the tree look like this:

case2:
The second case is dreaded red sibling case. If a node is black and it’s sibling is red then we reduce it  with a single rotation.

void case2(int dir, int last)
{
        if (dir == 1) {
                if (last == 1)
                        p = p->right = single_right(q);
                else if(last == 0)
                        p =  p->left = single_right(q);
        }else if (dir == 0){
                if (last == 1)
                        p = p->right = single_left(q);
                else if(last == 0)
                        p =  p->left = single_left(q);
        }
}

Let’s delete the node 17 from above red black tree. It is black and it’s right child is red and left child is black, that is case2. After handling case2  now the f points to node 17 and current node, q points to 15(inorder prececessor of node 17). Now we check the colour of sibling of node 15 since node 15 and both of its children is black(null pointer). The sibling of node 15 is node 22 and it is black. Hence we have to handle this case 1. After handling case1 we replace the data of f by data of current node, q.
After the case2 the tree look like this:

After case1 and remove tree look like this:

case 3 and case4:
If the node and both of its child are black then we look for the colour of it’s sibling’s children. If the right child of sibling is red then we reduce it with double rotation, that is case3. If sibling’s left child is red then single rotation is enough. It is case4.
case3:


case4:

void case3_4(struct tnode *sib, int dir2, int last)
{
       if ( is_red ( sib->right ) ){/*case 3*/
              if (dir2 == 0 && last == 0)
                     g->left = doubble_right ( p);
              else if (dir2 == 0 && last == 1)
                     g->left = doubble_left(p);
              else if(dir2 == 1 && last == 0)
                     g->right = doubble_right(p);
              else if (dir2 == 1 && last == 1)
                     g->right = doubble_left(p);
       } else if ( is_red ( sib->left ) ){/*case 4*
              if (dir2 == 0 && last == 0)
                     g->left = single_left ( p);
              else if (dir2 == 0 && last == 1)
                     g->left = single_right(p);
              else if (dir2 == 1 && last == 0)
                     g->right = single_left(p);
              else if (dir2 == 1 && last == 1);
                     g->right = single_right(p);

       }
}


Now delete the node 1 from the above red black tree. Since node 1 is at left subtree of root, loop traverse through the left subtree. When it reaches node 8, it’s both children are black so we check the colour of it’s sibling children. The sibling of node 8 is node 17 and it’s right child node 25 is red. Hence it is case3. We perform a double rotation. After double rotation we will force the correct colouring for all affected nodes by calling proper_coloring routine.
after double rotation:

after proper colouring:

Now the loop continues. When it reaches the node 1 its one child is black(Null pointer) and another is red so it is case2. After handling case2 we remove the node 1. Now tree look like this:

The removal function look like this:

void removal(struct tnode *f)
{
        int flag1 = p->right == q;
        int flag2 = q->left == NULL;
        f->data = q->data;
        if (flag1 == 0 && flag2 == 0)
                p->left = q->left;
        else if (flag1 == 0 && flag2 == 1)
                p->left = q->right;
        else if (flag1 == 1 && flag2 == 0)
                p->right = q->left;
        else if (flag1 == 1 && flag2 == 1)
                p->right = q->right;
        free ( q );

}