Is randomly building a BST different from random sampling whole trees?

Question

What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution

Answer 1

You want to distinguish

randomly built binary search tree

from

choosing a binary search tree from a random distribution.

Let me first tell you why this is not a well-posed query. Neither version is completely specified; the first misses the process by which the tree is built as well as the used random source, the second lacks a specification of the distribution to be used. In particular, the "randomly built" trees are "chosen from a random distribution"!

Now I'll assume that you (or your teacher) made the "usual" assumptions and reformulate the models.

1. Starting with the empty tree, we insert keys $s_1, \dots, s_n \in [1..n]$ successively (with BST insertion). The sequence is chosen uniformly at random from all permutations of $[1..n]$.

   This is the famous random permutation model.

2. Pick a tree uniformly at random from all BSTs with keys $[1..n]$.

There are several ways to see that the two models define different random distributions.

1. There are $n!$ different permutations but only $C_n = \frac{1}{n+1} \cdot \binom{2n}{n}$ BSTs. Show that it is not possible to distribute the permutations evenly, i.e. $C_n$ does not (always) divide $n!$.

   In particular, for $n=3$ we have six permutations but five BSTs.

2. For $n=3$, enumerate all trees and notice that four trees result from one permutation each while the fifth results from two. Ergo, the random permutation model is not uniform.

3. Know (from earlier studies) that BSTs have average height $\Theta(\log n)$ in the random permutation model but $\Theta(\sqrt{n})$ in the uniform model.

   The first is a standard result found in most textbooks on the matter. The latter, admittedly, a less known result by Flajolet and Odlyzko [1]; the method of analysis has broader relevance and the result generalises to many families of trees.

---

1. The average height of binary trees and other simple trees by P. Flajolet and A. Odlyzko (1982)

Answer 2

Randomly built binary search tree : When binary tree is built by picking n keys one by one randomly from a set of keys.

While binary search tree from a random distribution mean there are all possible ways of binary tree with n keys from a set of keys . and you are picking directly one of the tree.

Only way of making a random binary tree is different.

Randomly built binary search tree will be more efficient to make than the later one.

but both will result in estimated search time of O(log n)