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).

exp(x) inequality [Solution]

The problem was to show that

$$e^x \ge 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$$

for all $x \ge 0$ and integer $n \ge 0$.

Solution

---

Let $f_{n}(x) = 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}$ with $f_{0}(x) = 1$

Now $e^x \ge f_{0}(x)$ for all $x \ge 0$

Now suppose $e^x \ge f_{n}(x)$ for all $x \ge 0$.

Let $h(x) = e^x - f_{n+1}(x)$

Now $h(0) = 0$.

We also have that the derivative of $h$, $h'(x) = e^x - f_n(x)$

By induction assumption $h'(x) \ge 0$ for all $x \ge 0$.

Thus $h$ is increasing and so $h(x) \ge h(0) = 0$ for all $x \ge 0$.

Thus by induction, we are done.

Generate a random red-black tree

Following up on two previous posts.

Given $n$, can you give an algorithm to generate a random red-black tree consisting of $n$ nodes? Each structurally unique tree should have an equal chance of being generated (we are not interested in the actual assignment of colors).

[Solution]