A limit theory for random skip lists. (English) Zbl 0754.68039

Devroye, Luc

Ann. Appl. Probab. 2, No. 3, 597-609 (1992).

Summary: The skip list was introduced by W. Pugh [Lect. Notes Comput. Sci. 382, Springer, Berlin, 437-449 (1989)] in 1989 as a data structure for dictionary operations. Using a binary tree representation of skip lists, we obtain the limit law for the path lengths of the leaves in the skip list. We also show that the height (maximal path length) of a skip list holding \(n\) elements is in probability asymptotic to \(c\log_{1/p}n\), where \(c\) is the unique solution greater than 1 of the equation \(\log(1- p)=\log(c-1)-[c/(c-1)]\log c\), and \(p\in(0,1)\) is a design parameter of the skip list.

MSC:

68P05	Data structures
68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

random tree; skip list