(data structure)
Definition: A nearly-balanced tree that uses an extra bit per node to maintain balance. No leaf is more than twice as far from the root as any other.
Formal Definition: A red-black tree with n internal nodes has height at most 2log2(n+1).
Also known as symmetric binary B-tree.
Generalization (I am a kind of ...)
B-tree.
Specialization (... is a kind of me.)
AVL tree.
Aggregate child (... is a part of or used in me.)
left rotation, right rotation.
See also height-balanced tree.
Note: The extra bit "colors" the node red or black, hence the name. These were called "symmetric binary B-trees" when first invented. The red/black naming and explanation was given by Guibas and Sedgewick.
An AVL tree is at least as balanced as a red-black tree.
Author: PEB
Rudolf Bayer, Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms, Acta Informatica, 1:290-306, 1972.
Leo J. Guibas and Robert Sedgewick, A Dichromatic Framework for Balanced Trees, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pages 8-21. IEEE Computer Society, 1978.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 23 May 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "red-black tree", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 23 May 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/redblack.html
