Randomized dictionary comparisonDue: March 8
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?