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}$.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

....1
Note that skiplists and treaps also have this property in the expected sense. See Exercise 4.1 and Exercise 7.3.


Subsections
opendatastructures.org