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

DOI10.1016/J.TCS.2004.08.003zbMATH Open1086.68036OpenAlexW2111855548WikidataQ122938514 ScholiaQ122938514MaRDI QIDQ706615FDOQ706615

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

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

zbMATH Keywords

Generating functionsAverage case analysisBinary search treeHeight distribution

Mathematics Subject Classification ID

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

Cites Work

• On growing random binary trees
• A note on the height of binary search trees
• Title not available (Why is that?)
• Branching processes in the analysis of the heights of trees
• Constant bounds on the moments of 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
• On the concentration of the height of binary search trees
• The variance of the height of binary search trees
• The height of a random binary search tree
• On the Variance of the Height of Random Binary Search Trees
• The random multisection problem, travelling waves and the distribution of the height of \(m\)-ary 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)