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

A redblack tree is a type of selfbalancing 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 Btree", but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick.^{[2]} It is complex, but has good worstcase 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 redblack tree is a binary search tree which inserts and removes intelligently, to ensure the tree is reasonably balanced.
Contents
Terminology
A redblack 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 redblack 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 redblack 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.
Redblack trees, like all binary search trees, allow efficient inorder traversal in the fashion, LeftRootRight, of their elements. The searchtime 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 
Padic 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 Online 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) 
