Question 2: Skiplists [10]

(i) Suppose we have a program that uses our skiplist algorithms (as discussed in the labs and implemented in assignment 2) to insert N items into a list and then searches for a specific item.

Clearly explain how we could obtain the following different results on two runs of the same program with the same user input:

• On the first run, the search only looks at one item before finding the target item.

• On the second run, the search looks at N-1 items before finding the target item.

(ii) Suppose we were to insert value 4 as a level 3 node in the skiplist below. Redraw the skiplist to show the updated pointers.

Lev 4:------------------->*
Lev 3:------------------->*<--->*
Lev 2:------------->*<--->*<--->*
Lev 1:------>*<---->*<--->*<--->*
Node data:   0      1     5     6
(Levels)    (1)    (2)   (4)   (3)