Skip lists are one of my favourite data structures. They're slower than balanced trees, but ridiculously simple to implement.