The path length of random skip lists
The skip list is a recently introduced data structure that may be seen
as an alternative to (digital) tries. In the present paper we analyze
the path length of random skip lists asymptotically, i.e. we study
the cumulated successful search costs. In particular we derive a precise
asymptotic result on the variance, being of order $n^2$ (which is in
contrast to tries under the symmetric Bernoulli model, where it is only
of order $n$). We also intend to present some sort of technical toolkit
for the skilful manipulation and asymptotic evaluation of generating
functions that appear in this context.
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)