Say that a link between nodes x and y at some level l of a skip list “skips” a n
ID: 3759665 • Letter: S
Question
Say that a link between nodes x and y at some level l of a skip list “skips” a node z at level j < l if z lies between x and y and has height j + 1 (hence, its pillar reaches but does not exceed level j). Suppose I construct a skip list that satisfies the following two invariants at every level l > 0:
(1) Every link at level l skips at least one node at level l 1.
(2) No link at level l skips more than three nodes at level l 1.
(a) Prove that, in a skip list with n elements that satisfies invariants (1) and (2), the worst-case height of the tallest pillar must be O(log n).
(b) Prove that, in a skip list with n elements that satisfies invariants (1) and (2), a find operation takes worst-case O(log n) time. (Hint: imagine running the search backwards as we did in our analysis in class. Can use you the invariants to bound the number of horizontal steps at each level?) (c) The following procedure attempts to dynamically maintain the two invariants above when inserting an item into a skip list. It always assigns a new node height 1, but it may dynamically “elevate” one or more existing nodes during insertion, growing the height of their pillars by 1.
Insert(z)
allocate a pillar of height 1 for z
l head.height 1
x head
while l 0 do
y x[l].next
if y.key < z.key
x y
else if link x y skips 3 nodes a b c at level l 1
elevate node b to level l
l
link z between x, y at level 0
Prove that, if a skip list satisfies the two invariants before inserting a node with this procedure, it still satisfies them afterwards. You may assume that the list is initially non-empty, and that the head and tail are initially exactly one level taller than the tallest node in the list. (Hint: this strategy is similar to the preemptive splitting used to maintain the B-tree invariants on insertion. Formulate a similar inductive argument that shows that the invariant is maintained after processing each level of the list.)
Explanation / Answer
l head.height 1
x head
while l 0 do
y x[l].next
if y.key < z.key
x y
else if link x y skips 3 nodes a b c at level l 1
elevate node b to level l
l