Skiplists were introduced by Pugh  who also presented
a number of applications of skiplists . Since then they
have been studied extensively. Several researchers have done very
precise analysis of the expected length and variance in length of the
search path for the
th element in a skiplist [38,37,49].
Deterministic versions , biased versions [6,21],
and self-adjusting versions  of skiplists have all been
developed. Skiplist implementations have been written for various
languages and frameworks and have seen use in open-source database
systems [60,54]. A variant of skiplists is used in the HP-UX
operating system kernel's process management structures .
Skiplists are even part of the Java 1.6 API .
Show that, during an
operation, the expected
number of pointers in the structure that get changed is constant.
Suppose that, instead of promoting an element from
based on a coin toss, we promote it with some probability
. Show that the expected length of the search path in this case
is at most
. What is the value of
that minimizes this expression? What is the expected height of the
skiplist? What is the expected number of nodes in the skiplist?
Design and implement a
method for SkiplistSSet
; these are comparisons that have already
been done and occur because
Analyze the expected number of comparisons done by your modified
Design and implement a version of a skiplist that implements the
interface, but also allows fast access to elements by rank.
That is, it also supports the function
, which returns the
element whose rank is
expected time. (The rank
of an element
in an SSet
is the number of elements in the SSet
that are less than
Using the ideas from the space-efficient linked-list, SEList
design and implement a space-efficient SSet
. Do this by
storing the data, in order, in an SEList
and then storing the blocks
of this SEList
in an SSet
. If the original SSet
space to store
elements, then the SESSet
enough space for
Using an SSet
as your underlying structure, design and implement an
application that reads a (large) text file and allow you to search,
interactively, for any substring contained in the text.
Hint 1: Every substring is a prefix of some suffix, so it
suffices to store all suffixes of the text file.
Hint 2: Any suffix can be represented compactly as a single
integer indicating where the suffix begins in the text.
Test your application on some large texts like some of the books
available at Project Gutenberg .