Next: 5. Hash Tables Up: 4. Skiplists Previous: 4.4 Analysis of Skiplists Contents
Skiplists were introduced by Pugh [54] who also presented
a number of applications of skiplists [53]. 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 [40,39,51].
Deterministic versions [48], biased versions [7,23],
and self-adjusting versions [10] 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 [62,56]. A variant of skiplists is used in the HP-UX
operating system kernel's process management structures [38].
on the
in Figure 4.5. Assume that
selects a height
of 4 for the newly created node.
or a
operation, the expected
number of pointers in a
that get changed is constant.
into 
based on a coin toss, we promote it with some probability 
,
.
.
that minimizes the preceding expression?
method in a
sometimes performs
redundant comparisons; these occur when
is compared to the
same value more than once. They can occur when, for some node,
,
![$ \ensuremath{\mathtt{u.next[r]}} = \ensuremath{\mathtt{u.next[r-1]}}$](img762.png){kind=small}
. Show how these redundant comparisons
happen and modify
so that they are avoided. Analyze the
expected number of comparisons done by your modified
method.
interface, but also allows fast access to elements by rank.
That is, it also supports the function
, which returns the
element whose rank is
in
expected time. (The rank
of an element
in an
is the number of elements in the
that are less than
.)
in the
code on
page ![[*]](crossref.png)
is a finger; the shaded nodes in
Figure 4.3 show the contents of the finger.) One can
think of a finger as pointing out the path to a node in the lowest
list, 
.
A finger search implements the
operation using a
finger, by walking up the list using the finger until reaching a node
such that
and
or
and then performing a normal search for
starting from
.
It is possible to prove that the expected number of steps required
for a finger search is
, where 
is the number values
in between
and the value pointed to by the finger.
Implement a subclass of
called
that
does all
operations using an internal finger. This class
stores a finger and does every search as a finger search. During the
search it also updates the finger so that each
operation
uses, as a starting point, a finger that points to the result of the
previous
operation.
, that truncates a
at position
. After the execution of this method, the size
of the list is
and it contains only the elements at indices
. The return value is another
that
contains the elements at indices
. This method
should run in
time.
method,
, that takes as an
argument a
,
, empties it and appends its contents,
in order, to the receiver. For example, if
contains 
and
contains 
, then after calling
,
will contain
and
will be empty. This method should
run in
time.
,
design and implement a space-efficient
,
. Do this by
storing the data, in order, in an
and then storing the blocks
of this
in an
. If the original
implementation
uses
space to store
elements, then the
will use
enough space for
elements plus
wasted space.
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. As the user
types their query, a matching part of the text (if any) should appear
as a result.
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 [1]. If done correctly, your applications will be very responsive; there should be no noticeable lag between typing keystrokes and the results appearing.
