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 | Citation: | 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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.