Complete my Skip List implementation

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:

• skiplist.py
• skiplist.cpp
• SkipList.java

My implementation is incomplete in that it is missing the search and 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.

Specifically:

1. Make the insert method choose the height randomly by sampling random bits until a 1 bit is found, as we saw in class.
2. Write the search method that takes a key and returns the value associated with that key in the skip list, or something like null or None that indicates the key is not in the skip list at all.
3. Write the delete method that takes a key and removes the corresponding tower from the skip list, returning the associated value in the process.

4. The 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:

   • 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.