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 treeArticle

Authors: Matthew Roberts 1

  • 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)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Branching random walk,Quicksort,Yule tree,Binary search tree,Random permutation model,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
Funding:
    Source : OpenAIRE Graph
  • 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

4 Documents citing this article

Consultation statistics

This page has been seen 174 times.
This article's PDF has been downloaded 271 times.