This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
Write a Python, C++, or Java program that implements the dictionary ADT with a Skip List data structure and demonstrates your implementation with some random insertions and deletions.
I have begun this implementation for you; download the file for your favorite language here:
My implementation is incomplete in that it is missing the
delete operations, and the height in
insert is not chosen randomly but is hard-coded at 1. So fix it! And then extend the demo in the
main method to do some searches and deletions.
insertmethod choose the height randomly by sampling random bits until a
1bit is found, as we saw in class.
searchmethod that takes a key and returns the value associated with that key in the skip list, or something like
Nonethat indicates the key is not in the skip list at all.
deletemethod that takes a key and removes the corresponding tower from the skip list, returning the associated value in the process.
main method that I have include randomly inserts some items into the skip list with randomly-chosen small integer keys and boring string values, then prints the resulting skip list. Extend this demo to do the following:
Submit your program according to the instructions on the submit page.