TY - GEN

T1 - Deterministic skip lists

AU - Munrot, J. Ian

AU - Papadakis, Thomas

AU - Sedgewick, Robert

PY - 1992/9/1

Y1 - 1992/9/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84979675579&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84979675579&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84979675579

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 367

EP - 375

BT - Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

PB - Association for Computing Machinery

T2 - 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

Y2 - 27 January 1992 through 29 January 1992

ER -