TY - GEN
T1 - Deterministic skip lists
AU - Munrot, J. Ian
AU - Papadakis, Thomas
AU - Sedgewick, Robert
N1 - Funding Information:
*This research was supported in part by the National Science and Engineering Research Council of Canada under grant No. A-8237, the Information Technology Research Centre of Ontario, and the National Science Foundation under Grant No. CCR-8918152 t DePmtment of Computer Science, University of Waterloo, Waterloo, Ont N2L 3G1, Canada t Department of Computer Princeton, NJ 08544, USA
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 -