Chapter 5
These are the solutions to the .
-
The tree will look like this:
This is because we always switch the orientation of the parent-child relationship. Since previously, the A was the B’s left child, the B will now become the A’s right child.
-
The red-black tree will look like this after the rotation:
When we rotate the 80 and 100, the orientation flips, so the 100 becomes the right child of the 80. However, this creates a problem of where to place the 85. Given that the 85 was the 80’s right child, where does the 85 go now that the 100 became the 80’s right child?
The solution is to make the 85 a crossover node, which causes the 85 to become the 100’s left child.
-
The red-black tree will look like this after the insertion:
That is, we insert a red 30 as the 15’s right child. The 30 is red since all new nodes start out red. Now, given that this doesn’t violate the Red Enemies Rule, there’s no fixing up to do, and we can leave the tree as is.
-
Initially, we insert a 20 as the 30’s left child, and color the 20 red as we do with all new nodes:
However, this violates the Red Enemies Rule because the 20 and 30, which are parent and child, are both red. This means we have some fixing up to do!
The first thing we do as part of the fixing phase is to determine whether this is a Red-Uncle Case or a Missing-Or-Black-Uncle Case. This case happens to be a Missing-Uncle Case since the 20 doesn’t have an uncle. (That is, the 20’s grandparent, 15, has no children other than the 20’s parent, 30.)
Once we’ve determined that we’re dealing with a Missing-Uncle Case, we next need to check whether the 20 and 30 have the same orientation or not. Since the 20 is the 30’s left child, and the 30 is its parent’s right child, this means that they have different orientations. And this means that we need to execute the following steps:
First, we rotate the current node (20) and its parent (30) as shown in the .
The 30 now becomes designated as the current node.
Second, we flip the current node’s parent (20) black and the current node’s grandparent (15) red:
The third and final step is to rotate the current node’s parent (20) and grandparent (15):
And we’re done!
