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).
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).
No comments:
Post a Comment