On the silhouette of binary search trees

DOI10.1214/08-AAP593zbMath1203.60040arXiv0910.3825MaRDI QIDQ983879

Rudolf Grübel

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

zbMATH Keywords

functional limit theorems; convergence in distribution; analysis of algorithms; contraction method; external path length

Mathematics Subject Classification ID

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”