Data Structures with Generic Types in Python/

...

/

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:

Press + to interact
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 ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy