Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$). What is the number of comparisons that will occur in the worst case scenario, if we ask whether $k\in V(T)$ and why does it arise?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Understandable justification - don't expect us to solve your exercise for you. This won't help you understand the material. $\endgroup$– Yuval FilmusCommented Jun 14, 2013 at 5:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Hint: If the tree has height $h$ then the worst number of comparisons is ...? If the tree is "equilibrated by height" (I guess balanced) and has $n$ nodes then its height is ...?
answered Jun 14, 2013 at 5:43
$\begingroup$
$\endgroup$
A balanced tree of height 0 has one node. A balanced tree of height 1 has three nodes. A balanced tree of height 2 has seven nodes. A balanced tree of height $h$ has $2^{h+1}-1$ nodes. Looks familiar?
