Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

SkiplistSSet: An Efficient SSet

Explore the implementation of SkiplistSSet, a data structure that uses skiplists to maintain sorted sets efficiently. Learn how to perform add, remove, and find operations with expected logarithmic time, understand the role of the pickHeight method, and see how this structure optimizes search paths for fast data manipulation.

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:

C++
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 ...