I started skiplists. First, the basic structure and then the skiplistsset psuedocode. Recall also the sset ADT.
This comment is a good way of thinking about random variables if you are not confortable with them yet.
The book uses an iterative approach to find. For contrast, here is the recusrive version. It performs the same operation in the same way, and an optimizing compiler will likely produce the same code (since the recursive version is tail-recursive). For me, it is easier to reason about the recursive version.
find_pred_node(x, v, r):
# * Returns a node u such that u.x < x and u.next[0].x >= x, that is the node u
# that is the previous node from x
# * We are currently searching at node v at height r.
if v.next[r] = Nil or v.next[r].x >= x:
# Moving next along list L_r skips so far that we move past x.
if r == 0:
# If we are at level zero, we have found the correct node.
return v
else:
# Decrement r to still search starting from v but the next list down
return find_pred_node(x, v, r-1)
else:
# We need to move right along list r, since we are not yet skipping past x
return find_pred_node(x, v.next[r], r)
find(x):
# Start at the top of the sentinal
u = find_pred_node(u, sentinal, sentinal.h)
if u.next[0] == nil then return nil
return u.next[0].xNo homework, study for the exam