A self-balancing binary search tree that colors each node red or black and enforces a small set of coloring rules to keep the tree approximately balanced, guaranteeing logarithmic-time search, insertion and deletion; the structure behind many standard library ordered maps and sets.
Facts
Origin YearBayer called the structure a symmetric binary B-tree in 1972; Leonidas Guibas and Robert Sedgewick derived the modern red-black tree from it and gave it its current name in a 1978 paper. Core PrincipleA self-balancing binary search tree in which each node carries an extra red or black color bit; insertions and deletions trigger recoloring and rotations that keep the tree approximately balanced, guaranteeing O(log n) search, insert and delete. 1 Connections
In Field
Invented
Rudolf Bayer invented the symmetric binary B-tree in 1972, the structure later renamed the red-black tree by Leo Guibas and Robert Sedgewick.
Sources
1. Wikipedia: Red-black tree
Wikimedia FoundationHistory section, first paragraph
In 1972, Rudolf Bayer invented a data structure that was a special order-4 case of a B-tree.
Lead section, first paragraph
The nodes in a red-black tree hold an extra "color" bit, often drawn as red and black, which help ensure that the tree is always approximately balanced.
View the Source Frequently Asked Questions
Why does a red-black tree store a color on every node?
The color bit helps keep the tree approximately balanced.
The nodes hold an extra color bit, often drawn as red and black, which helps ensure that the tree is always approximately balanced. The structure dates to 1972, when Rudolf Bayer invented it as a special order-4 case of a B-tree.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.