Implicit data structures with fast update
- 1 October 1980
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 255-259
- https://doi.org/10.1109/sfcs.1980.23
Abstract
Several new data structures for dictionaries are presented that use just one location in addition to those required for key values. The structures are generalizations of a rotated sorted list, with the best realizing a search time of 0(log n) and insert and delete times of 0(n√2/log n(log n)3/2). Similar structures are presented for a dictionary with records containing k≫1 keys, under the operations of search, partial match, insert and delete.Keywords
This publication has 6 references indexed in Scilit:
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980
- Implicit data structures (Preliminary Draft)Published by Association for Computing Machinery (ACM) ,1979
- Interpolation search—a log log N searchCommunications of the ACM, 1978
- The complexity of searching an ordered random tablePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- Partial-Match Retrieval AlgorithmsSIAM Journal on Computing, 1976
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975