Skip Lists

Here is a skip list, including instance variables s (the starting position), h (the height: we assume that h starts counting from 0), and n (the number of keys currently stored in the skip list). For simplicity, the graphic shows only horizontal lines, but keep in mind that these are doubly linked lists in both the horizontal and vertical directions. You can use this simplified drawing in your response.

(a) Trace the path that SkipSearch(23) takes, by circling every node that p is assigned to as the SkipSearch algorithm executes, starting with s.

In the remaining questions, you will show what the skip list shown above looks like after the cumulative operations indicated below, using the pseudocode for SkipInsert and SkipSearch. Trace the algorithm using the sequence of random numbers, [0,1], where the insertion code says while random(0,1) 1/2 do (Not all of the numbers will be used). The operations are cumulative: each step builds on the result of the previous one. Redraw the entire data structure after each operation, and also update instance variables s, h and n as needed.

SkipInsert algorithm:

SkipSeach algorithm:

(b) Redraw after SkipInsert(53,data) where random(0,1) returns 0.11, 0.47, 0.23, 0.88, 0.04, ...

(c) Redraw after SkipInsert(32,data) where random(0,1) returns 0.37, 0.61, 0.13, 0.94, 0.28,

(d) Redraw after SkipDeletePosition(SkipSearch(15)).

h-3, n=4 S3 -inf +inf 15 S2 -in S1-inf SO -inf +inf 23inf 10 15 23 36 +inf h-3, n=4 S3 -inf +inf 15 S2 -in S1-inf SO -inf +inf 23inf 10 15 23 36 +inf