Header menu link for other important links
Some observations on skip-lists
Published in
Volume: 39
Issue: 4
Pages: 173 - 176
The Skip-list data-structure was proposed by Pugh as an alternate to balanced binary search trees. This remarkably simple data-structure uses randomization and Pugh proved that the expected performance is comparable to the balanced trees. In this note we prove that the performance can be further guaranteed in the following sense: the probability of the search time or space complexity exceeding their expected values, approaches 0 rapidly as the number of keys increases. © 1991.
About the journal
Published in
Open Access
Impact factor