Red-black tree

related topics
{math, number, function}
{black, white, people}
{woman, child, man}
{@card@, make, design}
{style, bgcolor, rowspan}
{line, north, south}

A red-black tree is a type of self-balancing binary search tree, a data structure used in computing science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer[1] and named "symmetric binary B-tree", but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick.[2] It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is total number of elements in the tree. Put very simply, a red-black tree is a binary search tree which inserts and removes intelligently, to ensure the tree is reasonably balanced.

Contents

Terminology

A red-black tree is a special type of binary tree, used in computer science to organize pieces of comparable data, such as text fragments or numbers.

The leaf nodes of red-black trees do not contain data. These leaves need not be explicit in computer memory — a null child pointer can encode the fact that this child is a leaf — but it simplifies some algorithms for operating on red-black trees if the leaves really are explicit nodes. To save memory, sometimes a single sentinel node performs the role of all leaf nodes; all references from internal nodes to leaf nodes then point to the sentinel node.

Red-black trees, like all binary search trees, allow efficient in-order traversal in the fashion, Left-Root-Right, of their elements. The search-time results from the traversal from root to leaf, and therefore a balanced tree, having the least possible tree height, results in O(log n) search time.

Full article ▸

related documents
Banach–Tarski paradox
Formal power series
Lebesgue integration
Big O notation
Lambda calculus
P-adic number
Determinant
Linear programming
Combinatory logic
Relational model
Travelling salesman problem
Prolog
Binomial coefficient
Discrete cosine transform
Grothendieck topology
System of linear equations
Laplace transform
Pythagorean triple
Wikipedia:Free On-line Dictionary of Computing/R - S
Quadratic reciprocity
Original proof of Gödel's completeness theorem
Spinor
Μ-recursive function
Group theory
Riemann integral
Lie group
Fibonacci number
Combinatorics
Trigonometric functions
Class (computer science)