Synopsis: The top 2 in performance were always 2 of the following three datastructures:
  1. Treap
  2. Splay tree
  3. AVL tree
...and the Treap was consistently in either first place or second place.

Here are the graphs.