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

DOI10.1016/J.IC.2021.104707MaRDI QIDQ2051772zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Mordecai J. Golin, 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)

Recommendations

• Optimal search trees using two-way key comparisons
• Optimal alphabetic trees for binary search
• A strategy for searching with different access costs.
• Binary search trees with binary comparison cost
• Optimal Search Trees with 2-Way Comparisons

Cites work

• A New Algorithm for Minimum Cost Binary Trees
• Faster construction of optimal binary split trees
• Generalized binary split trees
• scientific article; zbMATH DE number 4210044 (Why is no real title available?)
• scientific article; zbMATH DE number 4057247 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Median split trees
• Nearly optimal binary search trees
• Optimal binary split trees
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Optimal search trees using two-way key comparisons
• Optimal Search Trees with 2-Way Comparisons
• Optimum binary search trees
• Optimum split trees
• Thresholds and optimal binary comparison search trees
• Twenty (short) questions
• Twenty (simple) questions

Cited in

(6)

• A strategy for searching with different access costs.
• On Huang and Wong's algorithm for generalized binary split trees
• Optimal Search Trees with 2-Way Comparisons
• Cost-error relationships in A* tree-searching
• scientific article; zbMATH DE number 742968 (Why is no real title available?)
• Classification via two-way comparisons (extended abstract)

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

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