Skip to main content
Definition Website Computer and Technology

Red-Black Tree

Subject: Computer and Technology noun /ˈrɛdˌblæk ˈtriː/ 1 definition

  1. Definition (noun)

    Entry #50 · Updated

    A Red-Black Tree is a self-balancing binary search tree in which each node carries an extra color bit—red or black—used to enforce structural balance across every root-to-leaf path. By requiring that the root be black, treating null leaves as black, prohibiting adjacent red nodes, and keeping an equal count of black nodes along every path from any node to its descendant null leaves, the tree guarantees that the longest root-to-leaf path is never more than twice the length of the shortest. This invariant bounds tree height to O(log n) and ensures O(log n) worst-case time for search, insertion, and deletion through local recoloring and at most a constant number of tree rotations per update. Compared with stricter structures such as AVL trees, a Red-Black Tree permits slightly looser height balance in exchange for faster, bounded-rotation modifications in write-heavy workloads.

    Common Types

    • Left-Leaning Red-Black Tree (LLRB): Restricts red links to left children in its standard 2-3 formulation, establishing a direct correspondence with 2-3 trees and simplifying rebalancing logic.

    • Augmented Red-Black Tree: Stores auxiliary summary fields in each node—such as subtree counts for order-statistic queries or maximum bounds for interval trees—and updates them in O(1) per node across rotations.

    • Intrusive Red-Black Tree: Embeds the tree's link pointers and color metadata directly inside caller-managed structs rather than separate wrapper nodes, avoiding extra heap allocations in low-level systems such as the Linux kernel.

    • Persistent Red-Black Tree: Preserves prior versions across modifications by allocating new nodes only along the changed root-to-leaf path while sharing untouched subtrees, supporting immutable snapshots in functional data structures.

    Example

    An algorithmic trading engine maintains active limit-order price levels in a C++ std::map—implemented as a Red-Black Tree—to support ordered price traversal alongside fast lookups, insertions, and cancellations. Even when 100,000 price updates arrive in strictly ascending order during a market surge, node recoloring and rotations prevent the tree from skewing into a linear chain and keep every update bounded to O(log n) time.