Red-Black Tree

An extended Binary Tree satisfying the following conditions:

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

2. Every Leaf node is colored black.

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

4. Every path from the Root to a 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, ... (Sloane's A001131). The number of trees with black roots and red roots are given by Sloane's A001137 and Sloane's 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 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 ${\it rb}(n)$ be the number of red-black trees with $n$ 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\leq n\leq n/2} {2m\choose n-2m}R(m),$$ (3)

where ${n\choose k}$ is a Binomial Coefficient, ${\it rb}(1)=1$, ${\it rb}(2)=2$ for $R(n)={\it 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

References

Beyer, R. ``Symmetric Binary $B$-Trees: Data Structures and Maintenance Algorithms.'' Acta Informat. 1, 290-306, 1972.

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://sue.csc.uvic.ca/~cos/inf/tree/RedBlackTree.html.

Sloane, N. J. A. Sequences A001131, A001137, and A001138 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.