The 2–4 Trees

Red-black trees

Here, we present red-black trees, a version of binary search trees with logarithmic height. Red-black trees are one of the most widely used data structures. 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 $n$ values has height at most $2 \log n.$
2. The add(x) and remove(x) operations on a red-black tree run in $O(\log n)$ worst-case time.
3. The amortized number of rotations performed during an add(x) or 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 n)$ running times are only expected. Scapegoat trees have a guaranteed bound on their height, but add(x) and remove(x) only run in $O(\log n)$ amortized time. The third property is just icing on the cake. It tells us ...