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 2^{k} 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 2^{4} = 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 T_{h}(x) is the ordinary generating function of the number of red-black trees of black-height h, classified by the number of leaves, then T_{1}(x) = x + x^{2} and for h > 0,
If T(x) is the ordinary generating function of the number of red-black trees, then
rb(n) | = |
| ( | n-2m | ) | rb(m). |