Lecture Overview

I discussed the skiplist list. To continue with the contrast between iterative and recursive, I present here the recursive versions of find, get, set, and add.

find_pred(i, v, r):
    # Currently searching at v height r, with 
    # i the offset from the vth elememt.
    # Returns the node right before i
    if v.next[r] == nil or v.length[r] > i:
        # Moving along r moves too far
        if r == 0:
            return v
        else:
            # Search starting at list r-1 with the same offset i
            return find_pred(i, v, r-1)
    else:
        # Move along list L_r, decrementing i by the length
        return find_pred(i - v.length[r], v.next[r], r)


get(i):
    return find_pred(i, sentinal, sentinal.h).next[0].x

set(i, x):
    u = find_pred(i, sentinal, sentinal.h).next[0]
    y = u.x
    u.x = x
    return y

In the book, the add method operates a little differently between section 4.2 and 4.3. In section 4.2 and also my code on day22, we first search out the correct location to add while storing the sequence of nodes we searched through. In the book, the nodes were stored on an explicit stack, and in my recursive version the nodes are kept in frames on the call stack, one frame per recursive invocation. Once we found the correct location for the node, we trace back through the nodes linking in the new node to its proper location. The book does this by popping the stack, and the recursive version does it after the recursive call.

It doesn't impact the big-O execution time, but if we create the new node ahead of time, we can link it into its proper place as we search down through the lists. This removes the need to store the entire sequence of nodes we search through and provides a small speed improvement since once the proper location is found the add call can return. In the book in section 4.3 this is done iteratively, creating the node ahead of time and using a loop. In the code below, I create the node ahead of time and pass it into the recursion. I then make each recursive call tail-recursive and rely on the compiler to turn tail recursion into a loop.

add(i, x):
    Flip a coin repeatedly until a tails comes up.
    Let h be the number of heads before the first tail
    w = a new node with value x and height h
    if w.h > sentinal.h:
        resize sentinal
    add_helper(i, w, sentinal, sentinal.h)

add_helper(i, w, v, r):
    # Currently searching at node v height r.
    # Adds node w at offset i from the node v.

    if v.next[r] == nil or v.length[r] > i:
        # Moving along L_r moves too far.

        # Increment the length of v, since u will go inside here somewhere
        v.length[r] = v.length[r] + 1

        # Splice w into the list L_r, since we have found its proper location
        # in the list L_r.  But only splice if the height of w is large enough
        if w.h >= r:
            w.next[r] = v.next[r]
            v.next[r] = w

            # we are adding w at offset i from v, so the new length of v is i+1
            # since i is the offset.  w then has the remaining length, so the 
            # length of w is oldVlength - (i + 1)
            w.length[r] = v.length[r] - (i + 1)
            v.length[r] = i + 1


        # If we are not yet at the bottom, we need to splice u into the lists
        # below us.
        if r > 0:
            add_helper(i, w, v, r-1)
    else:
        # Move along L_r
        add_helper(i-v.length[r], w, v.next[r], r)

Exercises

Exercises 4..4 and 4..5 from this page. For 4..5, note that your illistration will be the same no matter if you use the recursive version or the version from the book.