**The fixAfterDeletion Method**

In this lab, we will focus on the implementation of the fixAfterDeletion method. Later on, we will develop a single example of a removal from a TreeMap in which all four cases of the fixAfterDeletion method apply.

Here is the method heading:

private void fixAfterDeletion (Entry<K, V> x)

If x is the root or if x's color is RED, all we need to do is set x's color to BLACK, so we will keep looping until x is the root or x's color is RED, that is:

while (x != root && colorOf (x) == BLACK)

At the start of any iteration of this loop, x may be a left child or a right child. There are four cases to consider if x is a left child. The four symmetric cases if x is a right child are handled by transposing the words "left" and "right" in the x-is-left-child cases. The determining factor turns out to be the current sibling -- referred to as sib -- of x.

Note: Much like the fixAfterInsertion method, the fixAfterDeletion also uses accessor methods as opposed to directly accessing the field.

The Four Cases of Deletion

Case 1: colorOf (sib) = RED

Suppose we want to delete p's entry from the following red-black tree:

After changing p's element to that of its successor, and then making p reference that successor Entry, fixAfterDeletion (p) is called, with x as the formal parameter. The references x and sib are as shown below:

If we now were to unlink x from its parent, the Path Rule would be violated, so we must do something else first. Because sib is RED, Case 1 applies. The action taken in this case is:


setColor (sib, BLACK);
setColor (parentOf (x), RED);
rotateLeft (parentOf (x));
sib = rightOf (parentOf (x));

The tree is now:

If we now were to unlink x from its parent, the Path Rule would still be violated, but we have a new sib, and it is BLACK! So Case 1 devolves into one of the other three cases.

Case 2: colorOf (leftOf (sib)) = BLACK && colorOf (rightOf (sib)) = BLACK

For example, we can apply Case 2 to the tree we had at the end of the Case 1 example. At the end of that example we had:

Because both of sib's children are null and the colorOf method returns BLACK for a null argument, Case 2 applies. The action taken for Case 2 is simply:


setColor (sib, RED);
x = parentOf (x);

When we apply that rule to this red-black tree (actually, a TreeMap), we get:

(Incidentally, p is still a reference to the leaf entry with 65 as its value, so this entry can be unlinked from the tree after the return is made from fixAfterDeletion.)

Now x is RED, so we fall through the loop. We then set x's color to BLACK, and return to deleteEntry, where p's entry is unlinked from its parent and we end up with the following TreeMap:

Here is the overall strategy of the while loop:


if (colorOf (sib) == RED)
// apply Case 1 action
if (colorOf (leftOf (sib)) == BLACK && colorOf (rightof (sib)) == BLACK)
// apply Case 2 action
else
// apply Case 3 and 4 actions

Fortunately, the while statement terminates after a single iteration if either Case 3 or Case 4 applies. And the while statement terminates after a single iteration if Case 1 applies unless, after Case 1 has been handled, Case 2 applies. Even then, as we have just seen, no additional iterations may be needed. Case 2 is the only one that allows for additional loop iterations, and when that happens, x is farther up the tree, so for the while statement, worstTime (n) is logarithmic in n, the size of the tree.

Case 3: colorOf (rightOf (sib)) = BLACK

From the outline given earlier, it is clear that to get to this case, it is impossible for both of sib's children to be BLACK. So sib's left child must be RED. For example, suppose at the beginning of the while loop we have the following:

Case 2 applies, so we change 75's color to RED and set x = parentOf (x). That completes the first iteration. At the start of the second iteration, sib is 90, and the tree is:

Now Case 3 applies. The action in this case is:


setColor (leftOf (sib), BLACK);
setColor (sib, RED);
rotateRight (sib);
sib = rightOf (parentOf (x));

After doing this, we have:

At first glance, this does not seem to be an improvement. But notice that sib's right child is now RED, and this leads us to Case 4.

Case 4: sib's right child is RED

By the Red Rule, if this case applies, sib must be BLACK. For example, suppose at the start of the while loop, the tree is as follows:

The action taken in this case is:


 setColor (sib, colorOf (parentOf (x)));
            setColor (parentOf (x, BLACK));
            setColor (rightOf (sib), BLACK);
            leftRotate (parentOf (x));
            x = root;  // to break out of the while statement

When we re-color and rotate, we get the following:

The loop is exited, and p's Entry (the leaf with 65) is unlinked from the tree, which is then a red-black tree.

For another example in which Case 4 applies, let's start with the tree at the end of Case 3:

Because sib's right child is RED, Case 4 applies. After re-coloring and left-rotating at x's parent, we get:

The loop is now exited, and we return to deleteEntry, where p's element, the leaf 65, is unlinked from the tree. Both the Red Rule and the Path Rule are now satisfied, so we are done.

If during some iteration, either Case 3 or Case 4 applies, x will be set to root, and that will be the last iteration of the loop.

Whenever Case 3 is applied, sib's right child will become RED, so Case 4 will always apply after Case 3. Rather than repeat the code for Case 4, we place that code after the Case 3 code. The overall structure (when x is a left child) is as follows:


if (sib's color is RED)    // Case 1
{
  …
} 
if (both of sib's children are BLACK)   // Case 2
{
  …
}
else {
  if( sib's right child is BLACK )     // Case 3
  {
    …
  }
  // Case 4
    …
}