Journal of the ACM · 2003 · 48 citations · 17 references
Natural SciencesComputer ScienceMathematicsAlgorithmsData StructuresDynamical SystemsLaw Of Large NumbersTree Height EstimationBinary Search TreesDifferential Equation FormulationSaturation
It is shown that all centralized absolute moments E | H n − E H n | α (α ≥ 0) of the height H n of binary search trees of size n and of the saturation level H n ′ are bounded. The methods used rely on the analysis of a retarded differential equation of the form Φ′( u ) = −α −2 Φ( u /α) 2 with α > 1. The method can also be extended to prove the same result for the height of m -ary search trees. Finally the limiting behaviour of the distribution of the height of binary search trees is precisely determined.
17
A note on the height of binary search trees
Luc Devroye · Journal of the ACM · 1986 · 234 citations · Full text
Branching processes in the analysis of the heights of trees
Luc Devroye · Acta Informatica · 1987 · 144 citations