An analytic approach to the height of binary search trees II
- 1 May 2003
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 50 (3) , 333-374
- https://doi.org/10.1145/765568.765572
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.Keywords
This publication has 12 references indexed in Scilit:
- The Variance of the height of binary search treesTheoretical Computer Science, 2002
- An analytic approach to the height of binary search treesAlgorithmica, 2001
- How Fast Does a General Branching Random Walk Spread?Published by Springer Nature ,1997
- On the Variance of the Height of Random Binary Search TreesSIAM Journal on Computing, 1995
- On the height of randomm‐ary search treesRandom Structures & Algorithms, 1990
- Branching processes in the analysis of the heights of treesActa Informatica, 1987
- A note on the height of binary search treesJournal of the ACM, 1986
- On the average internal path length of m-ary search treesActa Informatica, 1986
- On growing random binary treesJournal of Mathematical Analysis and Applications, 1984
- Theorie und Anwendung der Laplace-TransformationPublished by Springer Nature ,1937