Red-Black Trees

The need for an efficient self-balancing tree is precisely why computer scientists developed the red-black tree. The tree bears this name because its nodes are colored either red or black, for reasons we’ll look at shortly. Using brilliant algorithms, red-black trees keep themselves balanced and do so without taking too much extra time.

While these trees are clever and fast, they’re complex and involve many details. Most presentations of red-black trees plow straight into these details, getting into the weeds right away. This usually leaves people terribly confused.

As such, I’d like to start not with the what, but rather with the why and the how. Like peeling an onion, we’ll unpack this topic one layer at a time. This should make red-black trees considerably easier to grasp.

Rotations—Part 1

Let’s start with a visual example of how red-black trees maintain balance. Look at this terribly imbalanced tree:

In the following diagram, I highlight one particular segment of the tree:

Now, watch what happens when I bend that segment ever so delicately:

The 2 becomes the root instead of the 1:

The tree is now a little more balanced than before.

That was fun! Let’s do it again. Here, I highlight another tree segment:

And watch what happens when I bend that segment:

The 3 becomes the new root, and voila! The tree is now perfectly balanced:

This bending technique is known as performing a rotation. That is, we rotate segments of the tree. In this example, I happened to rotate two different tree segments. And if you look carefully, you’ll see that I rotated them in a counterclockwise direction.

This is a general idea of how rotations work (as rotations have a whole bunch of additional details to them). The gist is that as we insert and delete values from the tree, we perform these rotations when necessary to maintain the tree’s balance.

However, it’s not so easy to tell the computer when and how it should perform these rotations. This is especially true when dealing with a large, complex tree. We need a set of algorithms that list the cases for when a rotation is necessary and provide instructions on how to perform the rotation in each case. On top of this, we need to do this quickly. Accordingly, the computer shouldn’t have to analyze the entire tree to calculate how the rotation is to be executed.

To make this task less daunting, clever computer scientists found a way to make it so that these algorithms can work in bite-sized chunks. That is, upon each insertion and deletion, only a small subset of the tree needs to be analyzed, and a minimum number of rotations need to be performed. To accomplish this, they proposed a self-balancing tree that contains two types of nodes: one red and one black. Over time, you’ll see how this setup helps our situation, but let’s first look at the nature of this tree.

A Tale of Two Nodes

As mentioned, red-black trees get their name from the fact that they have two types of nodes that we treat as being either “red” or “black.” Let me explain what that means.

Here’s some basic code representing a node:

We can turn this node into either a “red” node or a “black” node by adding a new attribute to it:

We can now assign to the node’s self.color a string value of either "red" or "black".

The idea behind assigning a color to a node is simply so that we have a mechanism for designating two different types of nodes. (We’ll see soon why this is important.)

Now, to create two different types of nodes, we could have used any type of attribute. For instance, we could have assigned nodes different shapes, or different sizes, or different letters. We could even assign nodes different characters from The Lord of the Rings if we were feeling so inclined. Whatever attribute we use, the main goal is to have two different types of nodes. True, nodes are already different in that they contain different values, but we’re looking to also put all nodes into two different general categories.

And so, we have color. The colors didn’t have to be red and black; they could have been anything. I’m pretty sure, though, that they chose red and black instead of white and black to annoy authors who publish books with images that are only black and white.

And that brings me to my next point. In this book, the diagrams represent red nodes using white-colored nodes like this:

Here’s a pro tip: if you wear red-tinted glasses while reading this book, the images will look perfect.

The thing to address, now, is what we gain by having different types of nodes. When a tree has different types of nodes, we can construct algorithms that only have to analyze and deal with small sections of the tree rather than having to analyze the entire tree, which naturally would take time. Instead, the algorithm can analyze the section of the tree where it inserted or deleted a node, and by examining the pattern of surrounding nodes and their colors, it can perform appropriate rotations on that section of the tree.

As you’ll see later in this chapter, a tree segment may have various patterns, such as a black node with two red child nodes, or vice versa. The algorithm will know what to do with each pattern, including whether a rotation is in order, and if so, how to execute the rotation. As you may imagine, there are a number of possible patterns, and that’s exactly what makes a red-black tree complex; we need our algorithm to handle all of these patterns. And, sometimes, performing a rotation may form a new pattern that will require yet another rotation.

But truly, these concepts aren’t difficult in themselves. It’s just that there are a lot of details. Luckily for you, I spell them all out right here.