Red-Black Tree Insertion

Inserting a new node into a red-black tree is considerably more complicated than inserting a node into a classic BST. We can’t just plop the node into its correct spot; we also need to ensure that the tree follows the Red-Black Rules.

The first thing to know about red-black tree insertion is that the node we insert always starts out colored red. The reason for this will become apparent soon.

The second thing to know is that we insert a new node into a red-black tree in up to two phases. The first phase is virtually identical to a classic BST insertion. That is, we start at the root and move down through the tree searching for the correct spot to insert the new node based on its value. This follows the BST rule previously mentioned: namely, that a node’s left descendants must have smaller values and a node’s right descendants must all have greater values. I covered this process back in Volume 1, Chapter 15, but we’ll see code for this again shortly.

Once we find the correct spot, we attach the node to the tree by making it a child of another node. Once this first phase is complete, the inserted node will be a leaf node.

Now, if the newly inserted red node ends up having a black parent, we’re done, and there’s no need to move on to a second phase. Let’s look at a quick example of this. Say that we have a red-black tree like the following:

If we want to insert a node with the value of 60, we start by comparing 60 to the root value. In this case, the root is 50.

Because 60 is greater than 50, we look to the root’s right child, which in this case is 75. Because our new node, 60, is less than 75, we look to the 75’s left child. However, the 75 has no left child. As such, we insert our new node as the 75’s left child:

As with all newly inserted nodes, we’ve colored the 60 node red. Currently, there are no violations of the Red-Black Rules, so our insertion is complete. If, however, our new red node ends up with a parent that is also red, we will have violated the Red Enemies Rule, so we need to move on to a second phase, in which we “fix” the tree. This “fixing phase” modifies the tree in all sorts of ways, including changing nodes’ colors and performing rotations.

Before we move on to the fixing phase, though, let’s implement the first phase of insertion.

Code Implementation: Red-Black Tree Insertion (First Phase)

The following is our insert method:

​	​def​ ​insert​(self, value):
​	new_node = rbt_node.Node(value, ​"red"​)
​
​	​if​ ​not​ self.root:
​	self.root = new_node
​	​return​
​
​	current_node = self.root
​
​	​while​ current_node:
​
​	​if​ value < current_node.value:
​	​if​ ​not​ current_node.left_child:
​	current_node.left_child = new_node
​	new_node.parent = current_node
​
​	current_node = current_node.left_child
​
​	​elif​ value > current_node.value:
​	​if​ ​not​ current_node.right_child:
​	current_node.right_child = new_node
​	new_node.parent = current_node
​
​	current_node = current_node.right_child
​
​	​else​: ​# value is already inside tree​
​	​break​
​
​	self.fix_insert(new_node)

We call the method and pass a value into it. The first thing the method does is create a red node to encapsulate this value:

​	new_node = rbt_node.Node(value, ​"red"​)

All the remaining code, save for the final line, is a classic BST insertion. Now, in Volume 1, we implemented this using recursion, which led to some concise and elegant code. Here, however, we’ve implemented BST insertion using iteration rather than recursion.

While we could have used recursion here as well, much of the code that is to come is more easily understood using iteration. To keep a consistent code style throughout this chapter, I’ve used iteration for this method as well, even though the code ends up being a little longer.

Let’s briefly walk through the method’s remaining code.

After creating the new red node, we declare it to be the tree’s root if the tree doesn’t yet have any nodes other than this one. We then set a variable current_node to point at the root. Next, with a while loop, we compare our new node’s value to the value of the current_node and keep moving down through the tree via left or right children until we hit the spot where the new node should live. Once we’ve identified that spot, we insert the new node by making it a child of some existing leaf node.

In this implementation, we (arbitrarily) do not allow for duplicate values in our tree and break from the loop if we find that the value is already present in the tree.

This brings us to the method’s final line of code:

​	self.fix_insert(new_node)

This method, to be implemented soon, will check whether our new node violates the Red Enemies Rule, and if it does, modify the tree so that the tree becomes valid again. The fix_insert method is the core of how red-black trees work, and performs the fascinating magic of keeping the tree balanced. Let’s see how it works.

The Main Balancing Act: Fixing the Red-Black Tree

The fixing phase has lots of details, many of which will at first seem arbitrary and needlessly complex. To make things easier to comprehend, I begin with a high-level overview of how the fixing phase works. I’ll first focus on what the steps are and later return to explain why the steps do what they do.

First, remember that a node can have a left child and a right child and that a node is considered a parent to its children. Keeping with the familial jargon, a node can have a grandparent, which is the node’s parent’s parent. In the following image, the 100 node’s parent is the 75, and its grandparent is the 50:

Nodes are considered siblings if they share the same parent. In the following image, the 25 and 75 are siblings since they are both children of the 50:

Finally, a node can also have an uncle or, if you prefer, an aunt. These terms can be used synonymously, but we’ll use the term “uncle” only because most of the literature does. A node’s uncle is its parent’s sibling. For example, in the image that follows, the 25 is the 100’s uncle since the 25 is a sibling to the 75, which in turn is the 100’s parent:

With these definitions in place, let’s dig into the entire insertion algorithm, including its fixing phase. We’ll first describe this piece by piece, and then afterwards make a clean list of all the algorithm’s steps.

Remember, each time we insert a new node, we color it red. The color may eventually change, but when we first insert it, it’s red. Then, we use the rules of a BST to move down the tree and determine where this shiny new red node should go. Once we find the right spot, we plug it in.

If the new node’s parent is black, we’re done. This is because we know that we could not have possibly broken any of the Red-Black Rules by inserting this node. We couldn’t have broken the Black Height Rule because inserting a red node will not change the number of black nodes in a path. And we couldn’t have broken the Red Enemies Rule because our new red node has a black parent; we didn’t create a situation where a parent and child are both red.

If, however, our new node’s parent is red, we’ve broken the Red Enemies Rule, and the fun begins. It’s time for the fixing phase!

We set a variable called current_node to point to our newly inserted red node. Eventually, current_node will point to other nodes further up the tree, but at first, it points to our new node.

We then begin a loop which I’ll refer to as the “fixing phase loop.” The fixing phase loop lasts as long as the current_node and its parent are both red.

Within this loop, we look for one of three possible cases:

1. The current_node’s parent is the tree’s root. We’ll call this the “Root-Parent Case.”
2. The current_node’s uncle is red. We’ll dub this the “Red-Uncle Case.”
3. The current_node doesn’t have an uncle or its uncle is black. Even though these are technically two different scenarios, we’ll consider them a single case since we perform the same actions for both. I’ll call this the “Missing-Or-Black-Uncle Case.”

Depending on what our case is, we’ll perform a different series of actions that will help fix the tree. Some of these actions may seem arbitrary, but I’ll try to uncover at least some of the rationale for each one.

The Root-Parent Case

Imagine that we only have a single node in our tree. By definition, this node is the tree’s root. It will also be red since at the time that we inserted it, we colored it red, as we do with all insertions:

Isn’t it cute? Okay, let’s now insert a 2 into this tree:

Wow, we’re only two nodes in, and we’ve already managed to break the Red Enemies Rule. This triggers our loop, which analyzes the current_node to see which of the three cases it falls under.

This case is the Root-Parent Case since the current_node, which is the 2, has the root as its parent. In truth, it should also qualify as the Missing-Uncle Case since the current_node has no uncle, but the fact that its parent is the root takes precedence.

Luckily, there’s only one action we need to take in the Root-Parent Case. And that is, we color the root black:

This single action solves the red enemies problem since we no longer have a parent and child who are both red. At the same time, the fact that we colored a node black didn’t violate the Black Height Rule either. This is because when we color the root black, all the paths in the tree increase their black height by one. Even in large trees, coloring the root black can’t possibly add a black node to only one path and not another. After all, the root belongs to all paths!

That was simple enough. Let’s move on to the Red-Uncle Case.

The Red-Uncle Case

Take a look at the following tree:

If we insert a 6, our tree will initially look like this:

Our newly inserted node and its parent, the 8, are both red and are therefore in violation of the Red Enemies Rule. This triggers the fixing phase loop.

This scenario represents a Red-Uncle Case since the current_node’s uncle, the 2, is red. Here is the set of actions we take in a Red-Uncle Case:

1. We color the current_node’s parent black.
2. We color the current_node’s uncle black.
3. We color the current_node’s grandparent red.
4. We set the current_node variable to point to the current_node’s grandparent, and go back to the beginning of the fixing phase loop. (The loop will proceed again if the new current_node and its parent form a new red enemies violation.)

An image of what our tree looks like after the first three steps is .

We can see that the Red Enemies Rule has been resolved, for there are no longer any red nodes touching each other. At the same time, we also didn’t mess up the Black Height Rule; each path has the same black height of 1.

This set of color flips seems random and arbitrary at first. Yes, flipping the parent and uncle black while flipping the grandparent red seems to do the job, but why?

To make more sense of this, I like to think about the grandparent as bequeathing its black color to its two children as an inheritance. That is, the grandparent turns red and gives up its black color to its children.

Now, this immediately resolves the red enemies violation because one of these children that inherited black color is the parent of our current_node. In our example, this was the 8. This 8 was a red enemy, but because it turned black, it can happily be a parent to its red child (the current_node 6).

At the same time, when the grandparent bequeaths its black color to its two children, it automatically maintains the Black Height Rule. In our example, the grandparent, the 5, has two paths descending from it. Because it gives up its black color to both paths, these paths will both increase their black height equally.

Therefore, this set of color flips solves the Red Enemies Rule while also maintaining the Black Height Rule.

Repeating the Fixing Phase Loop

Now, after we perform all the color flips, we update the variable current_node to point to the grandparent of the newly inserted node. In our example, this is the 5. We then jump back to the top of our fixing phase loop, which will continue again if the current_node and its parent have become red enemies as a result of our color flips.

However, in our previous example, the loop terminates without repeating. This is because the current_node happens to be the root node, which, by definition, doesn’t have a parent in the first place, so it can’t have a parent who is also red. And so, we’re done with our entire fixing phase, and the tree is once again in compliance with the Red-Black Rules.

Let’s look at an example of where the fixing phase loop would run more than once.

Say that we have this tree:

If we insert a 77, we get:

The 77 is red enemies with the 80, so our fixing phase loop begins.

This is the Red-Uncle Case since the 77’s uncle, 95, is red. And so, we begin with the color flips. That is, we flip the grandparent red, and the grandparent’s children (the current_node’s parent and uncle) black:

Before beginning the next round of the loop, we update the current_node to point to the grandparent, which in this case is the 90:

We check to see if the current_node and its parent are both red, and lo and behold, they are! It turns out that by resolving the red enemies violation of the 77 and the 80, we introduced a new red enemies violation with the 90 and 100.

Now, this is also a Red-Uncle Case since the 90’s uncle, 50, is red. This means that we need to perform our color flips again, namely, turning the grandparent red and the parent and uncle black:

We gear up for the loop’s next round by turning the 90’s grandparent into the current_node. In this case, the current_node is now the root. And because the root and its parent aren’t both red (since the root doesn’t even have a parent), we’re done.

We’ve successfully covered the first two cases of the fixing phase: the Root-Parent Case and the Red-Uncle Case. This brings us to our final case.

The Missing-Or-Black-Uncle Case

Take a look at the section of a red-black tree .

If we insert a 25, we get a red enemies violation:

To resolve this violation, we begin our loop. Now, this is a Missing-Uncle Case since our current_node 25 has no uncle. (That is, its parent, 20, has no sibling.)

The Wrong Solution

Let’s first explore why we can’t use the same solution from the Red-Uncle Case. Again, the technique in the Red-Uncle Case is to flip the grandparent red and have the grandparent bequeath its black color to its children. This potentially fixes things because one of the grandparent’s children is the current_node’s parent. And so, if the current_node’s parent becomes black, we resolve the red enemies violation between the current_node and its parent. In this case, the grandparent has only one child, so our tree will become this:

This tree appears to stick to all the Red-Black Rules, as there are no red enemies and each path seems to have the same black height. But, alas, this is not true. Remember the phantom nodes? We need to measure the black height of each path, keeping the phantom nodes in mind, as shown in the .

While most of the paths have a black height of 2, the path coming off the phantom left child of the 15 has a black height of 1, so our tree would be in violation of the Black Height Rule.

So, the trick of having a grandparent bequeath its black color to its children only works when it can turn both of its children black. If it turns only one of its children black, it causes its descendant paths to have differing black heights.

This is also true in a Black-Uncle Case. Let’s look at such a case:

We’re only focusing on a piece of a larger tree since a Black-Uncle Case happens to never occur at the bottom of a tree. It can only happen during our loop as we work our way up through the tree.

In any case, the 25’s “Uncle 11” is black. If we were to try to resolve this by having “Grandma 15” bequeath her black color to both of her children, we’d be increasing the black height of her right-child path by one, while the black height of her left-child path would remain the same because the left child, 11, is already black. So we’re increasing the black height of the right path by one, while we’re not at all increasing the black height of the left path. This, in turn, results in a black height violation.

The Right Solution

It turns out that the technique used to resolve the Red-Uncle Case will not help for our case. Instead, for a Missing-Or-Black-Uncle Case, we actually do perform the aforementioned color flips. However, we also need to perform a rotation. We will perform either one or two rotations depending on the formation of the current_node and its parent and grandparent. Brace yourself, as the Missing-Or-Black-Uncle Case is subdivided into two further subcases. (Evil laugh. Just kidding; it’ll be fine.)

One subcase is where the current_node and its parent have the same orientation. That is, they are either both a right child or both a left child of their respective parents. For example:

Both the 25 (which is the current_node) and the 20 are right children of their respective parents. However, the other subcase is when the current_node and its parent have opposite orientations, like this:

The 17 (which is the current_node) is its parent’s left child, while the 20 is its parent’s right child.

Let’s take a look at how to deal with both subcases.

Subcase 1: Same Orientation

If the current_node and its parent have the same orientation, we only need to perform a single rotation plus a couple of color flips. Here’s the precise algorithm:

1. Flip the current_node’s parent black.
2. Flip the current_node’s grandparent red.
3. Perform a rotation between the current_node’s parent and grandparent. (Whether it’s a clockwise or counterclockwise rotation depends on whether the parent is a left or right child of the grandparent.) And then you’re done.

Let’s take a look at this in action. Here’s our current Missing-Uncle Case:

We flip the current_node’s parent black and grandparent red:

We then perform a rotation of the parent and grandparent, that is, the 20 and the 15. In this case, because the parent is the grandparent’s right child, we perform a counterclockwise rotation:

And we’re done! Our tree is now completely fixed.

Subcase 2: Opposite Orientations

When you encounter the other subcase, in which the current_node and its parent have opposite orientations, you need to perform one extra rotation before moving on to the same set of steps from the previous subcase. Take the following example:

If we insert a 2, we get:

The 2 and 1 form a red enemies violation. The current_node (the 2) has no uncle, so this is a Missing-Uncle Case. In particular, it’s the subcase in which the current_node and its parent don’t have the same orientation. That is, the 2 is a right child, but the 1 is a left child. This means we’re going to perform two rotations.

We’ll see in the next section exactly why we need two rotations, but let’s proceed with the algorithm details:

1. Perform a rotation between the current_node and its parent. Pay special attention to the fact that this rotation will transform the current_node’s parent into the current_node’s child.

2. Make this new child the current_node.

3. Flip the current_node’s parent black.

4. Flip the current_node’s grandparent red.

5. Perform a rotation between the current_node’s parent and grandparent, and then you’re done.

Note that steps 3, 4, and 5 for this subcase are identical to the final three steps of the first subcase. But in this second subcase, we perform a couple of extra steps first.

Returning to our example, we’ve inserted the 2 and created a red enemies violation with its parent. Our next step is to perform our first rotation, which rotates the current_node and its parent.

In our case, the 2 is the 1’s right child, so we perform a counterclockwise rotation:

Next, we update the 1 to be the new current_node:

Updating the current_node in this way isn’t a critical step, but doing so makes it so that the remaining steps of our algorithm can be described in exactly the same way as the steps of the algorithm for the previous subcase. Again, Steps 3–5 of this algorithm are the same as Steps 1–3 of the first subcase’s algorithm.

Next up, we flip the current_node’s parent black, and grandparent red:

We now perform the second (and final) rotation. Specifically, we rotate current_node’s parent and grandparent. This will be a clockwise rotation because the parent is the grandparent’s left child:

And our red-black tree is completely fixed!

Why the Double Rotation

To see why we needed two rotations for this last subcase, let’s return to the moment where we first inserted the new node:

If we tried to jump right away to the final rotation, where we rotate the current_node’s parent and grandparent (the 1 and the 3), we get this:

This step doesn’t get us any closer to balancing the tree. Before this rotation, our tree was five levels deep, and after the rotation, it’s still five levels deep.

What this boils down to is this: when we have a node, parent, and grandparent that are all in the same orientation, rotating the parent and grandparent will balance that tree segment. For example, take this three-level tree segment:

When we rotate the parent and grandparent, we turn it into the following perfectly balanced two-level segment:

But, say we have this tree segment where the A and the B do not have the same orientation:

Rotating the parent and grandparent merely turns it into a mirror of itself without doing anything to balance it:

So instead, we do a double rotation. That is, if we have a segment like this:

We first rotate the bottom node and its parent (in this case, the B and A):

And then we rotate the new parent with the grandparent (the B and the C):

And so the tree becomes balanced.

With a double rotation, I like to think of the first rotation as being the segment straightener—it straightens out the segment so that both the bottom node and its parent are now of the same orientation. Once the segment is straightened, we perform the second rotation, which perfectly balances that segment.

Wow. We’ve gone through a lot of details. If your head isn’t spinning a little bit, that makes one of us. Ready to put it all together?

The Grand Finale: The Complete Insertion Fixing Algorithm

I now present to you The Complete Insertion Fixing Algorithm. It may not be fun to read, but it’s a great reference. Here goes:

1. Insert the new node in the correct spot in the tree (according to BST rules) and color the new node red. This new node is dubbed the current_node.

2. Begin a loop that lasts while the current_node and its parent are both red. (If they’re not both red, skip to Step 17—you’re done!)

3. If the parent is the root, color the root black and skip to Step 17—you’re done.

4. Inspect the current_node’s uncle to see if it exists and what color it is.

5. If the uncle is not red, break out of the loop and skip to Step 11; this is the Missing-Or-Black-Uncle Case.

6. If the uncle is red, this is the Red-Uncle Case and proceed with the steps 7–11.

7. Color the current_node’s parent black.

8. Color the current_node’s uncle black.

9. Color the current_node’s grandparent red.

10. Make the grandparent of the current_node the new current_node and repeat the loop from Step 2.

11. Check if the current_node and its parent have the same orientation. If they do, skip to Step 14. If they do not have the same orientation, proceed with steps 12–17.

12. Perform a rotation between the current_node and its parent.

13. This rotation transformed the current_node’s parent into the current_node’s child. We make this new child the current_node.

14. Flip the current_node’s parent black.

15. Flip the current_node’s grandparent red.

16. Perform a rotation between the current_node’s parent and grandparent.

17. Top with lemon or your favorite garnish. Serves 6.

If you’re a flowchart person, look—I made something for you. The flowchart depicts these steps in visual form.

Let’s walk through one final example. The step numbers that follow correspond to the step numbers in our list of steps. Take the following tree:

Step 1: We insert a 77, as shown in the .

The 77 is the current_node. Both it and its parent, the 75, are red.

Step 2: We begin a loop that will last as long as the current_node and its parent are both red.

Step 3: The parent is not the root, so we’ll move on to the next step.

Step 4: Inspect the current_node’s uncle to see its color:

Steps 5 and 6: “Uncle 85” happens to be red. This is a Red-Uncle Case, and we therefore proceed through the loop.

Steps 7, 8, and 9: We flip the current_node’s parent and uncle black, and flip the grandparent red:

Step 10: We turn “Grandpa 80” into the current_node:

We go back to Step 2 to begin the loop again. The current_node and its parent are both red, so we continue to Step 3, which inspects the uncle. “Uncle 25” is black, which brings us to Step 5, which tells us to break out of the loop and skip to Step 11.

Step 11: We check whether the current_node and its parent have the same orientation. They do not, so we continue to Step 12.

Step 12: We rotate clockwise the current_node, 80, and its parent:

Step 13: The 100, which is now a child of the 80, becomes the new current_node:

Steps 14 and 15: Flip the current_node’s parent black, and grandparent red:

Step 16: Rotate the current_node’s parent and grandparent counterclockwise:

And WE. ARE. DONE.

Ready for some code?

Code Implementation: Red-Black Tree Insertion (Fixing Phase)

For this code implementation, I added comments within the code to connect each line to its corresponding step from . Instead of boring you with a long-winded code walk-through, I’ll let you match up each line of code to our list of steps.

Note that the main method is the fix_insert method, but it does rely on a series of helper methods:

​	​def​ ​fix_insert​(self, current_node):
​	​# Step 1 was accomplished by the `insert` method​
​	​# which calls this fix_insert method​
​	​while​ self.has_red_parent(current_node): ​# Step 2​
​	​if​ current_node.parent == self.root: ​# Step 3​
​	self.root.color = ​"black"​
​	​return​
​
​	uncle = self.find_uncle(current_node) ​# Step 4​
​	​if​ uncle ​and​ uncle.color == ​"red"​: ​# Step 6​
​	current_node.parent.color = ​"black"​ ​# Step 7​
​	uncle.color = ​"black"​ ​# Step 8​
​	current_node.parent.parent.color = ​"red"​ ​# Step 9​
​	current_node = current_node.parent.parent ​# Step 10​
​	​else​: ​# uncle is None or black Step 5​
​	​break​
​
​	​if​ self.has_red_parent(current_node):
​	​# The next line calls the straighten_segment method​
​	​# which accomplishes Steps 11, 12, and 13​
​	current_node = self.straighten_segment(current_node,
​	current_node.parent)
​	current_node.parent.color = ​"black"​ ​# Step 14​
​	current_node.parent.parent.color = ​"red"​ ​# Step 15​
​	self.perform_final_rotation(current_node.parent) ​# Step 16​
​
​	​def​ ​has_red_parent​(self, node):
​	​return​ node.parent ​and​ node.parent.color == ​"red"​
​
​	​def​ ​parent_is_root​(self, node):
​	​return​ node.parent == self.root
​
​	​def​ ​is_a_left_child​(self, node):
​	​return​ node == node.parent.left_child
​
​	​def​ ​is_a_right_child​(self, node):
​	​return​ node == node.parent.right_child
​
​	​def​ ​find_uncle​(self, node):
​	​if​ self.is_a_left_child(node.parent):
​	​return​ node.parent.parent.right_child
​	​else​: ​# parent is a right child​
​	​return​ node.parent.parent.left_child
​
​	​def​ ​straighten_segment​(self, node, parent):
​	former_parent = parent
​	​if​ self.is_a_left_child(parent) ​and​ self.is_a_right_child(node):
​	self.rotate_counterclockwise(parent, node)
​	​return​ former_parent
​	​elif​ self.is_a_right_child(parent) ​and​ self.is_a_left_child(node):
​	self.rotate_clockwise(parent, node)
​	​return​ former_parent
​	​else​: ​# no need to straighten the segment​
​	​return​ node
​
​	​def​ ​perform_final_rotation​(self, node):
​	​# If the node's parent is a left child of its OWN parent:​
​	​if​ self.is_a_left_child(node):
​	self.rotate_clockwise(node.parent, node)
​	​else​: ​# if the parent is instead a right child:​
​	self.rotate_counterclockwise(node.parent, node)