On the silhouette of binary search trees

DOI10.1214/08-AAP593zbMATH Open1203.60040arXiv0910.3825OpenAlexW3102180173MaRDI QIDQ983879FDOQ983879

Authors: Rudolf Grübel 

Publication date: 13 July 2010

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0910.3825

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

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)

Cites Work

• Title not available (Why is that?)
• Foundations of Modern Probability
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• The contraction method for recursive algorithms
• The profile of binary search trees
• Title not available (Why is that?)
• Asymptotic distribution theory for Hoare's selection algorithm
• A limit theorem for “quicksort”
• 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: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
• A note on the height of binary search trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Building uniformly random subtrees
• Title not available (Why is that?)
• Title not available (Why is that?)
• A limiting distribution for quicksort
• Title not available (Why is that?)
• Perfect simulation from the quicksort limit distribution
• A survey of multivariate aspects of the contraction method
• Asymptotical growth of a class of random trees
• Paths in a random digital tree: limiting distributions
• Title not available (Why is that?)
• Renewals for exponentially increasing lifetimes, with an application to digital search trees
• A note concerning the limit distribution of the quicksort algorithm
• A hooray for Poisson approximation

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)