0
$\begingroup$

Let $H(n)$ be the average height of a BST with nodes from ${1,...,n}$. I think that $$H(n) = \frac{1}{n}\sum_{i = 0}^{n-1}\left[\text{max}(H(i), H(n-1 -i)) + 1\right]$$ But I don't know how to prove this is correct. Can anyone help me or explain why this is incorrect?

Note proving it directly seems hard because you end up with E[max(X, Y)] where X is height of left subtree and Y height of right subtree. I'm not really sure how to deal with this if we're looking for an exact recursion, not just a bound.

$\endgroup$
3
  • $\begingroup$ Please see the following to find the average height of a BST. Average Height of BST $\endgroup$ Feb 5 at 9:42
  • $\begingroup$ @SubhankarGhosal this only gives an upper bound, not an exact formula, which is asked by OP. $\endgroup$
    – Nathaniel
    Feb 5 at 9:44
  • $\begingroup$ @Nathaniel calculating exact expression is not easy so far known. $\endgroup$ Feb 5 at 9:46

2 Answers 2

2
$\begingroup$

The formula is wrong.

Indeed, we can find by hand that $H(1) = 0$, $H(2) = 1$ and $H(3) = \frac95$ ($5$ different trees, $4$ of them being of height $2$, the last of height $1$).

But: $$\frac13\sum\limits_{i=0}^2(\max(H(i), H(2 - 1 - i)) + 1) = \frac13(H(2) + H(1) + H(2) + 3) = \frac53\neq\frac95$$

The reason is that in your formula, you do not weigh each $H(i)$ by the number of trees of size $i$.

$\endgroup$
0
$\begingroup$

In addition to the upper bound in https://cs.stackexchange.com/a/96451/12322

Lower bound

$\displaystyle E(Y_n)= \frac{2}{n} \sum^n_{i=0}(E[2\max(Y_{i−1},Y_{n−i})] + 1) \geq \frac{2}{n} \sum^{n-1}_{i=0} E[Y_{i}]$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.