Ask the web
with the leading AI models

Figure 4.2: The search path for the node containing 4 in a skiplist.

as consisting of a data value, x, and an array, next, of pointers, where u.next[i] points to u’s successor in the list L_i. In this way, the data, x, in a node is stored only once, even though x may appear in several lists.

struct Node {
  T x;
  int height;      // length of next
  Node *next[];
};

The next two sections of this chapter discuss two different applications of skiplists. In each of these applications, L₀ stores the main structure (a list of elements or a sorted set of elements). The primary difference between these structures is in how a search path is navigated; in particular, they differ in how they decide if a search path should go down into L_r−1 or go right within L_r.

4.2   SkiplistSSet: An Efficient SSet

A SkiplistSSet uses a skiplist structure to implement the SSet interface. When used in this way, the list L₀ stores the elements of the SSet in sorted order. The find(x) method works by following the search path for the smallest value y such that y ≥ x:

Node* findPredNode(T x) {

89

It is worth comparing the Treap data structure to the SkiplistSSet data structure. Both implement the SSet operations in O(log n) expected time per operation. In both data structures, add(x) and remove(x) involve a search and then a constant number of pointer changes (see Exercise 7.5 below). Thus, for both these structures, the expected length of the search path is the critical value in assessing their performance. In a SkiplistSSet, the expected length of a search path is

In a Treap, the expected length of a search path is

Thus, the search paths in a Treap are considerably shorter and this translates into noticeably faster operations on Treaps than Skiplists. Exercise 4.7 in Chapter 4 shows how the expected length of the search path in a Skiplist can be reduced to

by using biased coin tosses. Even with this optimization, the expected length of search paths in a SkiplistSSet is noticeably longer than in a Treap.

7.3   Discussion and Exercises

Random binary search trees have been studied extensively. Devroye [19] gives a proof of Lemma 7.1 and related results. There are much stronger results in the literature as well, the most impressive of which is due to Reed [62], who shows that the expected height of a random binary search tree is

where is the unique solution on the interval of the equation and . Furthermore, the variance of the height is constant.

168