Problem 44

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Limiting skip list height

Due: February 15
Points: 1

We have observed that the worst-case performance of a skip list is actually unbounded. Even with a single insertion, the height could grow to be arbitrarily large.

To avoid this behavior, we might explicitly limit the maximum height of new node being inserted to something like $$\lg n$$. Does this seem like a good idea to you? Why or why not?