Please use this identifier to cite or link to this item: https://doi.org/10.1006/jagm.1993.1049
Title: Unsuccessful Search in Self-Adjusting Data Structures
Authors: Hui, L.C.K. 
Martel, C.
Issue Date: Nov-1993
Source: Hui, L.C.K., Martel, C. (1993-11). Unsuccessful Search in Self-Adjusting Data Structures. Journal of Algorithms 15 (3) : 447-481. ScholarBank@NUS Repository. https://doi.org/10.1006/jagm.1993.1049
Abstract: This paper introduces a general technique for speeding up unsuccessful search using very little extra space (two bits per key). This technique is applicable to many data structures including linear lists and search trees. For linear lists we obtain 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 multiway search trees is competitive with an optimal static multiway tree and will often outperform the static tree. We are also able to extend several other results for successful search to include both successful and unsuccessful searches. © 1993 Academic Press. All rights reserved.
Source Title: Journal of Algorithms
URI: http://scholarbank.nus.edu.sg/handle/10635/99453
ISSN: 01966774
DOI: 10.1006/jagm.1993.1049
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

6
checked on Feb 14, 2018

WEB OF SCIENCETM
Citations

5
checked on Feb 14, 2018

Page view(s)

36
checked on Feb 11, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.