The fixAfterInsertion Method

In this lab, we will focus on the implementation of the fixAfterInsertion method. Later on, we will develop a TreeMap which upon one insertion will require all three cases.

Recall that the TreeMap's put method does not call the fixAfterInsertion method when an insertion is made at the root. The basic strategy of the TreeMap's put method is:

  1.	Let t be (a reference to) the parent Entry whose left or right child will hold the given element.

  2.	Create a new Entry pointed to by t.left or t.right, depending on whether the given element's key 
         is less than or greater than t.key.

  3.	Set that new Entry's key and value fields to the given element's key and value fields, respectively.  
         Also, set the new Entry's parent field to t, and the color field to RED.

  4.	Re-color and re-structure the TreeMap, if necessary.

  5.	Set the root's color (back) to BLACK.

The only step that requires some thought is Step 4. This step is carried out with three possible steps. These steps are contained within the fixAfterInsertion method. Normally, it would be easier to simply show you the code first, then discuss it. However, the fixAfterInsertion method's code is not very easy to decipher so we will discuss each step first, then look at the code.

In the discussion to follow, there will be mention of x and y. x refers to the newly inserted element. And y refers to the (right) sibling of x's parent. That is, y = x.parent.parent.right. (Later, we'll see that y will sometimes be a left sibling of x's parent.) Also, recall why the newly inserted element is always automatically colored RED (if it is not the root). This is due to the fact that even if the Red Rule is broken, the Path Rule will not be.

It is also worth noting that within the fixAfterInsertion method, accessor methods are used such as: colorOf, parentOf, leftOf and rightOf. Each of these accessor methods checks to see if the Entry p provided is null, and then returns a value accordingly. The reason we use accessor methods as opposed to directly accessing the field is in the case of the calling object being null. For example, colorOf (y) returns BLACK if y is null; y.color would throw a NullPointerException if y is null. An example is colorOf():

/**
 *BLACK has been returned if p is null. Otherwise, p.color has been returned.
 *
 *@param p an Entry whose color will be returned.
 *
 *@return a boolean representing the Entry's color.
 **/
private static boolean colorOf (Entry p) {

	return (p == null ? BLACK : p.color);
}

And now the three cases of Insertion. Note: One last thing, this first example is assuming that the parent of x is a left child.

Case 1. colorOf (y) = RED

Suppose 40 had just been inserted:

Here is the action to take in this case:
      
      setColor(parentOf(x), BLACK);
      setColor(y, BLACK);
      setColor(parentOf(parentOf(x)), RED);
      x = parentOf(parentOf(x));

The resulting partial tree is: 

Case 2. colorOf (y) = BLACK, and x is a right child:

Suppose 40 had just been inserted:

(Make sure you understand why 50's color must be BLACK.)  

   The action taken is:

      x = parentOf (x);
      rotateLeft (x);
                        
Here is the tree after this left rotation:

We are not done yet because x and its parent are both RED. And this leads us to Case 3.

Case 3. colorOf (y) = BLACK, and x is a left child:

Suppose 30 had just been inserted:

Here is the action taken in this case:

    setColor(parentOf(x), BLACK);
    setColor(parentOf(parentOf(x)), RED);
    if (parentOf(parentOf(x)) != null) 
	rotateRight(parentOf(parentOf(x)));

Here is the partial tree after this rotation: 

Clearly, this is a red-black tree. Notice that after the prescribed action is taken for Case 3, the color of x's parent will always be BLACK, and that will terminate the execution of the while loop. The basic idea is that if Case 1 does not apply, we first check for Case 2 and then, whether or not Case 2 applied, we apply Case 3. Note that Case 3 always applies after Case 2. Here is the overall structure (when x's parent is a left child):

if (y is RED)   // Case 1
{
  …
} 
else 
{
  if (x is a right child)   // Case 2
  {
    …
  }
  // Case 3
  setColor(parentOf(x), BLACK);
…
}

On the next page we will take a look at the actual implementation of the fixAfterInsertion.