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:
However, the nice properties of red-black trees come with a price: implementation complexity. Maintaining a bound of 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.