• Dictionary-like trees (see also this comparison, which includes a few other dictionary-like trees I've spent less time on, specifically: AA Tree, AVL Tree, and B Tree).

  Name of datastructure	Pypi link	Implementation language	Origin	Sort time	find_min time	find_max time	Does well with ordered keys?	Storage overhead beyond binary tree?	Notes
  Treap	pypi	Python2/Python3 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	pypi	Python2/Python3	Mostly Duncan G. Smith, but me too	O(n)	O(log2(n))	O(log2(n))	Yes	One machine word per element stored.
  Splay Tree	pypi	Python2/Python3	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	pypi	Python2/Python3	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	pypi	Python2/Python3	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	Pypi link	Implementation language	Origin	Notes
  Bloom Filter	pypi	Python2/Python3	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	N/A	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	pypi	Python2/Python3	Original work by me	Singly-linked list. Includes Stack and Queue implementations
  Dupdict	pypi	Python2/Python3	Original work by me	Builds on an arbitrary dictionary(-like) type to allow duplicates
  fibonacci-heap-mod	pypi	Python2/Python3	Ported from Java by me	A priority queue with nice theoretical limits
  bits_mod	pypi	Python2/Python3	Original work by me	A bit array that can adapt to different long sizes
  trie_mod	pypi	Python2/Python3	B. Dimmick's trie implementation	A Trie: Constant time lookup of potentially-many strings; one node for each character in a hierarchy of characters. These are nice for storing natural language dictionaries and similar data

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