Skip to content
Tutorials Center
My learning

Topics

Lesson 144 of 149 ยท Data Structures and Algorithms

Extra Data Structure Libraries: sortedcontainers, treelib, intervaltree, pygtrie

Go beyond lists and dicts. Use sortedcontainers for always-sorted data, treelib for trees, intervaltree for ranges and pygtrie for prefix lookups, with runnable examples.

Python's built-in list, dict, set and tuple, plus the collections module, cover most everyday work. But some problems keep asking for a structure the standard library does not include: a collection that stays sorted as you add items, a tree you can print and walk, a set of time ranges you can query for overlaps, or a prefix tree for autocomplete.

You could write each one yourself (and learning how is valuable: see data structures and algorithms). In real projects, though, a well-tested library is usually the better choice. This lesson tours four popular pure-Python libraries. All of them run in your browser here with the real packages.

Install them in your own environment with pip install sortedcontainers treelib intervaltree pygtrie. In the examples below, the micropip.install(...) line does the same job inside the browser.

Which one do I need?

Pick the structure for the question

sortedcontainers Always sorted, rank and range queries
treelib Parent and child nodes, pretty printing
intervaltree Which ranges overlap this point?
pygtrie All keys that start with a prefix

Each answers one question quickly.

1 / 2

sortedcontainers: always-sorted collections

Keeping a Python list sorted by calling list.sort() after every insert is wasteful, and bisect.insort is better but still moves many items. sortedcontainers provides SortedList, SortedDict and SortedSet, which keep their items in order after every change while staying fast (inserts and removals are roughly logarithmic in practice). The library is implemented in pure Python, yet it is often faster than C-extension tree packages.

Python SortedList, SortedDict and SortedSet

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A SortedList is a good fit for leaderboards, "median of a stream", order books, sliding-window statistics and scheduling by timestamp. Remember two rules. Items must be comparable with each other, and you must not mutate an item in a way that changes its sort position while it is inside the list (remove it, change it, add it again). SortedList.add is the insert method; there is no append, since position is decided by the value.

treelib: trees you can print and walk

Python has no built-in tree. You can build one from nested dictionaries or node classes, but treelib gives you named nodes with unique ids, parent and children lookups, traversal, subtrees and a pretty text display, which is perfect for organization charts, file system models, category menus and decision trees.

Python An organization chart with treelib

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every node needs a unique identifier (nid); the tag is only a label and may repeat. expand_tree is a generator that visits ids in depth-first, width-first or sorted order. Nodes can also carry a data= payload for anything you want to attach. Tree.to_json() and Tree.save2file() export the structure.

If all you need is a quick nested structure, a dictionary is simpler. Reach for treelib when you want to navigate and display.

intervaltree: questions about ranges

Calendars, bookings, genome regions, price bands and maintenance windows all store ranges, and you keep asking: which ranges contain this point? or which overlap this range? Scanning every range is slow when there are many. intervaltree stores ranges in a balanced tree so these queries are fast.

Intervals are half-open: [begin, end) includes the start and excludes the end. So 9:10 ends exactly when 10:13 would begin, and the two do not overlap.

Python Meeting overlaps with IntervalTree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare day[9.5] (point query: "who is active now?"), day[10:13] (overlap query), envelop(a, b) (ranges completely inside) and overlaps(a, b) (a yes or no). Each stored item is an Interval(begin, end, data) that you can sort and unpack.

pygtrie: prefix trees

A trie (prefix tree) stores keys character by character, so all keys sharing a prefix share a path. That makes "everything starting with car" cheap, because you walk to the car node and list what is below it. Tries power autocomplete, spell suggestions, IP routing and URL routers. pygtrie offers CharTrie (keys are strings), StringTrie (keys are split on a separator such as /) and Trie (any sequence).

Python Autocomplete and URL routing with pygtrie

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

longest_prefix returns a small object with .key and .value (or a falsy "no match" object), which is exactly what a router wants: the most specific rule that matches the start of the path. Tries trade memory for speed, since each character costs a node, so for a few hundred words a plain sorted list with bisect is fine, and the trie pays off with large vocabularies and frequent prefix queries.

Choosing and combining

Need Built-in answer Library answer
Sorted data with fast inserts list + bisect.insort SortedList, SortedDict
Top-k or smallest item only heapq heapq is enough
Hierarchy (parent and children) Nested dicts treelib.Tree
Does a point fall in a range? Loop over ranges IntervalTree
Autocomplete by prefix sorted + bisect pygtrie
Count things collections.Counter Built-in is enough

Before adding a dependency, ask three questions. Is the built-in tool (like heapq for "give me the smallest") enough? Is the library maintained and tested? Are you comfortable with the extra install in production? A good rule is to measure first: if a list of a few thousand items sorted in place works, you do not need more.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which method adds an item to a SortedList?

    SortedList.add(item) puts the value in its sorted position. There is no append because the position is decided by the value, not by the caller.
  2. 2. In IntervalTree, do 9:10 and 10:13 overlap?

    The start is included and the end is excluded, so back-to-back intervals do not overlap. This avoids double-counting boundaries.
  3. 3. What is the difference between a treelib node's tag and its identifier?

    Methods such as children, subtree and remove_node use the unique id. The tag is what show() prints and can be duplicated.
  4. 4. Which task is a trie especially good at?

    Keys that share a prefix share a path, so you walk to the prefix node and list everything below it.
  5. 5. Which is the best first step before adding a data-structure library to a project?

    Built-ins are free of dependencies. Add a library when you have a real need, such as a collection that must stay sorted under many inserts.

Summary

  • sortedcontainers (SortedList, SortedDict, SortedSet) keep data ordered after every change and support bisect_*, irange and positional access.
  • treelib models hierarchies with unique node ids, tags, traversal, subtrees and a readable show().
  • intervaltree answers point and range overlap queries on half-open intervals; merge_overlaps and envelop handle busy-time style problems.
  • pygtrie provides prefix trees: prefix key listing, longest_prefix and StringTrie for path-like keys.
  • Prefer built-ins when they are enough, and measure before adding a dependency.

Next: Time Complexity of Python Types.