A Simple Algorithm for Optimal Search Trees with Two-way Comparisons

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

doi:10.1145/3477910

A Simple Algorithm for Optimal Search Trees with Two-way Comparisons

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

Department of Computer Science and Engineering

Research output: Contribution to journal › Journal Article › peer-review

5 Citations (Scopus)

Abstract

We present a simple O(n4)-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.

Original language	English
Article number	2
Journal	ACM Transactions on Algorithms
Volume	18
Issue number	1
DOIs	https://doi.org/10.1145/3477910
Publication status	Published - 2 Dec 2021

Bibliographical note

Publisher Copyright:
© 2021 held by the owner/author(s).

Keywords

Data structures
algorithms
optimal search trees

Access to Document

10.1145/3477910

Cite this

@article{4aaf917d86cd4d00b9f6cd89e69d073c,

title = "A Simple Algorithm for Optimal Search Trees with Two-way Comparisons",

abstract = "We present a simple O(n4)-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.",

keywords = "Data structures, algorithms, optimal search trees",

author = "Marek Chrobak and Mordecai Golin and \{Ian Munro\}, J. and Young, \{Neal E.\}",

note = "Publisher Copyright: {\textcopyright} 2021 held by the owner/author(s).",

year = "2021",

month = dec,

day = "2",

doi = "10.1145/3477910",

language = "English",

volume = "18",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - A Simple Algorithm for Optimal Search Trees with Two-way Comparisons

AU - Chrobak, Marek

AU - Golin, Mordecai

AU - Ian Munro, J.

AU - Young, Neal E.

PY - 2021/12/2

Y1 - 2021/12/2

N2 - We present a simple O(n4)-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.

AB - We present a simple O(n4)-time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.

KW - Data structures

KW - algorithms

KW - optimal search trees

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:000944887800002

UR - https://openalex.org/W3134377377

U2 - 10.1145/3477910

DO - 10.1145/3477910

M3 - Journal Article

SN - 1549-6325

VL - 18

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 2

ER -

A Simple Algorithm for Optimal Search Trees with Two-way Comparisons

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this