Chapter 13: Red-Black Trees: Properties, Rotations, and Operations

Together these properties guarantee a tree height of at most 2 × log(n + 1), ensuring that SEARCH, INSERT, DELETE, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR all run in O(log n) time. The primary structural tool for maintaining these properties is rotation — left and right rotations that pivot around a node and its child in O(1) time while preserving the BST ordering invariant. Insertion proceeds like a standard BST insert but colors the new node red, potentially creating a double-red violation that is resolved by RB-INSERT-FIXUP through a series of recolorings and at most two rotations across three cases based on the uncle node's color and the inserted node's position, with the root always colored black as a final step. Deletion is more complex, using RB-TRANSPLANT to rewire parent links and then invoking RB-DELETE-FIXUP when a black node is removed, which addresses the resulting "extra black" imbalance through four cases involving the sibling's color and its children's colors, requiring at most three rotations and O(log n) time overall. Beyond the core operations, the chapter surveys a rich ecosystem of related structures — AVL trees, 2-3 trees, B-trees, treaps, splay trees, and skip lists — and notes that red-black trees serve as the backbone of many standard library implementations such as C++'s STL map and set.