• A table
• A series of graphs

Datastructure	Random performance	Sequential performance	Notes
AA_tree	Not good	Not good
AVL_tree	Mid-level performance	Mid-level performance
binary_tree_dict	Quite good	Quite poor	Writing to them in order will reduce these to a linked list
B_tree	Rather poor	Not that bad
dict	By far the fastest	By far the fastest	This is included for the sake of comparison. The others all do find_min and find_max in O(log2(n)) time and iterate over the sorted values of the dictionary in O(n) time; this one does neither. However, if you don't require find_min or find_max, and don't need to iterate over the dictionary's values in order, this is frequently a very good choice.
red-black_tree	Mid-level performance	Just slightly better than mid-level
scapegoat_tree_0_6	Very bad	Very bad	This is a Scapegoat Tree with α==0.6
scapegoat_tree_0_75	Good	Bad	This is a Scapegoat Tree with α==0.75
scapegoat_tree_0_9	Pretty good	Not so good	This is a Scapegoat Tree with α==0.9
splay_tree	Not bad	Excellent	Splay trees reorganize themselves not just on writes, but also on reads. The "Sequential" workload is actually ordered writes, but random reads. That's probably why this did so well at the Sequential workload. Normally, accessing each value in order will reduce these to a linked list, much like Binary Trees.
treap	Not so good	Good

• This time, instead of running all datastructures up to 8 million operations, I've run them to a maximum of 8 million operations, or until a given test exceeds 2 minutes - whichever comes first. This allowed a meaningful comparison of datastructures that do poorly at something - EG binary trees with sequential inputs.
• The operations are all either 5% get, 95% set; 50% get, 50% set; or 95% get, 5% set. The set-heavy workloads produce much larger trees.

You can e-mail the author with questions or comments: