Red-Black Tree
Visualize self-balancing binary search trees through nodes and recoloring.
Red-Black Tree
Concept Overview
A Red-Black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" (red or black), used to ensure the tree remains approximately balanced during insertions and deletions. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed such that this rearranging and recoloring can be performed efficiently.
Mathematical Definition
A Red-Black tree must satisfy the following invariants, which guarantee that no path from the root to a leaf is more than twice as long as any other path, ensuring logarithmic height:
2. The root is always black.
3. All leaves (NIL nodes) are black.
4. If a node is red, then both its children are black. (No two adjacent red nodes on a path).
5. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes (the "black-height").
Theorem: A Red-Black tree with n internal nodes has height h ≤ 2 log2(n + 1).
Key Concepts
- Rotations: Left and right rotations are local structural changes that preserve the binary search tree property while modifying tree depths, essential for rebalancing after an insertion or deletion.
- Color Flipping: Changing the color of a node and its siblings/parents without affecting the black-height property, typically propagating a "red violation" up the tree towards the root.
- Amortized Efficiency: Insertions, deletions, and lookups operate in O(log n) time. In practice, Red-Black trees perform fewer rotations per insertion/deletion than stricter balancing structures like AVL trees, making them highly efficient for mixed workloads.
Historical Context
The original structure was invented in 1972 by Rudolf Bayer, who termed them "symmetric binary B-trees". The familiar Red-Black terminology and specific properties were later introduced by Leonidas J. Guibas and Robert Sedgewick in a 1978 paper. They used the red and black colors to map 2-3-4 trees (a type of B-tree) into standard binary trees for simpler representation in memory.
Real-world Applications
- System APIs: They form the underlying data structure for associative containers in standard libraries, such as C++'s
std::mapandstd::set, as well as Java'sTreeMapandTreeSet. - Linux Kernel: The Completely Fair Scheduler (CFS) in Linux uses a Red-Black tree to model and sort task execution timelines efficiently.
- Memory Management: Many memory allocators use Red-Black trees to keep track of unallocated contiguous blocks of memory.
Related Concepts
- AVL Trees — another self-balancing binary search tree that is more rigidly balanced
- B-Trees — a generalization of binary search trees allowing nodes with more than two children
- Tree Traversal — algorithms used to visit nodes in a structured order
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Red-Black Tree module.
Try Red-Black Tree on Riano →