26 Red Black Trees -II

T.V. Geetha

 

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of Red Black tree and insertion into them. In this module we will discuss deletion from Red-Black Trees.

 

Learning Objectives

 

The learning objectives of the module are as follows:

 

• To understand the concept of deletion from Red Black Trees

• To discuss the properties of Red Black Trees that are affected by Deletion

• To explain the deletion from Red Black Trees

 

26.1 Deletion from Red-black Trees

 

There are basically two approaches to deletion from Red-black trees. The bottom-up approach is recursive where the BST deletion is carried out going down the tree (winding up the recursion) and the RB(Red-black) properties violated as a result of the deletion is fixed while coming back up the tree (unwinding the recursion). The other approach is the iterative top down approach where the tree is restructured on the way down itself and hence we do not need to go up the tree for fixing the violated RB properties. In this module we will be discussing the bottom-up approach in detail.

 

26.2 Deletion from Binary Search Trees

 

Before we discuss deletion from Red-black, let us recall the deletion of a node from a binary search tree, since Red-black trees are a type of balanced binary search trees. In the case of deletion from binary search trees, there are basically three cases. If the node to be deleted is a leaf, we can just delete it. If the node to be deleted has just one child, we replace it with that child by making the parent of the node to be deleted to point to the one child that exists. If the node to be deleted has two children, we replace the node by its in-order predecessor/successor and then then delete the in-order predecessor/ successor (a recursive step). We note that the deletion of the in-order predecessor/ successor will have either no child or only one child. In other words eventually a BST deletion will be done with the node being a leaf or having just one child.

 

26.3  Bottom-up Deletion

 

As we have already discussed we will be discussing bottom – approach to Red-black tree deletion. Now let us introduce some variables, in order to later explain the deletion from Red-black Tree.

 

1. If deleted node U, is a leaf, think of deletion as replacing U with the NULL pointer, V.

2. If U had one child, V, think of deletion as replacing U with V.

 

What can go wrong?? -Which RB Property may be violated after deletion?

  • If U is Red? – Not a problem – no RB properties are violated
  • If U is Black? if U is not the root, deleting it will change the black-height along some path

 

26.2.1 Concept of Red-black Deletion

 

Now let us discuss deletion from Red-black trees. In insert operation of Red-black trees, we check color of uncle to decide the appropriate case. In delete operation of Red-black trees, we will need to check the color of sibling to decide the appropriate case. In the case of deletion, the main violated property is, change of black height in sub-trees as deletion of a black node may cause reduced black height in one root to leaf path that is RB property 5 may be violated.

 

In order to understand deletion, we need to understand the notion of double black. When a black node is deleted and replaced by a black child, the child is marked as double black. The main task now becomes the conversion of this node marked as double black to single black.

 

26.2.2 Understanding Deletion with an Example

 

Let us assume that the node that is deleted is U. Now let us see what will be the consequence if the node U that was removed is Black. In other words let us see which of the 5 RB properties will be affected by this deletion.

 

Property 1-Every node is either red or black – this property is not affected by the deletion of a black node.

 

Property 2 – The root is black – this property will be violated if the node that is deleted is the root and the child that replaces it is red. The property that every leaf (NULL) node is black is not affected by the deletion of a black node.

 

Property 3 &4 – If a node is red, then both its children are black – this property will be violated as the deletion of the black node could sometimes create two red nodes in a row

 

Property 5 – For each node, all paths from the node to descendant leaves contain the same number of black nodes –this property may be violated as the deletion of the black node could change the black heights of some nodes.

 

26.2.3 Deletion – Case 1 and Case 2

 

Let U be the node to be deleted and V be the child that replaces U. V is NULL when U is a leaf and color of NULL is considered as Black.

 

Case 1 : If either U or V is red that is U is black and V is red or U is red and V is black

Case 2 : If Both U and V are Black.

 

26.2.3.1 Case 1: If either U or V is red

 

Figure 26.1 shows the case where U the node to be deleted is black and V is red. 30 the parent of U is black. In this case U, the black node to be deleted is 20 and V, the red node that replaces it is 10. We mark the replaced child 10 as black. There will be no change in black height. U and V cannot be red as U is parent of V and two consecutive reds are not allowed in the original red-black tree.

 

 

26.2.3.2 Case 2: If both U and V are Black.

 

In this case we color V as double black. Now our task reduces to converting this double black to single black. If U is leaf, then V is NULL and color of NULL is considered as black. So the deletion of a black leaf also causes a double black. This case is shown in Figure 26.2 where U, 10 is the black node to be deleted and the V node that replaces it is NULL. Now this NULL node V becomes a Double black Node.

 

 

 

26.3 Steps of the Deletion Procedure

 

For deletion we first carry out regular BST deletion. Let U be the node to be removed. The removed node can have at most one child. If deleted node, U is a leaf, deletion is the replacement of U with the NULL pointer, V. If U had one child, V, deletion is the replacement U with V. If the removed node U was red, no property could get violated, so we just remove it. Otherwise that is U is black remove it and call the tree-fix algorithm on U’s child V (the node which replaced the position of U). If U is not the root, deleting it will change the black-height along some path.

 

26.4 Fixing the problem

 

Let us assume that V is the node that has the “extra” unit of blackness, due to the deletion of a node U. This extra blackness must be absorbed into the tree (by a red node), or propagated up to the root and out of the tree.

 

Let us assume that the node that we just deleted was U. Let the node that replaces it be V and is the node with an extra unit of blackness or the double black node. Let the parent of V be P and it’s sibling be S. In the explanation we give we use the notation given in Figure 26.3.

 

 

 

 

26.4.1 Deletion and Violation of Red-Black Properties

 

The extra black unit is pushed up the tree until a red node is reached, when it is made black or the root node is reached or it can be removed by rotating and recoloring. If the deleted node U is red, no property is violated. If U is a leaf, no property is violated. Otherwise U is black and has a child V, and property 2, 3, and 4 (refer to properties of Red-black trees) are violated. For fixing property 2, set the color of root to black after deletion. To fix property 3 and 4, if U’s Child V (the replacing node) is red, set it to black and we are finished. If V is black, fixing property 3 and 4 requires the adding of an extra unit of black to V, making it a double black node. However now property 1 is violated.

 

In order to fix property 1, we will consider if V (the doubly black node) is a left child or right child, of its parent, the color of V’s sibling S is red or black and the colors of S’s children. We consider x is a left child first, where we have four cases. The other four cases when V is a right child of its parent are symmetric.

 

26.4.2 Cases 1-4

 

Remember V is the node that has is of concern here and is the node that replaces the node U that was deleted. Considering the double black node V as left child of its parent we have 4 cases as discussed below:

  • Case 1 – Sibling S of V is Red
  • Case 2-4 -Sibling S of V is Black
  • Case 2 – S is Black & S has two Black Children
  • Case 3 – S is Black & Right Child of S is Red & Left Child is either
  • Case 4 – S is Black & Right Child of S is Black & Left Child is Red

 

Now we will see how we handle each of the cases when we use the bottom-up approach. In delete operation of Red-black trees, checking the color of sibling is the operation which helps to decide the appropriate case.

 

26.4.2.1 Bottom-Up Deletion -Case 1

 

This is the case when Sibling S of V is Red (as shown in Figure 26.4).

 

•  Rotate S around P (parent of V )

•  Recolor S & P

 

This case is not a terminal case, as after this case, one of the other cases will apply. Three cases (2-4) apply when the sibling S is black

 

 

The operations for case 1 when V’s sibling S is Red is shown in Figure 26.5. Here we first perform a left rotate of S with P as pivot. Now S becomes the parent of P and P becomes Left Child of S. Now we recolor where S is colored black and P red.

 

26.4.2.2 Bottom-Up Deletion -Case 2-4

 

This concerns three cases as discussed in section 26.4.2 – Cases 2-4 where V has two Black Children – Sibling S of V is Black (as shown in Figure 26.6). The three cases are as follows:

 

Case 2. S has 2 Black Children

Case 3. S’s Right child is Red (Left child can be either color)

Case 4. S’s Right child is Black and S’s Left child is Red

 

Now we will consider each of the three cases 2-4, one by one.

 

26.4.2.2.1 Bottom-Up Deletion -Case 2

 

This is the case where V’s sibling, S, is Black and it has two Black children

 

(Figure26.7). The steps for fixing are as follows:

 

–  Recolor S to be Red

–  P absorbs V’s extra blackness

• If P is Red, we’re done (it absorbed the blackness)

• If P is Black, it now has extra blackness and problem has been propagated up the tree

 

The operations for case 2 when V’s sibling S is black and has two black children is shown in Figure 26.8. Here we first recolor S as red and make P absorb the blackness. If P was red, then the operation is complete. However if P is black, we propagate black up the tree.

 

 

Figure 26.9 shows an example of the above case. Here parent p (rooted at 20) is a sub-tree, u (10) is the node to be deleted and v the node that replaces u is a black NULL node. As you can see s (30), the sibling of the NULL node is black and has two black NULL children. Now node v (NULL) becomes a double black node. Now we first recolor s to be red. p (20) will absorb the blackness. Since p is already a black node, we need to propagate the blackness up the tree.

 

This is the case where V’s sibling, S (Right Child of Parent P of V) is Black and S’s Right child is RED (Left child can be either color) (Figure 26.10). The steps for fixing are as follows:

 

–  Rotate S around P

–  Swap colors of S and P, and color S’s right child Black

–  This is the terminal case – we’re done

 

 

 

 

This fixing is explained in Figure 26.11. We Left Rotate S (sibling of V that replaces the deleted node U), around P (parent of V). Then we swap the colors of S and P where P (red becomes black), S (black becomes red) and the red right child of S becomes black. We then continue down the tree.

 

Figure 26.12 shows an example of the above case. Here parent p (rooted at 30) is a sub-tree, u (20) is the node that is deleted and v the node that replaces u which was originally a black NULL node and now becomes a double black node. As you can see s (40), the sibling of the v node is black and has a red right child r (50). Remember that the left child of s can be either red (in this example 35 is red) or black. We first carry out a Left Rotate of s about p. and swap the colors of s and p. Since both are black in our example there in no effect. The original red right child of s (r-50) is now recolored black.

 

26.4.2.2.3 Bottom-Up Deletion – Case 4

 

This is the case where S the Right Sibling of V is Black, S’s Right child is Black and S’s Left child is Red (Figure 26.13). The steps for fixing are as follows:

  • Rotate S’s left child around S
  • Swap color of S and S’s left child
  • Now we are left with the conditions of case 3

 

 

This fixing is explained in Figure 26.14. We Right Rotate, the red left child LC of S with S as the pivot. Then we again Left rotate LC around P (the orginal parent of S). Then we swap the colors of S and LC the original left child of S. If the new V is Red, continue down again. However if the new V is Black (S is Red, P is Black), we Rotate S around P and recolor P and S. Now go back to the main case, that is we go to step 2, where again the cases 1-5 are checked.

 

 

 

Figure 26.15 shows an example of the above case. Here parent p (rooted at 30, u

 

(20)  is the node that is deleted and v the node that replaces u which was originally a black NULL node and now becomes a double black node. As you can see s (40), the sibling of the v node is black and has a red left child r (35). We first carry out a Left Rotate of lc (left child LC of s) about s. Then we again Right Rotate lc about p (the original parent of s). Then we swap the color of s and s’s original left child lc.

 

 

26.4.3 Algorithm for Fixing after Deletion

 

The algorithm for the fixing of the red-black after the deletion of a node is given in Figure 26.16. Here we assume that the deletion of a node has already been carried out and the replacement of the deleted node by another node sometimes results in violation of the red-black properties which needs to be fixed.

 

 

Summary

  • Explained the concept of deletion from Red Black Trees
  • Discussed the properties of Red Black Trees that are affected by Deletion
  • Explained the deletion operation of Red Black Trees