On the height of random m‐ary search trees

DOI10.1002/RSA.3240010206MaRDI QIDQ3977075zbMATHOpenAlexFDO

Authors Luc Devroye

Publication date 25 June 1992

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240010206

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50)

Recommendations

• Note on the heights of random recursive trees and random m‐ary search trees
• A note on the height of binary search trees
• Branching processes in the analysis of the heights of trees
• An analytic approach to the height of binary search trees. II
• An analytic approach to the height of binary search trees

Cites work

• scientific article; zbMATH DE number 4041254 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• Branching processes in the analysis of the heights of trees
• More Combinatorial Properties of Certain Trees

Cited in

(33)

• Transfer theorems and asymptotic distributional results for m‐ary search trees
• Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study
• Random-tree diameter and the diameter-constrained MST
• On the average internal path length of m-ary search trees
• Branching processes in the analysis of the heights of trees
• RANDOM HYPERPLANE SEARCH TREES IN HIGH DIMENSIONS
• On the Variance of the Height of Random Binary Search Trees
• Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
• Random-tree Diameter and the Diameter-constrained MST
• The height of Mallows trees
• Some estimates for the distribution of the height of digital search trees
• On the expected height of fringe-blanced trees
• A strong law for the height of random binary pyramids
• Some average measures in m-ary search trees
• scientific article; zbMATH DE number 3965074 (Why is no real title available?)
• ON THE AVERAGE ALTITUDE OF HEAP-ORDERED TREES
• Asymptotical growth of a class of random trees
• scientific article; zbMATH DE number 6678444 (Why is no real title available?)
• A Greedy Algorithm Estimating the Height of Random Trees
• scientific article; zbMATH DE number 2159649 (Why is no real title available?)
• Multiway trees of maximum and minimum probability under the random permutation model
• Limit distributions for multitype branching processes of \(m\)-ary search trees
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• A note on the growth of random trees
• Note on the heights of random recursive trees and random m‐ary search trees
• Paths in a random digital tree: limiting distributions
• The random multisection problem, travelling waves and the distribution of the height of \(m\)-ary search trees
• scientific article; zbMATH DE number 1552321 (Why is no real title available?)
• m‐ary Search trees when m ≥ 27: A strong asymptotics for the space requirements
• The height of increasing trees
• Dependence and phase changes in random \(m\)-ary search trees
• An analytic approach to the height of binary search trees. II
• On the joint distribution of the insertion path length and the number of comparisons in search trees

This page was built for publication: On the height of random m‐ary search trees

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