4.2 : An Efficient

A uses a skiplist structure to implement the interface. When used in this way, the list stores the elements of the in sorted order. The method works by following the search path for the smallest value such that :

Node* findPredNode(T x) { Node *u = sentinel; int r = h; while (r >= 0) { while (u->next[r] != NULL && compare(u->next[r]->x, x) < 0) u = u->next[r]; // go right in list r r--; // go down into list r-1 } return u; } T find(T x) { Node *u = findPredNode(x); return u->next[0] == NULL ? null : u->next[0]->x; }

Following the search path for is easy: when situated at some node, , in , we look right to . If , then we take a step to the right in ; otherwise, we move down into . Each step (right or down) in this search takes only constant time; thus, by Lemma 4.1, the expected running time of is .

Before we can add an element to a
, we need a method to
simulate tossing coins to determine the height,
, of a new node.
We do so by picking a random integer,
, and counting the number of
trailing s in the binary representation of
:^{4.1}

int pickHeight() { int z = rand(); int k = 0; int m = 1; while ((z & m) != 0) { k++; m <<= 1; } return k; }

To implement the method in a we search for and then splice into a few lists ,..., , where is selected using the method. The easiest way to do this is to use an array, , that keeps track of the nodes at which the search path goes down from some list into . More precisely, is the node in where the search path proceeded down into . The nodes that we modify to insert are precisely the nodes . The following code implements this algorithm for :

bool add(T x) { Node *u = sentinel; int r = h; int comp = 0; while (r >= 0) { while (u->next[r] != NULL && (comp = compare(u->next[r]->x, x)) < 0) u = u->next[r]; if (u->next[r] != NULL && comp == 0) return false; stack[r--] = u; // going down, store u } Node *w = newNode(x, pickHeight()); while (h < w->height) stack[++h] = sentinel; // height increased for (int i = 0; i < w->height; i++) { w->next[i] = stack[i]->next[i]; stack[i]->next[i] = w; } n++; return true; }

Removing an element, , is done in a similar way, except that there is no need for to keep track of the search path. The removal can be done as we are following the search path. We search for and each time the search moves downward from a node , we check if and if so, we splice out of the list:

bool remove(T x) { bool removed = false; Node *u = sentinel, *del; int r = h; int comp = 0; while (r >= 0) { while (u->next[r] != NULL && (comp = compare(u->next[r]->x, x)) < 0) { u = u->next[r]; } if (u->next[r] != NULL && comp == 0) { removed = true; del = u->next[r]; u->next[r] = u->next[r]->next[r]; if (u == sentinel && u->next[r] == NULL) h--; // skiplist height has gone down } r--; } if (removed) { delete del; n--; } return removed; }

The following theorem summarizes the performance of skiplists when used to implement sorted sets:

- ...:
^{4.1} - This method does not exactly replicate the coin-tossing experiment since the value of will always be less than the number of bits in an . However, this will have negligible impact unless the number of elements in the structure is much greater than .