An analytic approach to the height of binary search trees II

Michael Drmota

Journal of the ACM · 2003 · 48 citations · 17 references

Concepts

Abstract

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.

References

17