Course contentsShow
← Computer Science
Lesson 631 of 2,87215. Tries and Specialized TreesFree lesson

Compressed Tries (Radix Trees)

Learn how compressed tries merge single-child chains into edges to reduce space and improve traversal efficiency.

Compressed Tries (Radix Trees)

You'll learn how compressed tries optimize space by merging chains of single-child nodes into single edges.

The Problem with Standard Tries

In a standard trie, long words with unique suffixes create long chains where each node has exactly one child. For example, storing "cat", "catapult", and "catastrophe" creates many nodes where the path from "cat" onward is just a linear chain with no branching. This wastes memory and requires many pointer traversals.

What is a Compressed Trie?

A compressed trie (also called a radix tree or Patricia trie) merges these single-child chains into a single edge labeled with multiple characters. Instead of having separate nodes for 'c' → 'a' → 't' → 'a' → 'p', you'd have one edge labeled "catap" leading to the next branch point.

How It Works

When inserting words, the trie only creates branch nodes where paths diverge. Each edge stores a string (not just a character). When searching:

  • You match edge labels in chunks, not character-by-character
  • If an edge partially matches, you may need to split it to insert a new word

Example: Storing "cat", "catapult", "dog"

  • Root has two edges: "cat" and "dog"
  • The "cat" node has one child edge: "apult"
  • This requires only 3 nodes instead of 11 in a standard trie

Benefits

  • Space efficiency: Fewer nodes, especially for sparse dictionaries
  • Faster traversal: Skipping over single-child chains means fewer pointer dereferences
  • Better cache performance: Less memory access improves real-world speed

Key Takeaway: Compressed tries merge single-child node chains into multi-character edges, dramatically reducing memory usage and improving traversal speed while maintaining all the search capabilities of standard tries.