Derive expressions for C$($h$)$ and A$($h$)$ which generalize the total and average number of comparisons computed in Question $5$ to the case of a full binary search tree of any height h$.$

$[$Hint: This question is quite challenging! If your mathematics is strong, it is possible to write C$($h$)$ as the sum of the number of comparisons at each level, and then simplify that using the usual algebraic tricks for summing series. Or$,$ you may find it easier to proceed in the same way as in Lecture Notes Section $6\mathrm{.}5$ where an expression was derived for the tree size s$($h$),$ i$.$e$.$ the total number of nodes in a full binary tree of height h$.$ First think about how C$($h$+1)$ is related to C$($h$)$ by adding in the extra row h$+1,$ then think about how the height h$+1$ tree$’$s C$($h$+1)$ is related to its two sub$-$tree$’$s C$($h$),$ and finally combine the two equations you get for C$($h$+1)$ to give an equation for C$($h$).$ You can use the expression for s$($h$)$ from the Lecture Notes or Question $3.$ Whichever approach you use, show all the steps involved.$]$

What can you deduce about the average number of comparisons required, and hence the average time complexity of the search, for large trees? Provide only answers and calculation

Answer rating: 100% (QA)

To derive the expressions for Ch and Ah which represent the total and average number of comparisons in a full binary search tree of height h respectiv... View the full answer