Universal Limit Laws for Depths in Random Trees

DOI10.1137/S0097539795283954zbMath0915.68089OpenAlexW2022718961MaRDI QIDQ4210155

Luc P. Devroye

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795283954

zbMATH Keywords

law of large numbersdata structuresexpected time analysisbinary search treerandom treedepth of a node

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Data structures (68P05)

Related Items (39)

Distribution of distances in random binary search trees. ⋮ Tree limits and limits of random trees ⋮ Inversions in split trees and conditional Galton--Watson trees ⋮ Tree evolution processes for bucket increasing trees ⋮ Node profiles of symmetric digital search trees: Concentration properties ⋮ Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates ⋮ The asymptotic distribution of cluster sizes for supercritical percolation on random split trees ⋮ \(k\)-cut on paths and some trees ⋮ Random matrices and random graphs ⋮ Long and short paths in uniform random recursive dags ⋮ On densities for solutions to stochastic fixed point equations ⋮ Heavy subtrees of Galton-Watson trees with an application to Apollonian networks ⋮ The \(k\)-cut model in deterministic and random trees ⋮ A weakly 1-stable distribution for the number of random records and cuttings in split trees ⋮ Weighted height of random trees ⋮ The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees ⋮ The size of random fragmentation trees ⋮ Embedding small digraphs and permutations in binary trees and split trees ⋮ The total path length of split trees ⋮ Transversals in Trees ⋮ The fluctuations of the giant cluster for percolation on random split trees ⋮ On martingale tail sums for the path length in random trees ⋮ Phase changes in randomm-ary search trees and generalized quicksort ⋮ On a multivariate contraction method for random recursive structures with applications to Quicksort ⋮ Minima in branching random walks ⋮ A probabilistic analysis of some tree algorithms ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees ⋮ Dependence between path-length and size in random digital trees ⋮ Width and mode of the profile for some random trees of logarithmic height ⋮ On the internal path length ofd-dimensional quad trees ⋮ Embedding small digraphs and permutations in binary trees and split trees ⋮ Random Recursive Trees and Preferential Attachment Trees are Random Split Trees ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey ⋮ A phase transition for the heights of a fragmentation tree ⋮ Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees ⋮ The Wiener Index of Random Digital Trees ⋮ Recognising the last record of sequence ⋮ On binary search tree recursions with monomials as toll functions

Cites Work

• Some inequalities relating to the partial sum of binomial probabilities
• On growing random binary trees
• Generalized hypergeometric, digamma and trigamma distributions
• Generating random vectors uniformly distributed inside and on the surface of different regions
• The average height of binary trees and other simple trees
• Postulates for subadditive processes
• Subadditive ergodic theory
• Quad trees: A data structure for retrieval by composite keys
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
• An Analysis of Randomd-Dimensional Quad Trees
• The analysis of a fringe heuristic for binary search trees
• Paths in a random digital tree: limiting distributions
• Digital Search Trees Revisited
• Exact and asymptotic distributions in digital and binary search trees
• A linear algorithm for computing the visibility polygon from a point
• A note on the height of binary search trees
• The first- and last-birth problems for a multitype age-dependent branching process
• Locally balanced binary trees
• Chernoff's theorem in the branching random walk
• Note on the heights of random recursive trees and random m‐ary search trees
• Bounds on Moments of Certain Random Variables
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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: Universal Limit Laws for Depths in Random Trees