Problem 52

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Compare the three randomized data structures we have seen for the dictionary ADT: skip lists, randomized BSTs, and treaps. They all have expected cost \(\Theta(\log n)\) for every operation, search, insert, and delete. But they aren't exactly the same! So I want you to tell me:

- Which do you think will be fastest for search, and why?
- Which do you think will have the fastest insertion, and why?
- Which do you think will have the fastest deletion, and why?
- Which would be the simplest to implement, and why?
- Which would have the smallest memory footprint, and why?