On the silhouette of binary search trees

DOI10.1214/08-AAP593zbMath1203.60040arXiv0910.3825OpenAlexW3102180173MaRDI 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 theoremsconvergence in distributionanalysis of algorithmscontraction methodexternal path length

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Functional limit theorems; invariance principles (60F17)

Related Items (5)

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 ⋮ Search trees: metric aspects and strong limit theorems ⋮ On weighted depths in random binary search trees ⋮ Partial match queries in random quadtrees

Cites Work

• 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”
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the silhouette of binary search trees