Implicit Data Structures for the Dictionary Problem
Greg N. Frederickson · Journal of the ACM · 1983
Several new data structures for dictionaries are presented that use just one location in addition to those required for key values.The structures are generahzations of a rotated sorted list, with the best realizing a search tune of O(log n) and insemon and deletion tunes of O(n ~(log n) 3/2) Structures adapted to allow fast average search times and structures that allow pamal match retrieval on records wRh d keys, d > 1, are also considered.