Deterministic skip lists

ABSTRACT

We explore techniques based on the notion of a skip list to guarantee logarithmic search, insert and delete costs. The basic idea is to insist that between any pair of elements above a given height are a small number of elements of precisely that height. The desired behaviour can be achieved by either using some extra space for pointers, or by adding the constraint that the physical sizes of the nodes be exponentially increasing. The first approach leads to simpler code, whereas the second is ideally suited to a buddy system of memory allocation. Our techniques are competitive in terms of time and space with balanced tree schemes, and, we feel, inherently simpler when taken from first principles.

REFERENCES

• 1: G. M. Adel'son-Vel'skii and E. M. Landis. "An algorithm for the Organization of Information". Doklady Akademia Nauk SSSR, vol. 146, 1962, pp. 263-266. English translation in Soviet Mathematics Doklady, vol. 3, pp. 1259-1263.
• 2: R. Bayer and E. McCreight. "Organization and Maintenance of Large Ordered Indexes". A cta In/ormatica, vol. 1, 1972, pp. 173-189.
• 3: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete mathematics: a foundation for computer science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 4: L. Guibas and R. Sedgewick. "A dichromatic framework for balanced trees". 19th Annual Symposium in Foundations o/Computer Science IEEE Computer Society. Ann Arbor, Michigan, Oct. 1978, pp. 8-21.
• 5: Harry R. Lewis , Larry Denenberg, Data Structures and Their Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 6: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 7: Thomas Papadakis , J. Ian Munro , Patricio V. Poblete, Average search and update costs in skip lists, BIT, v.32 n.2, p.316-332, 1992 [doi>10.1007/BF01994884]
• 8: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

General Terms:
Algorithms, Theory, Verification