Chapter 5
The Great Balancing Act of Red-Black Trees

One of the most fundamental and useful data structures out there is the binary search tree, or BST for short. (I covered BSTs at length in Volume 1, Chapter 15.) However, as I pointed out in , BSTs lose their special powers if they become imbalanced.

In this chapter, I’ll introduce you to self-balancing BSTs. These are BSTs that use clever algorithms to ensure that the tree never becomes too imbalanced. The main focus of this chapter is the red-black tree, a widely used self-balancing BST that is also one of the classic data structures of computer science. You’ll discover how red-black trees work, why they work, and how to create your own basic red-black tree from scratch.

Red-black trees have a certain notoriety for being complicated, and while this chapter is indeed on the long side, I’ll lay everything out for you in a way that makes it all easier to digest. So, let’s jump right in.