Faster, Simpler Red-Black Trees

For more than two decades, functional programmers have refined the persistent red-black tree—a data structure of unrivaled elegance. This paper presents another step in its evolution. Using a monad to communicate balancing information yields a fast insertion procedure, without sacrificing clarity. Employing the same monad plus a new decomposition simplifies the deletion procedure, without sacrificing efficiency.

1. 1.

   The diagrams use the letters x, y, z for values; the letters a, b, c, d for subtrees; and \(\bullet \) for the empty tree.

2. 2.

   Where bh computes the black height of a tree.

3. 3.

   This type is the same as Either, but with more convenient constructors.

4. 4.

   Note that \(\mathtt {<}\)$$\(\mathtt {>}\) is not fmap. The functor instance implied by the monad applies a function only to T values.

5. 5.

   The half-colored nodes indicate that the color could be either red or black.

6. 6.

   Some split balance into balanceL and balanceR [10, exercise 3.10]. For balance, splitting is done for performance rather than convenience.

7. 7.

   The dotted triangle encloses the tree that balance’ is applied to.

Thanks to Matthias Felleisen for his feedback and encouragement. Also, thanks to Ben Lerner, Jason Hemann, Leif Andersen, Michael Ballantyne, Mitch Gamburg, Sam Caldwell, audience members at TFP, and anonymous TFP reviewers for providing valuable comments that significantly improved the exposition.

Much of the code in this paper was directly adapted or at least heavily influenced by the code of Okasaki [11] (for insertion) and Germane and Might [6] (for deletion). They deserve a great deal of credit for the final product.

This work was partially supported by NSF grant SHF 2116372.

Authors and Affiliations

1. PLT, Northeastern University, Boston, MA, 02115, USA

   Cameron Moy

Corresponding author

Correspondence to Cameron Moy .

Editors and Affiliations

1. University of Massachusetts Boston, Boston, MA, USA

   Stephen Chang

A Racket Implementation

This section shows a Racket port of the Haskell code. Monads can be implemented in many ways, but the following code uses macros and multiple return values [2] to do so. This choice yields excellent performance.

B Performance Evaluation Correction

Germane and Might [6] incorrectly conclude that their algorithm is always significantly slower than other approaches. This conclusion is due to a subtle confounding factor that put their algorithm at an unfair disadvantage.

To understand the flaw, consider this skeleton of their delete function:

It highlights the two most common cases during deletion, when the current node does not match the target and the function recurs on either the left or right side. However, the structure of the code forces each of the base cases to be checked first—before the most common cases.

To favor the common cases, the skeleton should look as follows:

The base cases are only checked at the target node. This simple modification improves the performance of the double-black algorithm by \(2 \times \).

Reprints and permissions

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics