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:
- insert 20, use coin flips "110"
- insert 40
- insert 10, demo/explain steps
- insert 20
- insert 5
- insert 80
- delete 20
- insert 100
- insert 20, use coin flips "10", demo/explain steps
- insert 30
- delete 5, demo/explain steps
- insert 50
- lookup 80, demo/explain steps
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)