CS1800ACC Project 4: Skiplists and BST

Study the Skiplists and Binary Search Tree data structures and operations. They are used for sorting values, but more efficient than lists or arrays; Skiplists are "more" guaranteed (statistically) to be balanced than binary search trees. Check out these visualizer tools:
skiplist visualizer
BST visualizer .

Demonstrate Operations.

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)

Demo them side by side and perform each operation in both before moving on. For example 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 random 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.