• Dictionary-like (see also this comparison, which includes a few other dictionary-like trees I've spent less time on).

  Name of datastructure	Implementation language	Origin	Sort time	find_min time	find_max time	Does well with ordered keys?	Storage overhead beyond binary tree?	Notes
  Treap	Python and/or Cython (m4)	Ported from Java by me	O(n)	O(log2(n))	O(log2(n))	Yes	One machine word per element stored.
  Red-Black Tree	Python	Mostly Duncan G. Smith, but me too	O(n)	O(log2(n))	O(log2(n))	Yes	One machine word per element stored.
  Splay Tree	Python	Originally from here, but I've added considerable polish.	O(n)	O(log2(n))	O(log2(n))	No	None	Storing or retrieving all keys in order would reduce it to a linked list. Recently-accessed keys are kept near the root of the tree: good for caches
  Scapegoat Tree	Python	Originally from here.	O(n)	O(log2(n))	O(log2(n))	Kind of	None	This datastructure reorganizes itself (within limits) to improve search times / storage times with no bookkeeping storage overhead.
  Binary Search Tree	Python	Originally from here.	O(n)	O(log2(n))	O(log2(n))	No	None	Storing all keys in order will reduce this to a linked list

• Miscellaneous

  Name of datastructure	Implementation language	Origin	Notes
  Bloom Filter	Python	This recipe plus some original work by me	Probabilistic set datastructure that never gives a false negative, but gives false positives with a user-adjustable probability
  Hash Table	C	Original work by me	Includes one version that works for all types using void *, and another that autogenerates one instance of the code for each type.
  Linked List	Python	Original work by me	Includes Stack and Queue implementations
  Dupdict	Python	Original work by me	Builds on dictionary-like type to allow duplicates

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