On Robson's convergence and boundedness conjectures concerning the height of binary search trees

DOI10.1016/J.TCS.2004.08.003MaRDI QIDQ706615zbMATH OpenOpenAlexWikidataFDO

Authors Michael Drmota

Publication date 9 February 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.08.003

zbMATH Keywords

Generating functionsAverage case analysisBinary search treeHeight distribution

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• On the concentration of the height of binary search trees
• On the Variance of the Height of Random Binary Search Trees
• On growing random binary trees
• A note on the height of binary search trees
• An analytic approach to the height of binary search trees

Cites work

• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• A note on the height of binary search trees
• An analytic approach to the height of binary search trees
• An analytic approach to the height of binary search trees. II
• Branching processes in the analysis of the heights of trees
• Constant bounds on the moments of the height of binary search trees
• On growing random binary trees
• On the Variance of the Height of Random Binary Search Trees
• On the concentration of the height of binary search trees
• The height of a random binary search tree
• The random multisection problem, travelling waves and the distribution of the height of m-ary search trees
• The variance of the height of binary search trees

Cited in

(2)

• The shape of unlabeled rooted random trees
• On growing random binary trees

This page was built for publication: On Robson's convergence and boundedness conjectures concerning the height of binary search trees

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