Subsections


4.2 $ \mathtt{SkiplistSSet}$: An Efficient $ \mathtt{SSet}$

A $ \mathtt{SkiplistSSet}$ uses a skiplist structure to implement the $ \mathtt{SSet}$ interface. When used in this way, the list $ L_0$ stores the elements of the $ \mathtt{SSet}$ in sorted order. The $ \mathtt{find(x)}$ method works by following the search path for the smallest value $ \mathtt{y}$ such that $ \ensuremath{\mathtt{y}}\ge\ensuremath{\mathtt{x}}$:

  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 $ \mathtt{y}$ is easy: when situated at some node, $ \mathtt{u}$, in $ L_{\ensuremath{\mathtt{r}}}$, we look right to $ \mathtt{u.next[r].x}$. If $ \ensuremath{\mathtt{x}}>\ensuremath{\mathtt{u.next[r].x}}$, then we take a step to the right in $ L_{\ensuremath{\mathtt{r}}}$; otherwise, we move down into $ L_{\ensuremath{\mathtt{r}}-1}$. Each step (right or down) in this search takes only constant time; thus, by Lemma 4.1, the expected running time of $ \mathtt{find(x)}$ is $ O(\log \ensuremath{\mathtt{n}})$.

Before we can add an element to a $ \mathtt{SkipListSSet}$, we need a method to simulate tossing coins to determine the height, $ \mathtt{k}$, of a new node. We do so by picking a random integer, $ \mathtt{z}$, and counting the number of trailing $ 1$s in the binary representation of $ \mathtt{z}$: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 $ \mathtt{add(x)}$ method in a $ \mathtt{SkiplistSSet}$ we search for $ \mathtt{x}$ and then splice $ \mathtt{x}$ into a few lists $ L_0$,..., $ L_{\ensuremath{\mathtt{k}}}$, where $ \mathtt{k}$ is selected using the $ \mathtt{pickHeight()}$ method. The easiest way to do this is to use an array, $ \mathtt{stack}$, that keeps track of the nodes at which the search path goes down from some list $ L_{\ensuremath{\mathtt{r}}}$ into $ L_{\ensuremath{\mathtt{r}}-1}$. More precisely, $ \mathtt{stack[r]}$ is the node in $ L_{\ensuremath{\mathtt{r}}}$ where the search path proceeded down into $ L_{\ensuremath{\mathtt{r}}-1}$. The nodes that we modify to insert $ \mathtt{x}$ are precisely the nodes $ \ensuremath{\mathtt{stack[0]}},\ldots,\ensuremath{\mathtt{stack[k]}}$. The following code implements this algorithm for $ \mathtt{add(x)}$:

  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;
  }

Figure 4.3: Adding the node containing $ 3.5$ to a skiplist. The nodes stored in $ \mathtt{stack}$ are highlighted.
\includegraphics[width=\textwidth ]{figs/skiplist-add}

Removing an element, $ \mathtt{x}$, is done in a similar way, except that there is no need for $ \mathtt{stack}$ to keep track of the search path. The removal can be done as we are following the search path. We search for $ \mathtt{x}$ and each time the search moves downward from a node $ \mathtt{u}$, we check if $ \ensuremath{\mathtt{u.next.x}}=\ensuremath{\mathtt{x}}$ and if so, we splice $ \mathtt{u}$ 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;
  }

Figure 4.4: Removing the node containing $ 3$ from a skiplist.
\includegraphics[width=\textwidth ]{figs/skiplist-remove}

4.2.1 Summary

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

Theorem 4..1   $ \mathtt{SkiplistSSet}$ implements the $ \mathtt{SSet}$ interface. A $ \mathtt{SkiplistSSet}$ supports the operations $ \mathtt{add(x)}$, $ \mathtt{remove(x)}$, and $ \mathtt{find(x)}$ in $ O(\log \ensuremath{\mathtt{n}})$ expected time per operation.



Footnotes

...:4.1
This method does not exactly replicate the coin-tossing experiment since the value of $ \mathtt{k}$ will always be less than the number of bits in an $ \mathtt{int}$. However, this will have negligible impact unless the number of elements in the structure is much greater than $ 2^{32}=4294967296$.
opendatastructures.org