Subsections


4.2 SkiplistSSet: An Efficient SSet Implementation

A SkiplistSSet uses a skiplist structure to implement the SSet interface. When used this way, the list $ L_0$ stores the elements of the 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<T> findPredNode(T x) {
        Node<T> 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<T> 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 so, 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 SkipListSSet, we need a method to simulate tossing coins to determine the height, $ \mathtt{k}$, of a new node. We do this 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.nextInt();
        int k = 0;
        int m = 1;
        while ((z & m) != 0) {
            k++;
            m <<= 1;
        }
        return k;
    }

To implement the $ \mathtt{add(x)}$ method in a 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)}$:

    boolean add(T x) {
        Node<T> 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<T> w = new Node<T>(x, pickHeight());
        while (h < w.height())
            stack[++h] = sentinel;   // increasing height of skiplist
        for (int i = 0; i < w.next.length; 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{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:

    boolean remove(T x) {
        boolean removed = false;
        Node<T> 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) {
                removed = true;
                u.next[r] = u.next[r].next[r];
                if (u == sentinel && u.next[r] == null)
                    h--;         // skiplist height has gone down
            }
            r--;
        }
        if (removed) n--;
        return removed;
    }

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

4.2.1 Summary

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

Theorem 4..1   A SkiplistSSet implements the SSet interface. A 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