Please use this identifier to cite or link to this item:
|Title:||Unsuccessful Search in Self-Adjusting Data Structures||Authors:||Hui, L.C.K.
|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.
checked on Feb 25, 2020
WEB OF SCIENCETM
checked on Feb 18, 2020
checked on Feb 28, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.