Complete my Skip List implementationDue: February 23
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.
- Make the
insertmethod choose the height randomly by sampling random bits until a
1bit is found, as we saw in class.
- Write the
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.
- Write the
deletemethod that takes a key and removes the corresponding tower from the skip list, returning the associated value in the process.
mainmethod 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:
- Insert some random items as before, but make the associated string values different for each inserted item.
- Print out this resulting skip list
- Prompt the user for a key to search for, and display the result (either "NOT FOUND" or the associated value to that key).
- Prompt the user for a key whose tower should be deleted, and then print out the resulting skip list
Submit your program according to the instructions on the submit page.