On the height of random m‐ary search trees

DOI10.1002/RSA.3240010206zbMATH Open0739.05077OpenAlexW2119067845MaRDI QIDQ3977075FDOQ3977075

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Branching processes in the analysis of the heights of trees
• Title not available (Why is that?)
• More Combinatorial Properties of Certain Trees

Cited In (33)

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