Universal Limit Laws for Depths in Random Trees

DOI10.1137/S0097539795283954zbMATH Open0915.68089OpenAlexW2022718961MaRDI QIDQ4210155FDOQ4210155

Authors: Luc 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

Recommendations

• Limit laws for local counters in random binary search trees
• Novel characteristics of split trees by use of renewal theory
• Search trees: metric aspects and strong limit theorems
• Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
• Applications of the theory of records in the study of random trees

zbMATH Keywords

data structuresexpected time analysislaw of large numbersrandom treebinary search treedepth of a node

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (41)

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

This page was built for publication: Universal Limit Laws for Depths in Random Trees

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