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

NotesTreap pypi Python2/Python3 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 pypi Python2/Python3 Mostly Duncan G. Smith, but me too O(n) O(log _{2}(n))O(log _{2}(n))Yes One machine word per element stored. Supports both dict-like and set-like use Splay Tree pypi Python2/Python3 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 pypi Python2/Python3 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 pypi Python2/Python3 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

Pypi link

Implementation language

Origin

NotesBloom 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

Hits: 9482

Timestamp: 2024-02-29 11:33:53 PST

Back to Dan's tech tidbits

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