Prefix Tries, Compressed Radix Trees & PATRICIA Trees

1. From Uncompressed Tries to Compressed Radix Trees & PATRICIA

Let $\mathcal{S} = \{s_1, s_2, \dots, s_N\}$ be a set of $N$ distinct strings of total length $M = \sum |s_i|$. Compare the three structural representations:

• Uncompressed Trie: Up to $M + 1$ nodes. Every character transition is an explicit node. Long unique keys create deep chains of degree-1 nodes that cause $L$ sequential L3/DRAM cache misses.
• Compressed Radix Tree (Compact Prefix Tree): Every internal node must have branching degree $\ge 2$ (unless it marks the end of a key). Any unary chain is collapsed into a single edge storing a string slice $(k, \text{offset}, \text{len})$. Because every internal node branches at least two ways, a Radix Tree over $N$ keys has at most $2N$ nodes ($N$ leaves and $\le N - 1$ branching nodes)!
• PATRICIA Tree (Practical Algorithm To Retrieve Information Coded In Alphanumeric): Stores keys only at the leaves; each internal node stores only the critical bit/byte position $d$ where its subtrees diverge. During search(q), the traversal skips intermediary bytes completely and only inspects q[d] at each internal node, performing a single full key comparison at the reached leaf to verify whether the skipped prefix segments actually match!

2. Production Implementation: Compressed Radix Tree (Insert, Exact Lookup & Prefix Enumeration)

class RadixNode {
  constructor(edgeLabel = "", value = undefined) {
    this.edgeLabel = edgeLabel;
    this.value = value; // !== undefined if a key terminates at this node
    this.children = new Map(); // firstChar -> RadixNode
  }
}

/**
 * Compressed Radix Tree (Compact Prefix Tree)
 * Guarantees at most 2N nodes regardless of string length L.
 */
class RadixTree {
  constructor() {
    this.root = new RadixNode("");
    this.size = 0;
  }

  _lcpLength(a, b) {
    const len = Math.min(a.length, b.length);
    let i = 0;
    while (i < len && a.charCodeAt(i) === b.charCodeAt(i)) i++;
    return i;
  }

  insert(key, value = true) {
    let curr = this.root;
    let i = 0;
    while (i < key.length) {
      const ch = key[i];
      const child = curr.children.get(ch);
      if (!child) {
        curr.children.set(ch, new RadixNode(key.slice(i), value));
        this.size++;
        return;
      }
      const rem = key.slice(i);
      const lcp = this._lcpLength(rem, child.edgeLabel);
      if (lcp === child.edgeLabel.length) {
        // Consumed entire child edge; continue descending
        curr = child;
        i += lcp;
      } else {
        // Split child edge at index lcp
        const splitNode = new RadixNode(child.edgeLabel.slice(0, lcp));
        curr.children.set(ch, splitNode);

        child.edgeLabel = child.edgeLabel.slice(lcp);
        splitNode.children.set(child.edgeLabel[0], child);

        if (lcp === rem.length) {
          splitNode.value = value;
        } else {
          const newLeaf = new RadixNode(rem.slice(lcp), value);
          splitNode.children.set(newLeaf.edgeLabel[0], newLeaf);
        }
        this.size++;
        return;
      }
    }
    if (curr.value === undefined) this.size++;
    curr.value = value;
  }

  get(key) {
    let curr = this.root;
    let i = 0;
    while (i < key.length) {
      const child = curr.children.get(key[i]);
      if (!child) return undefined;
      const label = child.edgeLabel;
      if (key.length - i < label.length) return undefined;
      for (let j = 0; j < label.length; j++) {
        if (key.charCodeAt(i + j) !== label.charCodeAt(j)) return undefined;
      }
      curr = child;
      i += label.length;
    }
    return curr.value;
  }

  keysWithPrefix(prefix) {
    let curr = this.root;
    let i = 0;
    let accumulated = "";
    while (i < prefix.length) {
      const child = curr.children.get(prefix[i]);
      if (!child) return [];
      const rem = prefix.slice(i);
      const lcp = this._lcpLength(rem, child.edgeLabel);
      if (lcp < rem.length && lcp < child.edgeLabel.length) return [];
      accumulated += child.edgeLabel;
      curr = child;
      i += lcp;
    }
    const results = [];
    const dfs = (node, path) => {
      if (node.value !== undefined) results.push(path);
      for (const child of node.children.values()) {
        dfs(child, path + child.edgeLabel);
      }
    };
    dfs(curr, accumulated);
    return results;
  }
}

3. Complexity Matrix