Red-Black Tree

A red-black tree is a rooted extended binary tree satisfying the following conditions:

1. Every internal 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 graph path from the root vertex to a tree leaf contains the same number (the "black-height") of black nodes.

The root vertex may be red or black, and left and right children are distinguished.

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

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

(1)

where . If is the generating function for the number of red-black trees, then

(2)

(Ruskey). Let be the number of red-black trees with tree leaves, the number of red-rooted trees, and the number of black-rooted trees. For , all three quantities satisfy the recurrence relation

(3)

where is a binomial coefficient, , for , , for , and for (Ruskey).