9. Red-Black Trees

In this chapter, we present red-black trees, a version of binary search trees that have logarithmic depth. Red-black trees are one of the most widely-used data structures in practice. They appear as the primary search structure in many library implementations, including the Java Collections Framework and several implementations of the C++ Standard Template Library. They are also used within the Linux operating system kernel. There are several reasons for the popularity of red-black trees:

1. A red-black tree storing $\mathtt{n}$ values has height at most $2\log \ensuremath{\mathtt{n}}$.
2. The $\mathtt{add(x)}$ and $\mathtt{remove(x)}$ operations on a red-black tree run in $O(\log \ensuremath{\mathtt{n}})$ worst-case time.
3. The amortized number of rotations done during an $\mathtt{add(x)}$ or $\mathtt{remove(x)}$ operation is constant.

The first two of these properties already put red-black trees ahead of skiplists, treaps, and scapegoat trees. Skiplists and treaps rely on randomization and their $O(\log \ensuremath{\mathtt{n}})$ running times are only expected. Scapegoat trees have a guaranteed bound on their height, but $\mathtt{add(x)}$ and $\mathtt{remove(x)}$ only run in $O(\log \ensuremath{\mathtt{n}})$ amortized time. The third property is just icing on the cake. It tells us that that the time needed to add or remove an element $\mathtt{x}$ is dwarfed by the time it takes to find $\mathtt{x}$.^9.1

However, the nice properties of red-black trees come with a price: implementation complexity. Maintaining a bound of $2\log \ensuremath{\mathtt{n}}$ on the height is not easy. It requires a careful analysis of a number of cases and it requires that the implementation does exactly the right thing in each case. One misplaced rotation or change of color produces a bug that can be very difficult to understand and track down.

Rather than jumping directly into the implementation of red-black trees, we will first provide some background on a related data structure: 2-4 trees. This will give some insight into how red-black trees were discovered and why efficiently maintaining red-black trees is even possible.

Footnotes

....^9.1

Note that skiplists and treaps also have this property in the expected sense. See Exercise 4.6 and Exercise 7.5.