TOPICS
Search

Red-Black Tree


RedBlackTree

An extended rooted binary tree satisfying the following conditions:

1. Every node has two children, each colored either red or black.

2. Every tree leaf node is colored black.

3. Every red node has both of its children colored black.

4. Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.

Let n be the number of internal nodes of a red-black tree. Then the number of red-black trees for n=1, 2, ... is 2, 2, 3, 8, 14, 20, 35, 64, 122, ... (OEIS A001131). The number of trees with black roots and red roots are given by OEIS A001137 and OEIS A001138, respectively.

Let T_h be the generating function for the number of red-black trees of black-height h indexed by the number of tree leaves. Then

 T_(h+1)(x)=[T_h(x)]^2+[T_h(x)]^4,
(1)

where T_1(x)=x+x^2. If T(x) is the generating function for the number of red-black trees, then

 T(x)=x+x^2+T(x^2(1+x)^2)
(2)

(Ruskey). Let rb(n) be the number of red-black trees with n tree leaves, r(n) the number of red-rooted trees, and b(n) the number of black-rooted trees. All three of the quantities satisfy the recurrence relation

 R(n)=sum_(n/4<=n<=n/2)(2m; n-2m)R(m),
(3)

where (n; k) is a binomial coefficient, rb(1)=1, rb(2)=2 for R(n)=rb(n), r(1)=r(3)=0, r(2)=1 for R(n)=r(n), and b(1)=1 for R(n)=b(n) (Ruskey).


See also

B-Tree, Rooted Tree

Explore with Wolfram|Alpha

References

Bayer, R. "Symmetric Binary B-Trees: Data Structures and Maintenance Algorithms." Acta Informat. 1, 290-306, 1972.Binstock, A.; and Rex, J. Practical Algorithms for Programmers. Reading, MA: Addison-Wesley, 1995.Cormen, T.; Leiserson, C.; and Rivest, R. Introduction to Algorithms. Cambridge MA: MIT Press, 1990.Guibas, L. and Sedgewick, R. "A Dichromatic Framework for Balanced Trees." In Proc. 19th IEEE Symp. Foundations of Computer Science, pp. 8-21, 1978.Rivest, R. L.; Leiserson, C. E.; and Cormen, R. H. Introduction to Algorithms. New York: McGraw-Hill, 1990.Ruskey, F. "Information on Red-Black Trees." http://www.theory.csc.uvic.ca/~cos/inf/tree/RedBlackTree.html.Skiena, S. S. The Algorithm Design Manual. New York: Springer-Verlag, pp. 177 and 179, 1997.Sloane, N. J. A. Sequences A001131, A001137, and A001138 in "The On-Line Encyclopedia of Integer Sequences."Wood, D. Data Structures, Algorithms, and Performance. Reading, MA: Addison-Wesley, 1993.

Referenced on Wolfram|Alpha

Red-Black Tree

Cite this as:

Weisstein, Eric W. "Red-Black Tree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Red-BlackTree.html

Subject classifications