- 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?

NotesTreap Python and/or Cython (m4) Ported from Java by me O(n) O(log _{2}(n))O(log _{2}(n))Yes One machine word per element stored. Red-Black Tree Python Mostly Duncan G. Smith, but me too O(n) O(log _{2}(n))O(log _{2}(n))Yes One machine word per element stored. Splay Tree Python Originally from here, but I've added considerable polish. O(n) O(log _{2}(n))O(log _{2}(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 cachesScapegoat Tree Python Originally from here. O(n) O(log _{2}(n))O(log _{2}(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(log _{2}(n))O(log _{2}(n))No None Storing all keys in order will reduce this to a linked list - Miscellaneous

Name of datastructure

Implementation language

Origin

NotesBloom 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

593

Back to Dan's tech tidbits

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