On the silhouette of binary search trees

DOI10.1214/08-AAP593MaRDI QIDQ983879zbMATH OpenOpenAlexFDO

Authors 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

analysis of algorithmsfunctional limit theoremsconvergence in distributioncontraction methodexternal path length

Mathematics Subject Classification ID

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

Abstract: A zero-one sequence describes a path through a rooted directed binary tree $T$; it also encodes a real number in $[0,1]$. We regard the level of the external node of $T$ along the path as a function on the unit interval, the silhouette of $T$. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.

Recommendations

• Search trees: metric aspects and strong limit theorems
• The profile of binary search trees
• Limit laws for local counters in random binary search trees
• Random binary trees: from the average case analysis to the asymptotics of distributions
• On the Contour of Random Trees

Cites work

• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1344715 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1064788 (Why is no real title available?)
• scientific article; zbMATH DE number 1552325 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 975592 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A hooray for Poisson approximation
• A limit theorem for “quicksort”
• A limiting distribution for quicksort
• A note concerning the limit distribution of the quicksort algorithm
• A note on the height of binary search trees
• A survey of multivariate aspects of the contraction method
• Asymptotic distribution theory for Hoare's selection algorithm
• Asymptotical growth of a class of random trees
• Building uniformly random subtrees
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Foundations of Modern Probability
• Paths in a random digital tree: limiting distributions
• Perfect simulation from the quicksort limit distribution
• Renewals for exponentially increasing lifetimes, with an application to digital search trees
• The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Genera
• The contraction method for recursive algorithms
• The profile of binary search trees

Cited in

(6)

• Partial match queries in random quadtrees
• A limit process for partial match queries in random quadtrees and 2-d trees
• On weighted depths in random binary search trees
• The density of the ISE and local limit laws for embedded trees
• Process convergence for the complexity of radix selection on Markov sources
• Search trees: metric aspects and strong limit theorems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q983879)