CS1800 honors PB4: Skiplists and BST demos

Study the Skiplists and Binary Search Tree data structures and operations. They are used for sorting values, but more effficient than lists or arrays; Skiplists are "more" guaranteed (statistically) to be balanced than binary search trees.

Demonstrate Operations.

Your sumbmission is a video url, 5-8 min, demonstrating the operations on skiplist visualizer and BST visualizer . Use two browser windows side by side and perform each operation in both before moving on. Your video should capture the screen, and the audio in sync with the displayed operations. You dont have to film yourslef (you can if you want to), but state clearly your name.

Perform the following operations: You might end up with a screen like this when you are done.

Keep in mind that each Skiplist INSERT operation requires flipping a fair coin until you get a 0. For example a particular insert might use the randomly-generated the coin flip sequence "110"; in this case the value inserted is promoted on the next two lists above the bottom-all-elements list, but not on the third list. When the coin flips are not specified, you can use a randon generator or let the visualizer flip coins for you. The BST ignores the coin flips.

On operations marked "demo/explain steps", once the animation is completed, hit "pause", and then very briefly describe each step. The visualizer helps you with a description at the top.

Optional (no credit).

Implement your own BST and Skiplist Data-structures and Operations (requires using a programming language that facilitates pointers, memory objects, and familiarity with linked lists)