In class, the professor showed that using a uniform random permutation $$ X_1,…, X_n$$ (each being i.i.d.) we can construct a Binary Search Tree by inserting the values in to the tree by their indices. That is fairly straightforward. We can right it as pairs:
$$ {(X_1, 1), .., (X_n, n)} $$
We can now define the inverse permutation as:
$$ {(1, Y_1), .., (n, Y_n)} $$
I understand it as given as a pair with the Global Rank of some node and a random variable representing the time that this node is inserted. I understand how this shows that any two consecutive values
$$ {(i, Y_i), (i+1, Y_{i+1})} $$
are in an ancestor-descendant relationship. This means that i is a leaf if
$$ Y_i = max(Y_{i-1}, Y_i, Y_{i+1}) $$
Thus, apart from rank 1 and rank n, the probability that any node is a leaf is 1/3 and 1/2 otherwise. This yields the expected number of leaves to be:
$$ E_{\# leaves} = \frac{1}{2} + \sum_{i=2}^{n-1}{1/3} + \frac{1}{2} = \frac{n+1}{3}$$
Ok, I'm good to this point. But then he makes a statement that the expected number of nodes with two children are one less then the above, that is they are
$$ \frac{n-2}{3} $$ This would make the expected number of nodes with only one child: $$ \frac{n+1}{3} $$
I do not understand why the expected number of nodes with two children is one less then the expected number of leaves?
Best Answer
The property holds for the binary tree with one node (which has 0 node with two children and 1 leave) and, each time one adds two children to a leave of a binary tree such that the property holds, it still holds for the larger tree (which has 1 more leave and 1 more node with two children), QED.