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: