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.

# 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?