Seonglae ChoThe depth of a node is the number of comparisons made during tree-insert.
Average node depth is based on Quick Sort analysis. But average node depth does not means expected height (because max node depth is tree height) so we need to prove it.
Height of a random binary search tree
prove process outline with Jensen’s Inequality
sum is always large than max when they are positive numbers
and guess
is convex function
