The height of a random binary search tree
- 1 May 2003
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 50 (3) , 306-332
- https://doi.org/10.1145/765568.765571
Abstract
LetHnbe the height of a random binary search tree onnnodes. We show that there exist constants α = 4.311… and β = 1.953… such thatE(Hn) = αln n− βln ln n+O(1), We also show thatVar(Hn) =O(1).Keywords
This publication has 10 references indexed in Scilit:
- An analytic approach to the height of binary search trees IIJournal of the ACM, 2003
- On the Variance of the Height of Random Binary Search TreesSIAM Journal on Computing, 1995
- Note on the heights of random recursive trees and random m‐ary search treesRandom Structures & Algorithms, 1994
- 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 growing random binary treesJournal of Mathematical Analysis and Applications, 1984
- On the Most Probable Shape of a Search Tree Grown from a Random PermutationSIAM Journal on Algebraic Discrete Methods, 1984
- SpacingsJournal of the Royal Statistical Society Series B: Statistical Methodology, 1965
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952