9: Red-Black Trees

Open Data Structures - An Introduction · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    9: Red-Black Trees

    In this chapter, 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 \(\mathtt{n}\) values has height at most \(2\log \mathtt{n}\).
    2. The \(\mathtt{add(x)}\) and \(\mathtt{remove(x)}\) operations on a red-black tree run in \(O(\log \mathtt{n})\) worst-case time.
    3. The amortized number of rotations performed 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 \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 \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 \mathtt{n}\) on the height is not easy. It requires a careful analysis of a number of cases. We must ensure that the implementation does exactly the right thing in each case. One misplaced rotation or change of colour 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 them is even possible.


    Footnotes

    1Note that skiplists and treaps also have this property in the expected sense. See Exercises 4.5.6 and 7.3.5.


    This page titled 9: Red-Black Trees was last modified on Sat, 01 May 2021 15:12:14 GMT and is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin (Athabasca University Press) .