On the cost of unsuccessful searches in search trees with two-way comparisons

DOI10.1016/j.ic.2021.104707OpenAlexW3135055537MaRDI QIDQ2051772

Mordecai J. Golin, Marek Chrobak, J. Ian Munro, Neal E. Young

Publication date: 25 November 2021

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2103.01052

zbMATH Keywords

algorithmsdata structuresoptimal search trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Classification via two-way comparisons (extended abstract) ⋮ On Huang and Wong's algorithm for generalized binary split trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized binary split trees
• Nearly optimal binary search trees
• Optimal search trees using two-way key comparisons
• Twenty (short) questions
• Optimum binary search trees
• Optimal binary split trees
• Optimum split trees
• Optimal Search Trees with 2-Way Comparisons
• Faster construction of optimal binary split trees
• A New Algorithm for Minimum Cost Binary Trees
• Median split trees
• Thresholds and optimal binary comparison search trees
• Twenty (simple) questions
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes

This page was built for publication: On the cost of unsuccessful searches in search trees with two-way comparisons