Patricia Trie (Radix Tree / PATRICIA)

What is Patricia Trie

PATRICIA — Practical Algorithm To Retrieve Information Coded In Alphanumeric.
Proposed by Donald R. Morrison in 1968.

Patricia Trie = a compressed Trie where chains of nodes with a single child are compressed into a single edge with a label (a string instead of a single character). This solves the primary problem of a standard Trie — redundant nodes.

Key Idea: Path Compression

Standard Trie for "interview", "internal", "intro":

root → i → n → t → e → r → v → i → e → w ✓
                          ↘ n → a → l ✓
               ↘ r → o ✓

Patricia Trie:

root → "int" → "er" → "view" ✓
                    ↘ "nal"  ✓
            ↘ "ro"  ✓

Visualization

Words: cat, car, card, care, bat, bad

Each edge now carries a string instead of a single character.

Node Structure

┌──────────────────────────────────────┐
│  children: map<string → Node>        │  ← edge key — string (label)
│  is_end: bool                        │
│  value: any                          │
└──────────────────────────────────────┘

Basic Operations

➕ Insertion — O(m)

Three situations are possible during insertion:

Case 1: Label matches exactly

Edge "car" exists, insert "car" → just set is_end = true

Case 2: New word is a prefix of the label

Edge "card" exists, insert "car":
  Split "card" → "car" (is_end=true) + "d" (is_end=true, child)

Case 3: Need to split the label

Edge "card" exists, insert "care":
  Common prefix: "car"
  Split → "car" → "d" ✓
                 ↘ "e" ✓

def insert(node, word):
    for label, child in node.children.items():
        common = longest_common_prefix(label, word)
        if not common:
            continue
        if common == label:                  # case 1/2
            insert(child, word[len(common):])
        else:                                # case 3 — split
            split_node = Node()
            split_node.children[label[len(common):]] = child
            node.children[common] = split_node
            node.children.pop(label)
            if word == common:
                split_node.is_end = True
            else:
                split_node.children[word[len(common):]] = Node(is_end=True)
        return
    node.children[word] = Node(is_end=True)  # new branch

🔍 Search — O(m)

Searching for "care" in Patricia Trie:
  root: check child labels
  Matches "ca" → proceed, remainder "re"
  Matches "r"  → proceed, remainder "e"
  Matches "e"  → proceed, remainder ""
  is_end = true  → FOUND ✓

➖ Deletion — O(m)

After deleting a node — merge the parent with the single remaining child:

Delete "card", only "care" remains:
  Node "car" → {"d": ✓, "e": ✓}
  After deleting "d":
  Node "car" → {"e": ✓}  →  collapse into "care" ✓

Trie vs Patricia Trie — Comparison

{
  "title": { "text": "Node Count: Trie vs Patricia", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["Trie", "Patricia Trie"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "name": "Number of Words",
    "data": ["10", "50", "100", "500", "1000"]
  },
  "yAxis": {
    "type": "value",
    "name": "Nodes (approximate)"
  },
  "series": [
    {
      "name": "Trie",
      "type": "line",
      "data": [60, 310, 650, 3400, 7000],
      "smooth": true,
      "lineStyle": { "color": "#d9534f", "width": 3 }
    },
    {
      "name": "Patricia Trie",
      "type": "line",
      "data": [19, 99, 199, 999, 1999],
      "smooth": true,
      "lineStyle": { "color": "#5cb85c", "width": 3 }
    }
  ]
}

Variants and Applications

Radix Tree (Radix Trie)

A generalization of Patricia Trie — compression by bit groups (radix 2, 4, 8...).
Used in the Linux kernel for process address space storage.

Where Patricia / Radix Tree is Used

Final Comparison of All Three Structures

BST vs Binary Heap

Main Question

Both structures are binary trees with ordered elements. But they solve different problems and have fundamentally different invariants.

Invariant — Key Difference

Same Array — Two Different Trees

Data: [20, 30, 40, 50, 60, 70, 80]

BST degenerates into a list — O(n) for all operations.
Heap always remains a complete tree — guaranteed O(log n).

Detailed Operation Comparison

🔍 Arbitrary Search

BST — Searching for 40:
  50 → 30 → 40 ✓   (3 steps = O(log n))

  Each step discards half the tree —
  left or right subtree

Heap — Searching for 40:
  80 → check 70 and 60
     → check 50, 40... ✓  but could have gone right as well

  No horizontal order info —
  must traverse entire tree in worst case

Conclusion: BST wins — O(log n) vs O(n)

🏆 Get Max / Min

Max-Heap — Get Max:
  return heap[0]   ← root, O(1) ✓

BST — Get Max:
  traverse right children to the end
  O(log n) for balanced
  O(n) for degenerate

Min-Heap — Get Min:
  return heap[0]   ← O(1) ✓

BST — Get Min:
  traverse left children to the end
  O(log n) / O(n)

Conclusion: Heap wins — O(1) vs O(log n)

➕ Insertion

BST — Insert 45:
  50 → 30 → 40 → right child empty → insert
  But! May require rebalancing (AVL/RB)

Heap — Insert 45:
  Add to end of array → sift up
  Guaranteed O(log n), no complex rebalancing

➖ Deletion

Heap — Arbitrary Deletion:
  1. Must FIND the element → O(n)
  2. Only then delete → O(log n)
  Total: O(n) — inefficient!

  Root Removal (min/max) — O(log n) ✓

BST — Arbitrary Deletion:
  1. Find → O(log n)
  2. Delete (3 cases) → O(log n)
  Total: O(log n) ✓

Conclusion: BST wins for arbitrary deletion

📊 Memory Storage

Heap → Array (ideal):

  Index:  0   1   2   3   4   5   6
  Data:  [80, 70, 60, 50, 40, 30, 20]

  parent(i) = (i-1) / 2
  left(i)   = 2*i + 1
  right(i)  = 2*i + 2

  ✅ No pointers
  ✅ Cache-friendly
  ✅ Minimal memory

BST → Nodes with pointers:

  Node { key, left*, right*, parent* }

  ❌ Each node = separate allocation
  ❌ Pointers = extra memory
  ❌ Cache misses during traversal

Complexity Visual Comparison

{
  "title": { "text": "Operation Comparison: BST vs Binary Heap", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["BST (balanced)", "Binary Heap"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "data": ["Arbitrary Search", "Min/Max", "Insertion", "Delete Min/Max", "Arbitrary Deletion", "Construction"]
  },
  "yAxis": {
    "type": "value",
    "name": "Relative Complexity (n=1000)",
    "max": 1100
  },
  "series": [
    {
      "name": "BST (balanced)",
      "type": "bar",
      "data": [10, 10, 10, 10, 10, 10000],
      "itemStyle": { "color": "#5b9bd5" },
      "label": {
        "show": true,
        "position": "top",
        "formatter": ["O(log n)", "O(log n)", "O(log n)", "O(log n)", "O(log n)", "O(n log n)"]
      }
    },
    {
      "name": "Binary Heap",
      "type": "bar",
      "data": [1000, 1, 10, 10, 1000, 1000],
      "itemStyle": { "color": "#f0ad4e" },
      "label": {
        "show": true,
        "position": "top",
        "formatter": ["O(n)", "O(1)", "O(log n)", "O(log n)", "O(n)", "O(n)"]
      }
    }
  ]
}

Final Summary Table

When to Choose What

Typical Scenarios

Standard Library Implementations

Summary

┌─────────────────────────────────────────────────────┐
│                                                     │
│  Heap  = Min/Max Specialist                         │
│          "Give me the largest/smallest — fast"      │
│          O(1) for the main operation                │
│                                                     │
│  BST   = Universal Ordered Dictionary               │
│          "Find, insert, delete anything"            │
│          O(log n) for everything, full order        │
│                                                     │
└─────────────────────────────────────────────────────┘