Matthew Roberts
-
Almost sure asymptotics for the random binary search tree
dmtcs:2775 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
-
https://doi.org/10.46298/dmtcs.2775
Almost sure asymptotics for the random binary search treeConference paper
Authors: Matthew Roberts 1
NULL
Matthew Roberts
1 Laboratoire de Probabilités et Modèles Aléatoires
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.
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Funder: French National Research Agency (ANR); Code: ANR-08-BLAN-0220
Bibliographic References
4 Documents citing this article
Radu Dascaliuc;Nicholas Michalowski;Enrique Thomann;Edward C. Waymire, Springer proceedings in mathematics & statistics, Complex Burgers Equation: A Probabilistic Perspective, pp. 138-170, 2019, 10.1007/978-981-15-0294-1_6.
Brigitte Chauvin;Julien Clément;Danièle Gardy, Mathématiques et applications, Arbres binaires de recherche, pp. 217-279, 2018, 10.1007/978-3-319-93725-0_6.
Pierre-Antoine Corre, 2016, Oscillations in the height of the Yule tree and application to the binary search tree, arXiv (Cornell University), 51, 1, pp. 90-120, 10.1002/rsa.20701, https://arxiv.org/abs/1411.4270.