This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 62

Randomized dictionary comparison

Due: March 8
Points: 3

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?