Wrapping Up

A red-black tree, while complex, is a dependable data structure that ensures that search, insertion, and deletion remain speedy while also maintaining the order of its values. The key word here is “ensure.” While a regular, good ol’ BST aims to have a speedy efficiency, it can’t absolutely ensure that speeds don’t degrade, which can happen when values are inserted into the tree in order. A red-black tree, on the other hand, does ensure that its operations remain fast since the tree is guaranteed to be pretty well-balanced.

In fact, red-black trees are found under the hood of many applications, some of which we use every day. Some operating systems use them for various functions, including process scheduling, in which scheduled events need to be easily found but also kept in order of time. Some databases use red-black trees for database indexing, a concept we’ll explore more fully in .

Also, I explained in Volume 1, Chapter 8, how collisions can occur within hash tables. There, I showed that one approach for handling this is to place all colliding values within an array or list using separate chaining. The disadvantage to this is that if we’ve encountered a value that collides with other values, we need to linearly search through all the colliding values until we find the one we want. As an alternative, some programming languages use red-black trees to store colliding values. This way, we can find any such value within O(log N) time, where N is the number of colliding values.

One of the biggest drawbacks of red-black trees, though, is their complexity. Sure, once they’re implemented properly, they’ll work as intended. But if you ever have to maintain them or improve them in some way, it could be a doozy to get it right.

In the next chapter, we’re going to look at another type of self-balancing tree that works as well as a red-black tree, but is much, much simpler. And to achieve its performance and simplicity, it uses randomization. Once again, you’ll see how the power of randomization can be used to achieve great things.