A Limit Theory for Random Skip Lists
Devroye, Luc
Ann. Appl. Probab., Tome 2 (1992) no. 4, p. 597-609 / Harvested from Project Euclid
The skip list was introduced by Pugh 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) - \lbrack c/(c - 1) \rbrack \log c$, and $p \in (0, 1)$ is a design parameter of the skip list.
Publié le : 1992-08-14
Classification:  Skip list,  data structures,  probabilistic analysis,  weak convergence,  height of a tree,  branching processes,  68P05,  68Q25,  60J85
@article{1177005651,
     author = {Devroye, Luc},
     title = {A Limit Theory for Random Skip Lists},
     journal = {Ann. Appl. Probab.},
     volume = {2},
     number = {4},
     year = {1992},
     pages = { 597-609},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177005651}
}
Devroye, Luc. A Limit Theory for Random Skip Lists. Ann. Appl. Probab., Tome 2 (1992) no. 4, pp.  597-609. http://gdmltest.u-ga.fr/item/1177005651/