## Information on Red-black Trees

From a combinatorial point of view, a red-black tree is an extended binary tree (every node has two children or is a leaf) which satisfies the following properties.
• Every node is colored either red or black.
• Every leaf node is colored black.
• If a node is red, then both of its children are black.
• Every path from the root to a leaf contains the same number of black nodes. This number is called the black-height of the tree.

We classify red-black trees according to n, the number of internal nodes. In the figure, n = 6. Among all red-black trees of height 4, this is one with the minimum number of nodes. A red-black tree with n nodes has height O(lg n).

Red-black trees are an important data structure but their combinatorial properties are not much studied. They were introduced by R. Bayer ("Symmetric binary B-trees: Data structures and maintenance algorithms", Acta Informatica, 1 (1972) 290-306). A nice discussion of their properties as data structures may be found in the book Introduction to Algorithms by Cormen, Leiserson, and Rivest, McGraw-Hill, 2nd Ed., 2001.

We represent red-black trees by traversing the tree in preorder, recording the color of each node and whether it is a leaf or an internal node. For string output we record a 1 for a black internal node, 2 for a red (internal) node, and a 0 for a (black) leaf. For example, the tree above is encoded as 1 1 0 0 2 1 2 0 0 0 1 0 0 as a string (standard output) and as as a sequence of nodes (alternate output).

There is an interesting connection between red-black trees and B-trees of order 4. The following image shows the correspondence between nodes of degree 2, 3, and 4, in a 2-3-4 tree and subtrees of a corresponding red-black tree. Since there are 2 possibilities for nodes of degree 3 in the 2-3-4 tree, there are 2k corresponding red-black trees, where k is the number of nodes of degree 3 in the 2-3-4 tree.

For the B-tree shown here on the B-tree information page, there are 24 = 16 corresponding red-black trees. The image comes from T. Ball, D. Hoffman, F. Ruskey, R. Webber, and L. White, State Generation and Automated Class Testing, Software Testing, Verification and Reliability, Volume 10, Issue 3, September 2000, pages 149-170.

The algorithm used is based on the algorithm for generating B-trees. It was developed by Richard Webber, who kindly supplied us with his code.

The number of red-black trees for n=1,2,...,31 is 2, 2, 3, 8, 14, 20, 35, 64, 122, 260, 586, 1296, 2708, 5400, 10468, 19888, 37580, 71960, 140612, 279264, 560544, 1133760, 2310316, 4750368, 9876264, 20788880, 44282696, 95241664, 206150208, 447470464. This is sequence A001131 in Neil J. Sloane's database of integer sequences. Of these, the number that have black roots is 1, 2, 2, 4, 8, 16, 33, 56, 90, 164, 330, 688, 1440, 3008, 6291, (sequence A001137 in Neil J. Sloane's database of integer sequences. ) and the number that have red roots is 1, 0, 1, 4, 6, 4, 2, 8, 32, 96, 256, 608, 1268, 2392, 4177 (sequence A001138(M0564) in Neil J. Sloane's database of integer sequences. ).

The following generating function and recurrence relation were derived for us by John Moon. If Th(x) is the ordinary generating function of the number of red-black trees of black-height h, classified by the number of leaves, then T1(x) = x + x2 and for h > 0,

Th+1(x) = [Th(x)]2 + [Th(x)]4.

If T(x) is the ordinary generating function of the number of red-black trees, then

T(x) = x + x2 + T(x2(1+x)2).

If rb(n) is the number of red-black trees with n leaves then rb(1) = 1, rb(2) = 2, and for n > 2,
rb(n)   =
 __ \ / n/4
(
2m
n-2m
) rb(m).
The number of red-rooted and black-rooted trees satisfies the same recurrence relation, but the initial conditions are different. For red-rooted trees, r(1) = r(3) = 0, and r(2) = 1. For black-rooted trees, b(1) = 1.

Programs available:

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Tuesday, 24-May-2011 10:59:02 PDT.