The Red-Black Rules

As mentioned, a red-black tree consists of nodes that are either red or black. There’s no way around this; each node must choose a side. You can’t have a node that has no color at all, or a node that is both red and black, or a node that prefers to be mustard yellow. Each node is either red or black, period.

However, not every tree that consists of red and black nodes is deemed a valid red-black tree. There are two major rules, which I call “The Red-Black Rules,” that a tree must adhere to for it to be admitted into the official red-black tree club:

• The Black Height Rule: Each path from the root node to the bottom of the tree must contain the same number of black nodes.

• The Red Enemies Rule: A parent and child cannot both be red. Think of red nodes as being angry enemies; you can’t put them next to each other!

The Black Height Rule takes its name from a concept known as black height. Take a look at the following red-black tree:

If you follow the path from the root node down to each leaf (a node that has no children, and is the final node of a path), you’ll see that each path has three black nodes. The number by each node in this illustration shows how many black nodes there are from the root to that node. This means that each path in our tree has a black height of 3.

The following tree is an invalid red-black tree since different paths have varying numbers of black nodes:

In this tree, some paths contain two black nodes, while others contain three black nodes, and yet others contain four black nodes. This violates the Black Height Rule, and the tree is, therefore, invalid. It may be red and black, and it may be a tree, but it’s not a red-black tree.

The Black Height Rule is the driving force behind ensuring the tree’s balance, and here’s why.

Imagine for a moment that there was no such thing as red nodes, and instead, our tree could only contain black nodes. The Black Height Rule enforces that a tree can never be imbalanced. Take this imbalanced tree:

This tree is imbalanced because its two paths have different black heights. The Black Height Rule would never allow this to happen. By definition, a tree with only black nodes where all its paths have the same black height is going to be balanced.

However, if we continue in this imaginary world where our tree can only contain black nodes, we quickly run into a major problem. Take a look at this perfectly balanced tree:

If we want to insert a new black node, where can we put it? We can’t put it anywhere since the insertion will cause one path to have a greater black height than the other paths! And this is why red-black trees also contain red nodes. Inserting a red node into a tree will never directly cause a violation the Black Height Rule, and it will allow us to grow the tree.

On the other hand, it would seem that the existence of red nodes can pull the rug from under the feet of the Black Height Rule. That is, while the Black Height Rule is trying to ensure that each path of the tree has the same black height, we can still make a tree highly imbalanced, like this:

This, my friends, is why the Red Enemies Rule exists. Again, the Red Enemies Rule states that we can’t have a parent and its child both be red, so this tree is invalid.

So, the Black Height Rule and Red Enemies Rule work in tandem to create a balanced but flexible tree. The Black Height Rule enforces balance, while the existence of red nodes provides some flexibility for tree growth. At the same time, the Red Enemies Rule prevents an abundance of red nodes from making the tree imbalanced.

Balanced Enough

A red-black tree does not always maintain perfect balance, however. Let’s see how imbalanced we can make a red-black tree, even while adhering to our two rules. Here, again, is a perfectly balanced tree:

Let’s try to add red nodes to make this tree as imbalanced as possible. What I came up with is shown in the .

Here, I extended the left branch of the tree by inserting red nodes between all the black nodes. And I didn’t violate any rules! Each path has the same black height, and we don’t have any red nodes connected to each other.

Indeed, a red-black tree is not designed to be perfectly balanced. Rather, it is designed to be balanced enough. While “balanced enough” sounds like some sort of subjective term, we can give it a firm and objective definition. That is, the goal of a red-black tree is to guarantee that it’s impossible to make one path more than twice as long as another path.

Here’s why this is so. If, with any red-black tree, I were to try to make one path longer than the others, I can’t add more black nodes without violating the Black Height Rule. And I also can’t string a bunch of red nodes together without creating red enemies. Instead, my only option is to insert a red node between every other black node. At most, then, I can double the length of one path over the others, but I can’t push it any further.

Ultimately, the combined push and pull of the Red-Black Rules make it so that a red-black tree remains pretty well-balanced and yet flexible enough to insert and delete nodes.

Phantom Nodes

Okay, pop quiz time! Is the following tree a valid red-black tree?

It seems hard to call this a red-black tree when it doesn’t contain any red nodes. Yet, it does not violate any of our rules. All paths have the same black height, and there certainly aren’t any two adjacent red nodes. So it is, indeed, valid. How about this one?

If you answered that it’s invalid, you’re correct since it has a pair of red enemies:

And now, I’m going to throw a monkey wrench into everything with a trick question. (Sorry!) Is the next tree a valid red-black tree?

It certainly has no adjacent red enemies, that’s for sure. And we don’t seem to have different paths with different black heights because apparently there is only one path. So the tree seems valid. However, this is pretty disturbing. We learned that the Red-Black Rules try to ensure balance, but this tree is the ultimate imbalanced tree! What has the world come to?

The answer to this is based on a concept known as phantom nodes. (Spooky!) When analyzing a red-black tree, we have to fill the tree in with imaginary, phantom nodes. Here’s what I mean.

Each node in a BST has the ability to hold two children: a left child and a right child. However, in a typical BST, some nodes have two children, some have one, and the leaves have none. In a red-black tree, in each spot where a node could potentially have a child but does not, we fill that spot in with an imaginary node. Let me demonstrate with an example.

In the tree from the previous diagram, the top four nodes each only have a left child, and the leaf has no children at all. This means that there are a number of empty spots in the tree where a child could exist but does not. Specifically, the top four nodes have empty spots for a right child, and the bottom node has two empty spots for both of its potential children. Therefore, we populate all the missing spots with phantom nodes. In the following image, a phantom node is represented with the letter N, representing None:

In your code, you don’t need to implement phantom nodes (although some people do). However, the reason why these phantom nodes are important is that they totally change the way we look at black height. That is, without phantom nodes, this tree has only one path and doesn’t violate the Black Height Rule. But with the phantom nodes, the tree now has multiple paths since each path from the root to a phantom node is considered a viable path. With this in mind, here are the black heights of the tree’s paths:

Note that the phantom nodes themselves do not increase a path’s black height. However, each phantom node represents a path’s destination.

Now we can see that this tree violates the Black Height Rule many times over. There are six paths, and almost all of them have different black heights. We can now breathe a sigh of relief since the Black Height Rule indeed will prevent such an imbalanced red-black tree from ever existing.

Technically, then, the Black Height Rule should be restated to accommodate phantom nodes. Here goes:

• The Black Height Rule: Each path from the root node to any phantom node must contain the same number of black nodes.

Let’s look at one more example to solidify all of this. Is the following tree a valid red-black tree?

It is not. When the phantom nodes are revealed, we’ll see that while most paths from the root to each phantom node have a black height of 2, there’s one path that has a black height of 1:

I omit these phantom nodes in most of the diagrams that follow. However, they’re important to keep in mind when calculating the black height of a tree’s path. Again, some people do implement phantom nodes in their code, but it’s not necessary. Our implementation—which we’ll get to eventually—will leave them out so as to keep the code more concise. We can get away with this because the red-black tree insertion and deletion algorithms don’t bother to count a path’s black height. Instead, the algorithms follow a different set of patterns, as we’ll soon see.

On that note, some of the literature states that there’s a convention to always make sure that the root of a red-black tree remains black. That is, it should start out as black, and if it somehow becomes red (you’ll see later in this chapter how this can happen), we should color it black again. However, this is only a convention, and not necessary. Once again, we’ll ignore it to simplify our code. But it’s good for you to know that it exists.

Rotations—Part 2

So far, I’ve mentioned two general ideas regarding how a red-black tree maintains its balance. One is the technique of rotation, in which we bend the tree in advantageous spots. The other is the Red-Black Rules. These two concepts work together, and here’s how.

Each time we insert or delete a node from the tree, we often cause a violation of the Red-Black Rules. (You’ll see examples of this shortly.) To get the tree back in compliance with the rules, we rotate sections of the tree.

In other words, a tree that follows the Red-Black Rules will always be reasonably balanced. But to get our tree to comply with these rules, we often have to perform rotations. And that’s how the Red-Black Rules and rotations relate to each other.

I described rotations in a general way in . Here, though, I delve into precisely how rotations work.

Whenever we perform a rotation, we focus on two nodes: a parent and a child. These nodes can be anywhere in the tree, but the diagrams that follow zoom in on these two nodes. Take the following example, with a parent node called B and a left child node called A:

Let’s rotate this tree segment clockwise:

This leaves us with:

As you can see, a rotation does two major things:

1. What was the parent now becomes the child, and what was the child now becomes the parent.

2. The left-right orientation of the parent-child relationship switches. In this example, the child was originally a left child, but what is currently the child is now a right child of its parent.

Rotations can also go counterclockwise. As you’re about to see, they’re a mirror opposite of a clockwise rotation. Here’s an example in which B is the right child of A:

Whenever we rotate a parent and child, the determination as to whether it should be clockwise or counterclockwise depends on whether the child is the left or right child. When it’s the left child, as in the previous example, we perform a clockwise rotation. When we have a right child, as in the present scenario, we perform a counterclockwise rotation:

This gives us:

Note that after we rotate the nodes counterclockwise, they end up in the state that the nodes looked like before a clockwise rotation. Similarly, after we rotate the nodes clockwise, they end up in the state that the nodes looked like before a counterclockwise rotation. In theory, we could take the same two nodes and rotate them back and forth forever, but of course, that would be completely pointless.

Let’s see what this all looks like in the context of a larger tree such as this one:

Although most of the nodes hold integer values, I snuck A and B nodes into the tree as well. Let’s focus on those two nodes since those are the ones we’re going to rotate.

Because A is B’s left child, we execute a clockwise rotation:

A is now B’s parent, and B has become the right child of A. Note that the 6, which was A’s left child, is still A’s left child even after the rotation. Similarly, the 8 has never changed from being B’s right child.

Also, note how we’ve “pulled” the 6 closer to the top of the tree, while “pushing” the 8 down. In this case, the tree isn’t any more balanced than before. However, if the 8 didn’t exist, this rotation would have transformed the tree from being a four-level tree into a three-level tree, and also made the tree perfectly balanced.

Keep in mind that since a red-black tree is a type of BST, not only does the tree have to adhere to the Red-Black Rules, but it also has to follow the rules of any BST. The main rule regarding a BST is that for each node of the tree, the node’s left descendants must all have smaller values than it, and the node’s right descendants must all have greater values than it.

One of the key things to know about rotations is that they never interfere with this BST rule. No matter how many segments you rotate clockwise or counterclockwise, the tree will always remain a valid BST. As such, we can perform rotations to fix Red-Black Rule violations without ever having to worry that we may inadvertently introduce a new BST rule violation.

Crossover Nodes

There’s one more detail about rotations that’s important to know. To help illustrate the concept, I’ll pose a conundrum: how would you rotate the A and B nodes in the following tree? Grab a pencil and paper and try to do this yourself before moving on.

You’ve learned that we need to rotate these nodes in a clockwise fashion because the parent, B, has a left child. But here’s the thing: with a clockwise rotation, B will become A’s right child. However, A already has a right child—the star! So, the problem is what we’re supposed to do with the star node.

In such cases, rotations perform one more switcheroo: specifically, we designate the star to be a crossover node. That is, the star crosses over by completely detaching itself from the A, and becoming a left child of B:

Now, there’s no reason to worry about what happens if B already has a left child because A was B’s left child! So, by definition, when we make it so that A is no longer B’s child, that automatically opens up a spot for B to have a new left child. The same applies to a counterclockwise rotation, but in reverse. Take the following tree, for example:

We run into a problem when trying to turn the A into the B’s left child since B already has the star left child. So, we pull off the same crossover node trick as before by making the star become A’s right child:

To sum it all up, a rotation involves either two or three changes to the tree:

1. The child and parent switch places.

2. We switch the orientation of the parent-child relationship. If we had a left child, we now have a right child, and vice versa.

3. If the new parent (say, A) already has a child (say, the star), where the new child (say, B) is supposed to go, we turn the offending node (the star) into a crossover node and make it a child of B, with the opposite orientation. That is, if the crossover node was a right child of A, it now becomes a left child of B, and vice versa.

Let’s put this all together in the context of a realistic tree where there are no letters or stars, but only integers. In the following diagram, we’re going to rotate the 5 and the 8:

The 8 is the 5’s right child, so we’re going to rotate counterclockwise. However, the 6 is an offending node because it’s blocking us from turning the 5 into the 8’s left child. So we have the 6 cross over and become the 5’s right child:

Note that the crossover node’s children come along with it. In this example, the 7 remains the right child of the crossover node just as before.

Okay, we’re almost ready to tackle inserting new values into a red-black tree. But because rotations play a crucial role in these algorithms, let’s implement the rotations first.

Code Implementation: Nodes and Rotations

Here’s an implementation of a red-black tree node:

As with a regular BST node, we’ve established attributes for the node’s value, left_child, and right_child. And because we’re dealing with a red-black tree, we’ve also added the critical color attribute that we’ve previously described.

However, you’ll also note that this code includes a parent attribute as well. While this wasn’t necessary for the regular operations of the classic BST, it makes the implementation of a red-black tree’s operations more straightforward, as you’ll see soon.

The parent attribute allows each child node to point to its parent. This is akin to a doubly linked list, where each node links not just to its next node, but also to its previous node. Here as well, each node links both to its children and to its parent. Each node will have a parent except for the root node, whose parent will remain None.

Let’s begin implementing the actual RedBlackTree. This class will contain a lot of code by the time we’re done, but here’s the basic class plus its rotation operations:

The class constructor initializes the tree’s root, which represents the root node of the tree. Like a classic BST, we’ll need to keep track of this at all times.

We then have the rotation methods, rotate_counterclockwise and rotate_clockwise. The good news is that the logic behind one method is the symmetrical inverse of the other, so we only need to analyze one method in depth. We’ll do this with the rotate_counterclockwise method.

We pass the arguments a and b into the rotate_counterclockwise method, representing the A and B nodes from this diagram:

Alternatively, we could have passed one of the nodes in, such as A, and deduce that B is the right child of A since that is always the case when we perform a counterclockwise rotation. However, I prefer setting up the method signature in such a way that makes it clear which two nodes we’ll be rotating.

For a moment, let’s skip to the end of the method, where the essence of the rotation takes place:

Before the rotation, B was the right child of A. With this snippet, we transform A into the left child of B, which yields:

The rest of our method deals with the crossover node and a couple of other details. So let’s jump back to the top of the code, which handles all of that:

First, we update A’s right child. Previously, A’s right child was B. However, now that A no longer has B as a child, we need to update this.

Now, if B has a left child, this child will be the crossover node. Accordingly, we turn the crossover node into A’s right child. On the other hand, if B does not have a left child, this means that its child is None, so now A’s right child will also be None.

We then check to see if B actually did have a left child, which again is the crossover node. If this is the case, we make sure to set the crossover node’s parent to now be A.

Next up, we redefine who B’s parent is. Again, B’s parent used to be A, but our rotation is going to turn B into A’s parent. That leaves us hanging with the issue of who B’s parent will be. Here’s the code that deals with this:

Because B is taking over A’s spot, we need to explicitly turn B into the child of the node that was A’s parent. Whenever you do something like this, you need to perform two distinct steps:

1. Declare B’s parent to be what was A’s parent
2. Declare within A’s parent node that it now has a child B

If A was its parent’s left child, then we need to make B its new parent’s left child. And if A was its parent right child, then we need to make B its new parent’s right child.

If it turns out that B’s new parent is None, that means that B is in the root position and we need to declare that the tree’s self.root is now B.

The rotate_clockwise method, as mentioned, has the exact same logic as rotate_counterclockwise, except that everything is the mirror opposite.

We’re finally ready to explore a red-black tree’s most important operation: insertions.