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

DOI10.1016/J.IC.2021.104707OpenAlexW3135055537MaRDI QIDQ2051772FDOQ2051772

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

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

zbMATH Keywords

algorithmsdata structuresoptimal search trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• Classification via two-way comparisons (extended abstract)
• Optimal Search Trees with 2-Way Comparisons
• Cost-error relationships in A* tree-searching
• On Huang and Wong's algorithm for generalized binary split trees
• A strategy for searching with different access costs.

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)