Search⌘ K
Home
Courses
Data Structures with Generic Types in Java

SkiplistSSet: An Efficient SSet

Explore the SkiplistSSet data structure that implements sorted sets using skiplists. Understand how to efficiently add, find, and remove elements with expected logarithmic time complexity. Learn about the underlying search path, height selection using pickHeight, and practical implementation details like stack use for insertion and immediate removal during search.

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:

Java
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 ...