Skip to Main content Skip to Navigation
Conference papers

Almost sure asymptotics for the random binary search tree

Abstract : We consider a (random permutation model) binary search tree with $n$ nodes and give asymptotics on the $\log$ $\log$ scale for the height $H_n$ and saturation level $h_n$ of the tree as $n \to \infty$, both almost surely and in probability. We then consider the number $F_n$ of particles at level $H_n$ at time $n$, and show that $F_n$ is unbounded almost surely.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 4:32:32 PM
Last modification on : Monday, December 14, 2020 - 9:41:57 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:53:16 AM


Publisher files allowed on an open archive


  • HAL Id : hal-00459166, version 1


Matthew Roberts. Almost sure asymptotics for the random binary search tree. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.565-576. ⟨hal-00459166⟩



Record views


Files downloads