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.

Randomized dictionary comparison

Due: March 8
Points: 5

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?