A SkiplistSSet uses a skiplist structure to implement the SSet interface. When used this way, the list stores the elements of the SSet in sorted order. The method works by following the search path for the smallest value such that :
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 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 so, by Lemma 4.1, the expected running time of is .
Before we can add an element to a SkipListSSet, we need a method to simulate tossing coins to determine the height, , of a new node. We do this by picking a random integer, , and counting the number of trailing s in the binary representation of :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 method in a SkiplistSSet 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 :
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; }
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:
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; }
The following theorem summarizes the performance of skiplists when used to implement sorted sets: