New lower bounds on the cost of binary search trees

DOI10.1016/0304-3975(95)00153-0zbMath0871.68065OpenAlexW2064947478MaRDI QIDQ1351808

Roberto De Prisco, Alfredo De Santis

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00153-0

zbMATH Keywords

Kraft sum

Mathematics Subject Classification ID

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

Related Items (3)

Efficient Construction of Near-Optimal Binary and Multiway Search Trees ⋮ Optimal binary search trees ⋮ Reflections on Optimal and Nearly Optimal Binary Search Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Nearly optimal binary search trees
• On binary search trees
• An achievable bound for optimal noiseless coding of a random variable (Corresp.)
• Tight lower bounds for optimum code length (Corresp.)
• A Best Possible Bound for The Weighted Path Length of Binary Search Trees
• Some equivalences between Shannon entropy and Kolmogorov complexity
• A lower bound on the expected length of one-to-one codes
• New bounds on the expected length of one-to-one codes

This page was built for publication: New lower bounds on the cost of binary search trees