The variance of the height of binary search trees

DOI10.1016/S0304-3975(01)00006-8zbMath0988.68059WikidataQ127932493 ScholiaQ127932493MaRDI QIDQ5958339

Michael Drmota

Publication date: 3 March 2002

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

zbMATH Keywords

generating functionsbinary search treeaverage case analysis

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

One-sided variations on binary search trees ⋮ Retracted: Strong limiting behavior in binary search trees ⋮ Limiting theorems for the nodes in binary search trees ⋮ On Robson's convergence and boundedness conjectures concerning the height of binary search trees ⋮ EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES

Cites Work

• Unnamed Item
• On growing random binary trees
• 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
• The height of a random binary search tree
• A note on the height of binary search trees
• On the concentration of the height of binary search trees
• On the Variance of the Height of Random Binary Search Trees

This page was built for publication: The variance of the height of binary search trees