Branching processes in the analysis of the heights of trees

DOI10.1007/BF00265991zbMATH Open0643.60065OpenAlexW2008048984MaRDI QIDQ1102045FDOQ1102045

Authors: Luc Devroye 

Publication date: 1987

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00265991

Recommendations

• An analytic approach to the height of binary search trees
• On the height of random m‐ary search trees
• A note on the height of binary search trees
• Note on the heights of random recursive trees and random m‐ary search trees
• On the Variance of the Height of Random Binary Search Trees

zbMATH Keywords

branching processesheight of random treesbinary search treesquadtreesunion-find trees

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Limit theorems in probability theory (60F99) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cited In (60)

• The longest minimum-weight path in a complete graph
• On random cartesian trees
• Retracted: Strong limiting behavior in binary search trees
• The shape of random pattern-avoiding permutations
• Long and short paths in uniform random recursive dags
• The height of increasing trees
• Applications of the theory of records in the study of random trees
• A functional limit theorem for the profile of random recursive trees
• Depth properties of scaled attachment random recursive trees
• Weighted height of random trees
• Geometry of weighted recursive and affine preferential attachment trees
• The variance of the height of binary search trees
• Analytic variations on quadtrees
• On Robson's convergence and boundedness conjectures concerning the height of binary search trees
• A phase transition for the heights of a fragmentation tree
• \(D\cdot E\cdot K=(100)_8\)
• Note on the heights of random recursive trees and random m‐ary search trees
• Weak convergence of the number of vertices at intermediate levels of random recursive trees
• Probabilistic analysis of bucket recursive trees
• A limit process for partial match queries in random quadtrees and 2-d trees
• The profile of binary search trees
• The strong convergence of maximal degrees in uniform random recursive trees and dags
• A functional limit theorem for the profile of \(b\)-ary trees
• Oscillations in the height of the Yule tree and application to the binary search tree
• High degrees in recursive trees
• The height of a binary search tree: the limiting distribution perspective.
• Analytic methods in asymptotic enumeration
• Limiting theorems for the nodes in binary search trees
• Height-analysis of k-dimensional leaf and node height-balanced trees: A new approach
• A limit field for orthogonal range searches in two-dimensional random point search trees
• Finding Adam in random growing trees
• A non-increasing tree growth process for recursive trees and applications
• Martingales and large deviations for binary search trees
• EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES
• Search problems in groups and branching processes.
• Poisson-Dirichlet branching random walks
• On the internal path length ofd-dimensional quad trees
• The height of a random binary search tree
• Limit distribution for the maximum degree of a random recursive tree
• The height of random k‐trees and related branching processes
• Hypergeometrics and the cost structure of quadtrees
• Correction terms for the height of weighted recursive trees
• On the height of random m‐ary search trees
• General Edgeworth expansions with applications to profiles of random trees
• On the concentration of the height of binary search trees
• Analytic analysis of algorithms
• On the expected height of fringe-blanced trees
• A note on the growth of random trees
• Bounded branching process and and/or tree evaluation
• Diameter of the stochastic mean-field model of distance
• Limit laws for local counters in random binary search trees
• Two Applications of Urn Processes The Fringe Analysis of Search Trees and The Simulation of Quasi-Stationary Distributions of Markov Chains
• Critical random graphs and the structure of a minimum spanning tree
• Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes
• Transversals in trees
• Combinatorial differential operators in: Faà di Bruno formula, enumeration of ballot paths, enriched rooted trees and increasing rooted trees
• Zip-zip trees: making zip trees more balanced, biased, compact, or persistent
• Community modulated recursive trees and population dependent branching processes
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Random trees have height \(O(\sqrt{n})\)

This page was built for publication: Branching processes in the analysis of the heights of trees

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