The path length of random skip lists

Abstract. 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.

helmut@gauss.cam.wits.ac.za

Peter.Kirschenhofer@tuwien.ac.at,


This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)