Skiplists were introduced by Pugh [61] who also presented a number of applications of skiplists [60]. 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 [45,44,58]. Deterministic versions [53], biased versions [8,26], and self-adjusting versions [12] 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 [69,63]. A variant of skiplists is used in the HP-UX operating system kernel's process management structures [42]. Skiplists are even part of the Java 1.6 API [55].

- Show that the expected length of a search path is at most .
- What is the value of that minimizes the preceding expression?
- What is the expected height of the skiplist?
- What is the expected number of nodes in the skiplist?

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 `Skiplist` called `SkiplistWithFinger` 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.

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.

- Explain how removing some edges of a skiplist lead to a structure that looks like a binary tree and that is similar to a binary search tree.
- Skiplists and binary search trees each use about the same number of pointers (2 per node). Skiplists make better use of those pointers, though. Explain why.