28.06Intermediate / Advanced4 topics14 min3 interactive animations

Compressed tries

Compressed tries store whole strings on edges (radix trees), skip bits (Patricia tries) or split three ways (ternary search trees) to cut the number of nodes.

Learning goals

Build a radix tree by splitting edges where words diverge
Explain the critical-bit idea behind Patricia tries
Insert into and search a ternary search tree
Compare node counts of plain tries and compressed tries

Prerequisites

Trie implementationBinary search trees

A plain trie often contains long chains of nodes with one child each, one node per letter of a unique tail. Compression collapses each chain into a single edge, so the tree has a node only where something happens: a branch or a word end.

28.06.1

Radix tree

A **radix tree** (compressed trie) stores a whole string on each edge. A node exists only where words branch or end, so a tree with w words has at most 2w nodes however long the words are. Insertion follows an edge as far as its label matches; if the word leaves the label partway, the edge is split there, and the rest of the word becomes a new leaf.

Run the preset "Radix: splits on a shared prefix" (test team toast tea). test becomes one edge; team shares te and splits it; toast splits at t; tea ends exactly on an existing node and just sets the word flag. The finished tree has 6 nodes besides the root where the plain trie needs 10.

Java

1class RadixTree {
2    private static class Node {
3        String label = "";                       // the string on the edge from the parent
4        Map<Character, Node> kids = new TreeMap<>();
5        boolean end;
6    }
7    private final Node root = new Node();
8    private static int common(String a, String b) {
9        int k = 0;
10        while (k < a.length() && k < b.length() && a.charAt(k) == b.charAt(k)) k++;
11        return k;
12    }
13    void insert(String w) {
14        Node n = root;
15        while (!w.isEmpty()) {
16            Node child = n.kids.get(w.charAt(0));
17            if (child == null) {                 // no edge starts with this letter: add a leaf
18                Node leaf = new Node();
19                leaf.label = w;
20                leaf.end = true;
21                n.kids.put(w.charAt(0), leaf);
22                return;
23            }
24            int k = common(child.label, w);
25            if (k < child.label.length()) {      // split the edge where the words diverge
26                Node lower = new Node();
27                lower.label = child.label.substring(k);
28                lower.kids = child.kids;
29                lower.end = child.end;
30                child.label = child.label.substring(0, k);
31                child.kids = new TreeMap<>();
32                child.kids.put(lower.label.charAt(0), lower);
33                child.end = false;
34            }
35            n = child;
36            w = w.substring(k);
37        }
38        n.end = true;
39    }
40    boolean contains(String w) {
41        Node n = root;
42        while (!w.isEmpty()) {
43            Node child = n.kids.get(w.charAt(0));
44            if (child == null || !w.startsWith(child.label)) return false;
45            w = w.substring(child.label.length());
46            n = child;
47        }
48        return n.end;
49    }
50}

Radix tree (edge splitting) and ternary search tree

Interactive · edit the input

radix tree (each edge carries a string) · 1 node

root

Being followedNew or split nodeMatchMissingA word ends here

Setup

A radix tree stores a whole string on each edge instead of one letter, and a node exists only where words branch or end. Insertion follows an edge as far as the labels agree and splits it where they diverge.

Step 1 / 20

Java

1void insert(String w) {                                   // radix tree
2    Node n = root;
3    while (!w.isEmpty()) {
4        Node child = n.kids.get(w.charAt(0));
5        if (child == null) { n.kids.put(w.charAt(0), leaf(w)); return; }   // no edge starts with this letter
6        int k = commonPrefix(child.label, w);
7        if (k < child.label.length()) split(child, k);    // cut the edge where the words diverge
8        n = child; w = w.substring(k);
9    }
10    n.end = true;
11}
12Node insert(Node n, String w, int i) {                    // ternary search tree
13    char c = w.charAt(i);
14    if (n == null) n = new Node(c);
15    if (c < n.c) n.lo = insert(n.lo, w, i);               // smaller: left
16    else if (c > n.c) n.hi = insert(n.hi, w, i);          // larger: right
17    else if (i + 1 < w.length()) n.eq = insert(n.eq, w, i + 1);   // equal: next letter
18    else n.end = true;
19    return n;
20}
21boolean contains(String w) {
22    Node n = root; int i = 0;
23    while (n != null) {
24        char c = w.charAt(i);
25        if (c < n.c) n = n.lo;
26        else if (c > n.c) n = n.hi;
27        else if (++i == w.length()) return n.end;
28        else n = n.eq;
29    }
30    return false;
31}

Live state

0 radix nodes0 plain trie nodes

words

No condition evaluated on this step

Execution trace (dry run table)Show 20 steps

Step	Line	State	What happens
1	L1	words=4	A radix tree stores a whole string on each edge instead of one letter, and a node exists only where words branch or end. Insertion follows an edge as far as the labels agree and splits it where they diverge.
2	L5	word="test" edge="test"	No edge below the root starts with 't': add one leaf edge carrying the rest, "test".
3	L10	word="test" radix nodes=1 plain trie nodes=4	"test" inserted. A plain trie would now need 4 nodes; the radix tree has 1.
4	L6	edge="test" rest="team" common="te"	The edge "test" and "team" share only "te": split the edge there.
5	L7	upper="te" lower="st"	Split: "te" now ends at a new branching node, and "st" hangs below it.
6	L5	word="team" edge="am"	No edge below "te" starts with 'a': add one leaf edge carrying the rest, "am".
7	L10	word="team"	"team" ends exactly at an existing node: mark it as a word (no new node).
8	L10	word="team" radix nodes=3 plain trie nodes=6	"team" inserted. A plain trie would now need 6 nodes; the radix tree has 3.
9	L6	edge="te" rest="toast" common="t"	The edge "te" and "toast" share only "t": split the edge there.
10	L7	upper="t" lower="e"	Split: "t" now ends at a new branching node, and "e" hangs below it.
11	L5	word="toast" edge="oast"	No edge below "t" starts with 'o': add one leaf edge carrying the rest, "oast".
12	L10	word="toast"	"toast" ends exactly at an existing node: mark it as a word (no new node).
13	L10	word="toast" radix nodes=5 plain trie nodes=10	"toast" inserted. A plain trie would now need 10 nodes; the radix tree has 5.
14	L6	edge="t" rest="tea"	The whole edge "t" matches the start of "tea": follow it.
15	L6	edge="e" rest="ea"	The whole edge "e" matches the start of "ea": follow it.
16	L6	edge="am" rest="a" common="a"	The edge "am" and "a" share only "a": split the edge there.
17	L7	upper="a" lower="m"	Split: "a" now ends at a new branching node, and "m" hangs below it.
18	L10	word="tea"	"tea" ends exactly at an existing node: mark it as a word (no new node).
19	L10	word="tea" radix nodes=6 plain trie nodes=10	"tea" inserted. A plain trie would now need 10 nodes; the radix tree has 6.
20	L10	radix nodes=6 plain trie nodes=10	6 nodes besides the root instead of 10: every node is a word end or a real branching point, so there are at most 2 × words nodes. The characters are still stored once, on the edges.

28.06.2

Patricia trie

A **Patricia trie** (also called a crit-bit tree) applies the same compression to binary keys. Instead of storing bits on edges, each internal node stores the position of the first bit at which the keys below it differ, and keys are tested only at those positions. A tree of n keys has exactly n leaves and n - 1 internal nodes.

The core operation is finding the **critical bit** of two keys: the highest bit where they differ, which is the highest set bit of a ^ b. In a sorted list of keys, the critical bit between neighbours decides where the branches of the tree lie. The sketch below computes it; a full tree adds the branching and search around it, which this course does not implement.

Keys	a ^ b	Critical bit
1010 and 1000	0010	1
1010 and 0101	1111	3
0110 and 0111	0001	0

Java

1static int criticalBit(int a, int b) {           // highest bit where a and b differ (a != b)
2    return 31 - Integer.numberOfLeadingZeros(a ^ b);
3}
4static int[] criticalBits(int[] sortedKeys) {    // between neighbouring keys
5    int[] out = new int[Math.max(0, sortedKeys.length - 1)];
6    for (int i = 0; i + 1 < sortedKeys.length; i++) out[i] = criticalBit(sortedKeys[i], sortedKeys[i + 1]);
7    return out;
8}

28.06.3

Ternary search tree

A **ternary search tree** keeps one letter per node and three links: lo for letters smaller than the node's, hi for larger ones, and eq for the next letter of the word once this one matches. It is a binary search tree over the letters at each position combined with a trie over positions. Each node has 3 references instead of 26, so it is much smaller than the array trie.

Lookups cost O(L + log n) on average for a word of length L among n words, because every letter may need a few left or right moves. The animation's "Ternary: found", "Ternary: prefix only" and "Ternary: missing" presets show the three outcomes of a lookup: all letters matched and a word ends, all letters matched but no word ends, and a missing link. As with an unbalanced BST, the shape depends on the insertion order.

Java

1class TernaryTree {
2    private static class Node {
3        final char c;
4        Node lo, eq, hi;
5        boolean end;
6        Node(char c) { this.c = c; }
7    }
8    private Node root;
9    void insert(String w) { root = insert(root, w, 0); }
10    private Node insert(Node n, String w, int i) {
11        char c = w.charAt(i);
12        if (n == null) n = new Node(c);
13        if (c < n.c) n.lo = insert(n.lo, w, i);                      // smaller: left
14        else if (c > n.c) n.hi = insert(n.hi, w, i);                 // larger: right
15        else if (i + 1 < w.length()) n.eq = insert(n.eq, w, i + 1);  // equal: next letter
16        else n.end = true;
17        return n;
18    }
19    boolean contains(String w) {
20        Node n = root;
21        int i = 0;
22        while (n != null) {
23            char c = w.charAt(i);
24            if (c < n.c) n = n.lo;
25            else if (c > n.c) n = n.hi;
26            else if (++i == w.length()) return n.end;
27            else n = n.eq;
28        }
29        return false;
30    }
31}

Radix tree (edge splitting) and ternary search tree

Interactive · edit the input

radix tree (each edge carries a string) · 1 node

root

Being followedNew or split nodeMatchMissingA word ends here

Setup

Step 1 / 20

Java

1void insert(String w) {                                   // radix tree
2    Node n = root;
3    while (!w.isEmpty()) {
4        Node child = n.kids.get(w.charAt(0));
5        if (child == null) { n.kids.put(w.charAt(0), leaf(w)); return; }   // no edge starts with this letter
6        int k = commonPrefix(child.label, w);
7        if (k < child.label.length()) split(child, k);    // cut the edge where the words diverge
8        n = child; w = w.substring(k);
9    }
10    n.end = true;
11}
12Node insert(Node n, String w, int i) {                    // ternary search tree
13    char c = w.charAt(i);
14    if (n == null) n = new Node(c);
15    if (c < n.c) n.lo = insert(n.lo, w, i);               // smaller: left
16    else if (c > n.c) n.hi = insert(n.hi, w, i);          // larger: right
17    else if (i + 1 < w.length()) n.eq = insert(n.eq, w, i + 1);   // equal: next letter
18    else n.end = true;
19    return n;
20}
21boolean contains(String w) {
22    Node n = root; int i = 0;
23    while (n != null) {
24        char c = w.charAt(i);
25        if (c < n.c) n = n.lo;
26        else if (c > n.c) n = n.hi;
27        else if (++i == w.length()) return n.end;
28        else n = n.eq;
29    }
30    return false;
31}

Live state

0 radix nodes0 plain trie nodes

words

No condition evaluated on this step

Execution trace (dry run table)Show 20 steps

Step	Line	State	What happens
1	L1	words=4	A radix tree stores a whole string on each edge instead of one letter, and a node exists only where words branch or end. Insertion follows an edge as far as the labels agree and splits it where they diverge.
2	L5	word="test" edge="test"	No edge below the root starts with 't': add one leaf edge carrying the rest, "test".
3	L10	word="test" radix nodes=1 plain trie nodes=4	"test" inserted. A plain trie would now need 4 nodes; the radix tree has 1.
4	L6	edge="test" rest="team" common="te"	The edge "test" and "team" share only "te": split the edge there.
5	L7	upper="te" lower="st"	Split: "te" now ends at a new branching node, and "st" hangs below it.
6	L5	word="team" edge="am"	No edge below "te" starts with 'a': add one leaf edge carrying the rest, "am".
7	L10	word="team"	"team" ends exactly at an existing node: mark it as a word (no new node).
8	L10	word="team" radix nodes=3 plain trie nodes=6	"team" inserted. A plain trie would now need 6 nodes; the radix tree has 3.
9	L6	edge="te" rest="toast" common="t"	The edge "te" and "toast" share only "t": split the edge there.
10	L7	upper="t" lower="e"	Split: "t" now ends at a new branching node, and "e" hangs below it.
11	L5	word="toast" edge="oast"	No edge below "t" starts with 'o': add one leaf edge carrying the rest, "oast".
12	L10	word="toast"	"toast" ends exactly at an existing node: mark it as a word (no new node).
13	L10	word="toast" radix nodes=5 plain trie nodes=10	"toast" inserted. A plain trie would now need 10 nodes; the radix tree has 5.
14	L6	edge="t" rest="tea"	The whole edge "t" matches the start of "tea": follow it.
15	L6	edge="e" rest="ea"	The whole edge "e" matches the start of "ea": follow it.
16	L6	edge="am" rest="a" common="a"	The edge "am" and "a" share only "a": split the edge there.
17	L7	upper="a" lower="m"	Split: "a" now ends at a new branching node, and "m" hangs below it.
18	L10	word="tea"	"tea" ends exactly at an existing node: mark it as a word (no new node).
19	L10	word="tea" radix nodes=6 plain trie nodes=10	"tea" inserted. A plain trie would now need 10 nodes; the radix tree has 6.
20	L10	radix nodes=6 plain trie nodes=10	6 nodes besides the root instead of 10: every node is a word end or a real branching point, so there are at most 2 × words nodes. The characters are still stored once, on the edges.

28.06.4

Memory reduction

How much does compression save? For a set of words, a plain trie has one node per distinct non-empty prefix. A radix tree has a node only for prefixes that are a word or have two or more different next letters. The saving is largest for long words with unique tails and smallest for dense sets of short words.

Measured in the animation: test team toast tea needs 10 nodes in a plain trie and 6 in a radix tree, and romane romanus romulus rubens needs 17 and 7. The radix tree still stores every character once, on the edges, so the characters saved are the node overhead, not the text. Use the function below to count both for your own word list.

Java

1static int[] nodeCounts(List<String> words) {    // {plain trie nodes, radix tree nodes}, root not counted
2    Set<String> prefixes = new HashSet<>();
3    Set<String> wordSet = new HashSet<>(words);
4    Map<String, Set<Character>> kids = new HashMap<>();
5    for (String w : words) {
6        for (int i = 1; i <= w.length(); i++) {
7            prefixes.add(w.substring(0, i));
8            kids.computeIfAbsent(w.substring(0, i - 1), k -> new HashSet<>()).add(w.charAt(i - 1));
9        }
10    }
11    int radix = 0;
12    for (String p : prefixes) {                  // a node survives if a word ends there or the words branch there
13        if (wordSet.contains(p) || kids.getOrDefault(p, Set.of()).size() >= 2) radix++;
14    }
15    return new int[]{prefixes.size(), radix};
16}

Radix tree (edge splitting) and ternary search tree

Interactive · edit the input

radix tree (each edge carries a string) · 1 node

root

Being followedNew or split nodeMatchMissingA word ends here

Setup

Step 1 / 20

Java

1void insert(String w) {                                   // radix tree
2    Node n = root;
3    while (!w.isEmpty()) {
4        Node child = n.kids.get(w.charAt(0));
5        if (child == null) { n.kids.put(w.charAt(0), leaf(w)); return; }   // no edge starts with this letter
6        int k = commonPrefix(child.label, w);
7        if (k < child.label.length()) split(child, k);    // cut the edge where the words diverge
8        n = child; w = w.substring(k);
9    }
10    n.end = true;
11}
12Node insert(Node n, String w, int i) {                    // ternary search tree
13    char c = w.charAt(i);
14    if (n == null) n = new Node(c);
15    if (c < n.c) n.lo = insert(n.lo, w, i);               // smaller: left
16    else if (c > n.c) n.hi = insert(n.hi, w, i);          // larger: right
17    else if (i + 1 < w.length()) n.eq = insert(n.eq, w, i + 1);   // equal: next letter
18    else n.end = true;
19    return n;
20}
21boolean contains(String w) {
22    Node n = root; int i = 0;
23    while (n != null) {
24        char c = w.charAt(i);
25        if (c < n.c) n = n.lo;
26        else if (c > n.c) n = n.hi;
27        else if (++i == w.length()) return n.end;
28        else n = n.eq;
29    }
30    return false;
31}

Live state

0 radix nodes0 plain trie nodes

words

No condition evaluated on this step

Execution trace (dry run table)Show 20 steps

Step	Line	State	What happens
1	L1	words=4	A radix tree stores a whole string on each edge instead of one letter, and a node exists only where words branch or end. Insertion follows an edge as far as the labels agree and splits it where they diverge.
2	L5	word="test" edge="test"	No edge below the root starts with 't': add one leaf edge carrying the rest, "test".
3	L10	word="test" radix nodes=1 plain trie nodes=4	"test" inserted. A plain trie would now need 4 nodes; the radix tree has 1.
4	L6	edge="test" rest="team" common="te"	The edge "test" and "team" share only "te": split the edge there.
5	L7	upper="te" lower="st"	Split: "te" now ends at a new branching node, and "st" hangs below it.
6	L5	word="team" edge="am"	No edge below "te" starts with 'a': add one leaf edge carrying the rest, "am".
7	L10	word="team"	"team" ends exactly at an existing node: mark it as a word (no new node).
8	L10	word="team" radix nodes=3 plain trie nodes=6	"team" inserted. A plain trie would now need 6 nodes; the radix tree has 3.
9	L6	edge="te" rest="toast" common="t"	The edge "te" and "toast" share only "t": split the edge there.
10	L7	upper="t" lower="e"	Split: "t" now ends at a new branching node, and "e" hangs below it.
11	L5	word="toast" edge="oast"	No edge below "t" starts with 'o': add one leaf edge carrying the rest, "oast".
12	L10	word="toast"	"toast" ends exactly at an existing node: mark it as a word (no new node).
13	L10	word="toast" radix nodes=5 plain trie nodes=10	"toast" inserted. A plain trie would now need 10 nodes; the radix tree has 5.
14	L6	edge="t" rest="tea"	The whole edge "t" matches the start of "tea": follow it.
15	L6	edge="e" rest="ea"	The whole edge "e" matches the start of "ea": follow it.
16	L6	edge="am" rest="a" common="a"	The edge "am" and "a" share only "a": split the edge there.
17	L7	upper="a" lower="m"	Split: "a" now ends at a new branching node, and "m" hangs below it.
18	L10	word="tea"	"tea" ends exactly at an existing node: mark it as a word (no new node).
19	L10	word="tea" radix nodes=6 plain trie nodes=10	"tea" inserted. A plain trie would now need 10 nodes; the radix tree has 6.
20	L10	radix nodes=6 plain trie nodes=10	6 nodes besides the root instead of 10: every node is a word end or a real branching point, so there are at most 2 × words nodes. The characters are still stored once, on the edges.

Practice ladder

Now try it yourself

Easy

Longest Common Prefix
Short Encoding of Words

Medium

Implement Trie (Prefix Tree)
Replace Words

Advanced

Stream of Characters
Longest Duplicate Substring

Key takeaways

A radix tree has a node only where words branch or end: at most 2 × words nodes.
Patricia tries test only the critical bit, the highest bit where neighbouring keys differ.
A ternary search tree uses three links per node instead of an alphabet-sized array.