Average search and update costs in skip lists. (English) Zbl 0761.68030

Papadakis, Thomas; Munro, J. Ian; Poblete, Patricio V.

BIT 32, No. 2, 316-332 (1992).

Summary: Skip lists, introduced by W. Pugh [Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM 33(6), 668-676 (1990); A skip list cook bound. Technical Report CS–TR–2286, Department of Computer Science, University of Maryland/College Park (1989)], provide an alternative to search trees, although a precise analysis of their behaviour had been elusive. The exact value of the expected cost for the search of the \(m\)th element in a skip list of \(n\) elements is derived first in terms of previously studied functions, and secondly, as an asymptotic expression. The latter suggests that Pugh’s upper bound of the expected search cost is fairly tight for the interesting cases. Assuming a uniform query distribution, the exact and an asymptotic value of the average (over all \(m\)) expected search cost in a skip list on \(n\) elements is also derived. Finally, all insert and delete costs are obtained.

MSC:

68P05

Data structures

Keywords:

dictionary; probabilistic algorithms; Skip lists

References:

[1]	Aragon, C. R. and Seidel, R. G.Randomized search trees. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park, NC, Oct. 1989, pp. 540–545. · Zbl 0857.68030
[2]	Culberson, J. and Munro, J. I.Explaining the behaviour of binary search trees under prolonged updates: a model and simulations. The Computer Journal, vol. 32, no. 1, Feb. 1989, pp. 68–75.
[3]	Culberson, J. and Munro, J. I.Analysis of the standard deletion algorithms in exact fit domain for binary search trees. Algorithmica, vol. 5, no. 3, 1990, pp. 295–311. · Zbl 0696.68031
[4]	Devroye, L.Expected time analysis of skip lists. Technical Report, School of Computer Science, McGill University, Montreal, 1990.
[5]	Devroye, L.A limit theory for random skip lists. Annals of Applied Probability, to appear. · Zbl 0754.68039
[6]	Flajolet, P.Mathematical methods in the analysis of algorithms and data structures. In Trends in Theoretical Computer Science, Börger, E., ed., Computer Science Press, 1988, pp. 225–304.
[7]	Knuth, D. E.The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 1973. · Zbl 0302.68010
[8]	Mahmoud, H.Evolutions of Random Search Trees, John Wiley & Sons, 1991.
[9]	Papadakis, T., Munro, J. I. and Poblete, P.Analysis of the expected search cost in skip lists. Lecture Notes in Computer Science, no. 447, Proceedings of the 2nd Scandinavian Workshop of Algorithm Theory. Bergen, Norway, July 1990, pp. 160–172.
[10]	Pugh, W.Skip lists: a probabilistic alternative to balanced trees. Communications of the ACM, vol. 33, no. 6, June 1990, pp. 668–676.
[11]	Pugh, W.A skip list cook book. Technical Report CS-TR-2286, Department of Computer Science, University of Maryland, College Park, July 1989.
[12]	Vitter, J. S. and Flajolet, P.Average-case analysis of algorithms and data structures. InHandbook of Theoretical Computer Science, The MIT Press, 1990, pp. 431–524. · Zbl 0900.68251