Data Structures with Generic Types in Java/

...

/

SkiplistSSet: An Efficient SSet

SkiplistSSet: An Efficient SSet

Learn to implement a SkiplistSSet.

We'll cover the following...

A SkiplistSSet uses a skiplist structure to implement the SSet interface. When used in this way, the list L0L_0 stores the elements of the SSet in sorted order.

The find() method

The find(x) method works by following the search path for the smallest value yy such that y≥xy \ge 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 yy is easy: when situated at some node, u, in LrL_r, we look right to u.next[r].x. If x > u.next[r].x, then we take a step to the ...