Lecture Overview

Continue with skiplistsset.

Here is a recursive implementation of add. Again, it does the same thing in the same way, but for me it is easier to understand the recursive version. The version in the book uses an explicit stack while the recursive version uses the call stack. The recursive version also allows you to focus on understanding a single step in the add procedure. Also, notice the similarity to the recursive find_pred_node from last time.

new_node(x):
    Flip a coin repeatedly until a tails comes up.
    Let h be the number of heads before the first tail
    return a new node with value x and height h

add_helper(x, v, r):
    # Adding value x.  Currently searching at node v at height r for the place to
    # add in x.  The return value is the newly added node.

    if v.next[r] = Nil or v.next[r].x >= x:
        # Moving along r moves past where x should go
        if r == 0:
            # We are at level zero, create a new node for x
            u = new_node(x)
        else:
            # Decrement r to search starting from v but the next list down
            u = add_helper(x, v, r-1)

        # u is the new node and since moving next along r from v moves past where
        # x should go, u must go right after v inside the list L_r.  But only splice
        # u into the list L_r if the height of u (which was randomly picked) is large enough
        if u.h >= r:
            u.next[r] = v.next[r]
            v.next[r] = u

        # Return the new node
        return u

    else:
        # We need to move right along the list r, since we are not yet skipping past x
        return add_helper(x, v.next[r], r)

add(x):
    u = add_helper(x, sentinal, sentinal.h)
    if u.h > sentinal.h:
        # The new node has height larger than the sentinal, so create new lists
        # by resizing the sentinal
        resize sentinal.next to have length h+1
        for i from sentinal.h+1 to u.h:
            sentinal.next[i] = u
        sentinal.h = u.h

Implementation

skiplistsset.cpp contains my implementation. A few notes:

• I decided to use an array of next pointers for the node, and just reallocate the sentinal's next pointers every time the sentinal has to grow. First, the sentinal will have expected height \(O(\log n)\) so this resizing will not impact my running time. Second, it is very rare to grow the sentinal, it only happens when a new list is added. And finally, this keeps the structure used for the sentinal and each node the same. If for example the sentinal used a vector or say ArrayStack, the sentinal and each node would be different C++ structures. It is possible to do that, but it would complicate the code in add and remove. Since there isn't much downside to just always reallocating the sentinal's next array, that is the technique I use.

• I also have each node store a value. It was easy to add this value, since it was just added to each node and passed around the various functions. The core of the operation of the find and add methods is the same as the pseudocode.

• A reference for the code generating a random integer is here.

Exercise

Implement the remove method inside skiplistsset.cpp. It should work similarly to find and add; I suggest you use a recursive version.