Anzeige
Erschienen in:
2024 | OriginalPaper | Buchkapitel
A Tight Threshold Bound for Search Trees with 2-Way Comparisons
verfasst von : Sunny Atalig, Marek Chrobak
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Nature Singapore
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study search trees with 2-way comparisons (2wcst ’s), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. These trees have a much subtler structure than standard search trees with 3-way comparisons (3wcst ’s) and are still not well understood, hampering progress towards designing an efficient algorithm for computing minimum-cost trees. One question that attracted attention in the past is whether there is an easy way to determine which type of comparison should be applied at any step of the search. Anderson, Kannan, Karloff and Ladner studied this in terms of the ratio between the maximum and total key weight, and defined two threshold values: \(\lambda ^-\) is the largest ratio that forces the less-than test, and \(\lambda ^+\) is the smallest ratio that forces the equal-to test. They determined that \(\lambda ^-= \tfrac{1}{4}\), but for the higher threshold they only showed that \(\lambda ^+\in [\tfrac{3}{7},\tfrac{4}{9}]\). We give the tight bound for the higher threshold, by proving that in fact \(\lambda ^+= \tfrac{3}{7}\).