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

Patricia Tries (PATRICIA)

Understand Practical Algorithm to Retrieve Information Coded in Alphanumeric, a space-efficient binary trie variant.

Patricia Tries (PATRICIA)

What You'll Learn

You'll learn how PATRICIA (Practical Algorithm to Retrieve Information Coded in Alphanumeric) optimizes radix trees by skipping single-child paths and storing skip counts.

The Core Idea

Recall that radix trees already compress chains of single-child nodes into edges. PATRICIA takes this further with a clever twist: instead of storing full strings on edges, it stores bit positions to skip and only checks characters when absolutely necessary.

Think of it like giving directions: instead of saying "walk down every single house on the street," you say "skip 15 houses, then turn." PATRICIA does the same with string characters—it jumps over sections where no branching decision is needed.

How It Works

In a traditional trie or radix tree, you might store partial strings along edges. PATRICIA stores:

  • Skip count: how many bits/characters to jump forward
  • Only the critical branching character where paths diverge

When searching, you leap forward by the skip count and check only that one position. If it matches, continue; if not, the word isn't in the trie.

Space Efficiency Boost

Because PATRICIA nodes store integers (skip counts) rather than string fragments, memory usage drops significantly. You're trading string storage for small integers, making PATRICIA especially efficient for large alphabets or long common prefixes.

Comparison to Radix Trees

While radix trees compress paths, they still store the actual character sequences. PATRICIA abstracts this to positional arithmetic—more compact, but requires bit-level thinking during implementation.

Key Takeaway: PATRICIA tries optimize radix trees by replacing edge strings with skip counts, checking only critical character positions to achieve excellent space efficiency for alphanumeric data retrieval.