The most recent such comparison is
On the Python datastructures:
Datastructures of Some Interest
Datastructure Implementations for Python
(When there's more time) I'd like to do a comparison of Heaps as well, including trees and treaps in heap-like usage.
Ones I did
2014-03-22 comparison with operations/second
2014-03-18 comparison of just the trees, including blist.sorteddict; excludes Pypy and Jython
2014-01 comparison of just the trees
2012-05 comparison of just the trees
, in case you want to check my methodology, etc.
Conducted by others
focuses on C-augmented datastructures and smallish datasets - in CPython.
comparison of binary search trees
in C++ dismisses treap a bit quickly, but is otherwise interesting.
Skip Lists compared with Treaps and Red-Black Trees
AVL Tree: Comparison to other data structures
Another performance comparison
xkzou on Red-Black trees
xkzou on other search trees
Heap (data structure)
described on wikipedia
to Dan's tech tidbits
You can e-mail the author with questions or comments: