Fork me on GitHub

Introducing prefixtree

prefixtree implements Python dict and set like objects using a trie or prefix tree. Tries are ordered, tree based data structures. Using tries adds unique features to dict and set like objects:

  • Keys are returned in sorted order.
  • Slice operations for getting, setting and deleting values.

Python’s builtin dict is implemented using a hash table. While they are an excellent, general purpose container that have been heavily optimised. There are use cases where tree based containers are a better solution.