Generate a random red-black tree [Solution]

The problem was to generate a random structurally unique red-black tree on $n$ nodes.

Solution

---

Now if we knew exactly how many red-black trees of $n$ nodes have $L$ nodes in the left subtree, then we can generate them as follows.

Count the total number of trees with $n$ nodes. For each $L$ in $\{0,1,\dots,n\}$,  count the fraction $\alpha_L$ of them with $L$ left nodes in the left subtree.

Now generate a random number $L$ in $\{0,1,2,\dots, n\}$ with probability $\alpha_L$. This will be the number of children in the left subtree. The number of children in the right subtree is $n-1-L$. Recursively generate the subtrees now.

This works because the subtrees of a red-black tree are red-black trees themselves. On how to count, see this previous post on this blog on counting red-black trees (some modifications might be needed).