On efficient unsuccessful search
Lucas C. K. Hui, Charles U. Martel · Symposium on Discrete Algorithms · 1992
This paper introduces a general technique for speeding up unsuccessful search using very little extra space (2 bits per key). This technique is applicable to many data structures including linear lists, and search trees. For linear lists we get on-line algorithms for processing a sequence of successful and unsuccessful searches which are competitive with strong off-line algorithms. In a virtual memory environment our self-adjusting algorithm for multi-way search trees is competitive with an optimal static multi-way tree and will often outperform the static tree.