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

SkiplistSSet: An Efficient SSet

Explore how SkiplistSSet implements the SSet interface using a skiplist to maintain elements in sorted order. Understand the efficient O(log n) expected runtime of add, remove, and find operations. Learn algorithms for node height selection, insertion using a stack to track search paths, and removal techniques. Gain practical insight through code examples and test cases that verify operation correctness and performance.

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:

Python 3.10.4
class SkiplistSSet(BaseSet):
    class Node(object):
        """A node in a skip list"""
        def __init__(self, x, h):
            self.x = x
            self.next = new_array(h+1)
        
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def find_pred_node(self, x):
        u = self.sentinel
        r = self.h
        while r >= 0:
            while u.next[r] is not None and u.next[r].x < x:
                u = u.next[r]  # go right in list r
            r -= 1  # go down into list r-1
        return u
    def find(self, x):
        u = self.find_pred_node(x)
        if u.next[0] is None: return None
        return 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 right in LrL_r ...