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 tree
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)
Méthodes Aléatoires et Déterministes pour les processus de COllision, coalescence, de Fragmentation; Funder: French National Research Agency (ANR); Code: ANR-08-BLAN-0220
Brunet, Ăric; Derrida, Bernard, 2011, A Branching Random Walk Seen From The Tip, Journal Of Statistical Physics, 143, 3, pp. 420-446, 10.1007/s10955-011-0185-z.
Chauvin, Brigitte; Clément, Julien; Gardy, Danièle, 2018, Arbres Binaires De Recherche, Arbres Pour l’Algorithmique, pp. 217-279, 10.1007/978-3-319-93725-0_6.
Corre, Pierre-Antoine, 2016, Oscillations In The Height Of The Yule Tree And Application To The Binary Search Tree, Random Structures And Algorithms, 51, 1, pp. 90-120, 10.1002/rsa.20701.
Dascaliuc, Radu; Michalowski, Nicholas; Thomann, Enrique; Waymire, Edward C., 2019, Complex Burgers Equation: A Probabilistic Perspective, Sojourns In Probability Theory And Statistical Physics - I, pp. 138-170, 10.1007/978-981-15-0294-1_6.