Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Almost sure asymptot ...
Conference paper

Almost sure asymptotics for the random binary search tree

Matthew Roberts (1)
(1) Laboratoire de Probabilités et Modèles Aléatoires
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Proceedings
DOI
10.46298/dmtcs.2775
License
https://about.hal.science/hal-authorisation-v1
French National Research Agency (ANR)
ANR-08-BLAN-0220
Indicators
548
Views
862
Downloads

Almost sure asymptotics for the random binary search tree

Matthew Roberts (1)
(1) Laboratoire de Probabilités et Modèles Aléatoires
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.
Keywords
  • [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]
  • Binary search tree
  • Random permutation model
  • Yule tree
  • Quicksort
  • Branching random walk
Cited by

Source: OpenCitations

  • Arbres binaires de recherche

    Mathématiques et applications

    Authors : Brigitte Chauvin, Julien Clément ORCID, Danièle Gardy ORCID

    Journal reference : Volume , 2018, pp. 217-279

    DOI : 10.1007/978-3-319-93725-0_6

  • Complex Burgers Equation: A Probabilistic Perspective

    Springer proceedings in mathematics & statistics

    Authors : Radu Dascaliuc ORCID, Nicholas Michalowski, Enrique Thomann ORCID, Edward C. Waymire

    Journal reference : Volume , 2019, pp. 138-170

    DOI : 10.1007/978-981-15-0294-1_6

  • Oscillations in the height of the Yule tree and application to the binary search tree

    arXiv (Cornell University)

    Authors : Pierre-Antoine Corre

    Journal reference : Volume 51, 2016, pp. 90-120

    DOI : 10.1002/rsa.20701

  • A Branching Random Walk Seen from the Tip

    arXiv (Cornell University)

    Authors : Éric Brunet ORCID, Bernard Derrida ORCID

    Journal reference : Volume 143, 2011, pp. 420-446

    DOI : 10.1007/s10955-011-0185-z
Preview
Loading PDF preview...