neal young / Chrobak21Cost
-
Information and Computation 218:11 pages(2021)
Optimal search trees can be used to implement access operations to a set of keys whose access probabilities are known. For a non-key query, such trees can determine its approximate location by returning the inter-key interval containing the query. This is in contrast to other dictionary data structures, like lists or hash tables, that only report a failed search. We address the question `what is the additional cost of determining approximate locations for non-key queries'? We prove that for two-way comparison trees this additional cost is at most 1. Our proof is technically interesting, as it is based on a novel probabilistic argument that involves converting a search tree that does not identify non-key queries into a random tree that does.
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.