Data structure zoo: 6 ways of implementing an ordered set

This article compares six different ways of implementing an ordered set: AVL tree, red-black tree, treap, splay tree, skip list, and a pre-balanced tree. The different data structures make different trade offs and ultimately arrive at curiously different solutions that fit a variety of real-world use cases.