On the silhouette of binary search trees
From MaRDI portal
Publication:983879
DOI10.1214/08-AAP593zbMath1203.60040arXiv0910.3825MaRDI QIDQ983879
Publication date: 13 July 2010
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0910.3825
functional limit theorems; convergence in distribution; analysis of algorithms; contraction method; external path length
68W40: Analysis of algorithms
05C05: Trees
05C80: Random graphs (graph-theoretic aspects)
60F17: Functional limit theorems; invariance principles
Related Items
Partial match queries in random quadtrees, A limit process for partial match queries in random quadtrees and 2-d trees, Process convergence for the complexity of radix selection on Markov sources, On weighted depths in random binary search trees, Search trees: metric aspects and strong limit theorems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Asymptotical growth of a class of random trees
- Perfect simulation from the quicksort limit distribution
- The contraction method for recursive algorithms
- The profile of binary search trees
- Renewals for exponentially increasing lifetimes, with an application to digital search trees
- Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
- Paths in a random digital tree: limiting distributions
- A limiting distribution for quicksort
- A note on the height of binary search trees
- Foundations of Modern Probability
- A note concerning the limit distribution of the quicksort algorithm
- Building uniformly random subtrees
- Asymptotic distribution theory for Hoare's selection algorithm
- A limit theorem for “quicksort”