1
$\begingroup$

Suppose search $n$ times in a given binary search tree $T$ with $n$ nodes. each searching have cost $C_i$, and $\sum_{i=1}^{n}C_i=O(n\log n)$. Now the problem is to find height of $T$. I think it be $O(\sqrt{n\log n})$, but after reading this post, what is correct proof to get that result?

$\endgroup$
1
  • $\begingroup$ The other post ask for the upper boundary of a tree's height, which is in his case not $O(\log(n))$ (considering a tree with only left/right branches). Your problem is different, it already gives you the information of the upper boundary of cost for searching every node together, which is $O(n \log n)$, what would be then the upper boundary of cost for searching one single node? And given the upper boundary cost of searching one single node, what would be the upper boundary for tree's height? $\endgroup$ Mar 19, 2021 at 13:12

1 Answer 1

1
$\begingroup$

Let $h$ be longest path from root $T$ to leaves. We must read $h+1$ nodes. So searching for root of $T$ we have cost $1$, for child of root we have cost $2$ , and etc. it's sufficient to sum over cost at each nodes on $h$. As a result we have

\begin{gather*} 1+2+3...+h=O(h^2). \end{gather*}

Now as mentioned in question, $O(h^2)$ must be $O(n\log n)$. More formally, $O(h^2)=O(n\log n)$ that we can conclude that $h=O(\sqrt{n\log n})$.

For example consider a binary search tree with $n$ nodes such that root have sub tree with height $\sqrt{n\log n}$, and right sub tree of root have height $\log (n-\sqrt{n\log n}).$

$\endgroup$

Your Answer

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