Why this matters
A plain trie stores one node for every letter of every word. That makes it easy to follow, but it costs memory. A word of 13 letters takes 13 nodes below the root, and most of those nodes have only one child. Nothing branches there, so the node only passes the reader on to the next letter.
A radix tree removes that waste. It is a trie in which each run of single-child nodes becomes one edge, and the edge carries a label of several letters. The tree then has fewer nodes, and the same words are still stored. Radix trees are used for IP routing tables and for some search indexes. This lesson shows how to make one from a plain trie, which nodes to keep and why, and how many nodes a real word list saves.
The lesson uses the trie with end flags from earlier in this module. It does not build a radix tree from scratch with inserts that split edges. That is the hard part of a real radix tree, and it is outside the scope here. We build the compressed form from a finished plain trie.
Start with a plain trie that has chains
Take four words: car, card, care and cat. A plain trie for them has seven nodes, counting the root. Here is the shape:
- The root has one child, for the letter "c".
- "c" has one child, for the letter "a". Nothing branches at "c".
- "ca" has two children, "r" and "t". The word continues in two ways, so "ca" is a branch.
- "car" is a word, and it has two children, "d" and "e".
- "card" and "care" are words with no children.
- "cat" is a word with no children.
The node for "c" is in a chain. A chain is a run of nodes where each has exactly one child and none of them ends a word. The chain from the root to "ca" has one node in the middle, "c". A radix tree can remove that node and put its letter into the edge label. The edge from the root then reads "ca" in one step, not "c" and then "a".
The rule: which nodes to keep
Each node in the plain trie falls into one of three groups. A radix tree keeps the first two groups and merges the third.
- The root. It is always kept, because it is where the tree starts.
- A word end. A node where a stored word ends must be kept, even when it has one child. Otherwise the tree cannot say that the word is stored.
- A branch. A node with two or more children must be kept, because the tree needs a place where the paths split.
Every other node has exactly one child and does not end a word. Such a node is merged into the edge that runs through it. Its letter joins the label.
In the four words above, the kept nodes are the root, "ca" (a branch), "car" (a word end and a branch), "card" (a word end), "care" (a word end) and "cat" (a word end). That is six nodes. The one node not kept is "c". So the radix tree has six nodes, and the plain trie had seven.
Here is what the program in this lesson prints for those four words:
plain trie nodes: 7
radix nodes: 6
label letters: 6
ca
r (word)
d (word)
e (word)
t (word)Each line is one edge. The first line, "ca", is the edge from the root. The indentation shows the depth. The text "(word)" shows that a stored word ends at the node at the end of that edge. The line "r (word)" is the edge from "ca" to "car", so the word "car" is stored. The lines below it are the edges to "card" and "care". The line "t (word)" is the edge to "cat".
The count "label letters" is the total number of letters across all edge labels. It is 6 here, and the plain trie had 7 nodes including the root. The root holds no letter, so that matches: each of the other six nodes holds one letter. The letters did not disappear. They moved from separate nodes into the labels. This fact matters later.
Worked example 1: one long word
Take a single word, "international", which has 13 letters. The plain trie has 14 nodes: the root and one node for each letter. Every node except the last has exactly one child, and none of them is a word end. So all of them merge into one edge. The last node is a word end, so it is kept. The root is kept too.
plain trie nodes: 14
radix nodes: 2
label letters: 13
international (word)The radix tree has two nodes and one edge. The edge carries the whole word as its label. This is the best case: the tree is almost as small as the word itself.
Worked example 2: words that share a start
Now take the words information, informer, informal, inform, internal, international, interval, intern, interest and interior. These share the start "in" and "inter", and then split into different endings. Here is the output of the program:
plain trie nodes: 36
radix nodes: 15
label letters: 35
in
form (word)
a
l (word)
tion (word)
er (word)
ter
est (word)
ior (word)
n (word)
a
l (word)
tional (word)
val (word)Read the tree from the top. The edge "in" leads to a node that is not a word. Its children are "form" and "ter". The edge "form" ends the word "inform". From "form", the edge "a" leads to a branch that splits into "l" (the word informal) and "tion" (the word information). The edge "er" ends "informer".
The edge "ter" leads to a branch with four children: "est", "ior", "n" and "val". The edge "n" ends "intern" and then continues to "internal" and "international". So the tree shows "inter" as a shared start for several words, and it shows which parts are unique.
The count is 36 plain nodes and 15 radix nodes. That is 21 nodes fewer. The label letters are 35, which is the 36 plain nodes minus the root. Again, the letters are all still there.
The method in code
The steps are short. First, decide for each node whether it is kept, using the rule above. Second, for each kept node, follow each child edge until the next kept node, and collect the letters on the way. That collected string is the edge label. The count of letters is the total length of all labels.
The function that decides whether a node is kept is short:
bool is_kept(const std::vector<Node>& nodes, int id) {
return id == 0 || nodes[id].is_end || child_count(nodes[id]) != 1;
}The printing function follows each edge through the nodes that are not kept, and appends their letters to the label:
while (!is_kept(nodes, cur)) {
for (int j = 0; j < 26; ++j) {
if (nodes[cur].next[j] != 0) {
label.push_back(static_cast<char>('a' + j));
cur = nodes[cur].next[j];
break;
}
}
}A node that is not kept has exactly one child, so the inner loop finds that child and stops. The loop ends when it reaches a kept node. The label then holds every letter of the merged chain.
Here is the whole program. It has a plain trie, the kept-node rule, the printing, the counting, and a table over a word list file. Save it as radix.cpp.
#include <array>
#include <cstddef>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
struct Node {
std::array<int, 26> next{}; // child index per letter; 0 means no child
bool is_end = false; // a stored word ends here
};
class PlainTrie {
public:
PlainTrie() : nodes_(1) {} // node 0 is the root
void insert(std::string_view word) {
int cur = 0;
for (char c : word) {
int i = c - 'a';
if (nodes_[cur].next[i] == 0) {
nodes_[cur].next[i] = static_cast<int>(nodes_.size());
nodes_.emplace_back();
}
cur = nodes_[cur].next[i];
}
nodes_[cur].is_end = true;
}
const std::vector<Node>& nodes() const { return nodes_; }
private:
std::vector<Node> nodes_;
};
int child_count(const Node& n) {
int count = 0;
for (int c : n.next) {
if (c != 0) ++count;
}
return count;
}
// A node stays in the radix tree if it is the root, if a word ends there,
// or if it has two or more children. Any other node has exactly one child
// and is merged into the edge that runs through it.
bool is_kept(const std::vector<Node>& nodes, int id) {
return id == 0 || nodes[id].is_end || child_count(nodes[id]) != 1;
}
// Prints one line per radix edge: its label, and "(word)" if it ends a word.
void print_radix(const std::vector<Node>& nodes, int id, int depth) {
for (int i = 0; i < 26; ++i) {
int child = nodes[id].next[i];
if (child == 0) continue;
std::string label(1, static_cast<char>('a' + i));
int cur = child;
while (!is_kept(nodes, cur)) {
for (int j = 0; j < 26; ++j) {
if (nodes[cur].next[j] != 0) {
label.push_back(static_cast<char>('a' + j));
cur = nodes[cur].next[j];
break;
}
}
}
std::cout << std::string(static_cast<std::size_t>(depth) * 2, ' ')
<< label << (nodes[cur].is_end ? " (word)" : "") << '\n';
print_radix(nodes, cur, depth + 1);
}
}
struct Stats {
std::size_t plain_nodes = 0; // nodes in the plain trie, root included
std::size_t radix_nodes = 0; // nodes kept in the radix tree, root included
std::size_t label_letters = 0; // letters stored across all radix edge labels
};
// Walks every kept node and follows each of its edges to the next kept node,
// counting the letters on the way.
Stats measure(const std::vector<Node>& nodes) {
Stats s;
s.plain_nodes = nodes.size();
for (std::size_t id = 0; id < nodes.size(); ++id) {
if (!is_kept(nodes, static_cast<int>(id))) continue;
++s.radix_nodes;
for (int i = 0; i < 26; ++i) {
int cur = nodes[id].next[i];
if (cur == 0) continue;
++s.label_letters;
while (!is_kept(nodes, cur)) {
for (int j = 0; j < 26; ++j) {
if (nodes[cur].next[j] != 0) {
cur = nodes[cur].next[j];
++s.label_letters;
break;
}
}
}
}
}
return s;
}
int main(int argc, char** argv) {
if (argc == 1) {
PlainTrie t;
for (std::string_view w : {"car", "card", "care", "cat"}) t.insert(w);
Stats s = measure(t.nodes());
std::cout << "plain trie nodes: " << s.plain_nodes << "\n";
std::cout << "radix nodes: " << s.radix_nodes << "\n";
std::cout << "label letters: " << s.label_letters << "\n";
print_radix(t.nodes(), 0, 0);
return 0;
}
if (std::string(argv[1]) == "--tree") {
PlainTrie t;
for (int k = 2; k < argc; ++k) t.insert(argv[k]);
Stats s = measure(t.nodes());
std::cout << "plain trie nodes: " << s.plain_nodes << "\n";
std::cout << "radix nodes: " << s.radix_nodes << "\n";
std::cout << "label letters: " << s.label_letters << "\n";
print_radix(t.nodes(), 0, 0);
return 0;
}
std::ifstream in(argv[1]);
std::vector<std::string> words;
std::string w;
while (in >> w) words.push_back(w);
std::cout << "words plain radix saved saved% label_letters\n";
for (std::size_t n : {10, 100, 1000, 5000}) {
if (n > words.size()) break;
PlainTrie t;
for (std::size_t k = 0; k < n; ++k) t.insert(words[k]);
Stats s = measure(t.nodes());
std::size_t saved = s.plain_nodes - s.radix_nodes;
double pct = 100.0 * static_cast<double>(saved) / static_cast<double>(s.plain_nodes);
std::cout << std::setw(5) << n << std::setw(7) << s.plain_nodes
<< std::setw(7) << s.radix_nodes << std::setw(7) << saved
<< std::setw(8) << std::fixed << std::setprecision(1) << pct
<< std::setw(15) << s.label_letters << "\n";
std::cout.unsetf(std::ios::fixed);
}
return 0;
}Compile it and run the small example, a tree for a few words, and a word list file:
g++ -std=c++20 -Wall -Wextra -o radix radix.cpp
./radix
./radix --tree tomato tomatoes
./radix words5000.txtThe table at the end of this lesson comes from the last command. The --tree mode prints the tree for the words given on the command line.
Counting on a real word list
The examples so far used words typed by hand. A better test uses a real list. The list here is the English Wikipedia word frequency list that comes with the zxcvbn password checker. It has about 30,000 entries, ordered by how often each word appears in Wikipedia text. The file used in this lesson holds the first 5,000 entries that are all lowercase letters. To make the same file, take the english_wikipedia list in lib/frequency_lists.js from the zxcvbn npm package, keep the entries that are all lowercase letters, and save the first 5,000 of them, one word per line. The program builds a plain trie from the first 10, 100, 1,000 and 5,000 words of that file.
The program takes a word list file as its argument, and prints one row for each size:
words plain radix saved saved% label_letters
10 23 15 8 34.8 22
100 299 134 165 55.2 298
1000 3328 1343 1985 59.6 3327
5000 15802 6737 9065 57.4 15801Each row has these columns:
words: how many of the first words were used.plain: nodes in the plain trie, including the root.radix: nodes kept in the radix tree, including the root.saved: plain minus radix, the number of nodes that were merged away.saved%: saved as a share of the plain nodes.label_letters: letters across all radix labels. It is always the plain count minus one.
The saved share is about 35 to 60 percent in every row. With 1,000 words, the radix tree has 1,343 nodes where the plain trie has 3,328. The saved share is 59.6 percent. It does not keep rising with the list size: it is 57.4 percent at 5,000 words, because a bigger list has more branch nodes, and branch nodes are kept.
The counts were checked with a separate Python script. It counts the distinct prefixes of the words, then counts the prefixes that are words or have two or more distinct next letters. The Python numbers match the table in every row.
What the saving means for memory
The program measures nodes, not bytes. Each node in this program holds an array of 26 integers and a flag. With g++ 15 on the machine used for this lesson, one node is 108 bytes. That was measured with a small program that printed sizeof(Node), the number of bytes C++ uses for one Node.
So for the 1,000-word row, the plain trie uses 3,328 times 108 bytes, which is 359,424 bytes. The radix tree uses 1,343 times 108 bytes, which is 145,044 bytes. The difference is 214,380 bytes, or about 209 KiB.
These numbers are only the node objects. They ignore the vector's spare capacity and any memory outside the nodes. A real radix tree also stores each label as a string, so its nodes are not all the same size. The saving on the labels depends on the design. The count of letters does not change, so a design that stores labels as copies of the words would pay for the letters again.
The saving therefore depends on the shape of the data. It is large when the words have long runs of letters that no other word shares. It is small when most nodes are branches or word ends. Take the two words a and b. The plain trie has three nodes: the root and two single-letter words. Both single-letter nodes are word ends, so both are kept. No node merges, and the saving is zero:
plain trie nodes: 3
radix nodes: 3
label letters: 2
a (word)
b (word)Common mistakes
Merging a word end into its child
The most common bug is to merge every single-child node, including the word ends. Take the words car and card. The node for "car" has one child, "d". If the rule ignores the word-end flag, "car" merges into the edge to "card". The tree then says only that "card" is stored.
The bug was tested by removing nodes[id].is_end || from is_kept and running the program on car and card. The output was:
plain trie nodes: 5
radix nodes: 2
label letters: 4
card (word)The correct output for the same two words is:
plain trie nodes: 5
radix nodes: 3
label letters: 4
car (word)
d (word)The buggy tree has two nodes and one edge, so it looks smaller. It is wrong, because the word "car" disappeared. The node count looks plausible, so a test has to check which words the tree still holds.
Expecting the letters to shrink
A reader may expect the radix tree to hold fewer letters in total. It does not. The letters are the same, and only the number of nodes changes. The "label_letters" column in the table is always one less than the plain node count, which shows that every letter is still stored once. If a design reports fewer letters, something has been lost.
Forgetting an include
The printing code uses std::setw to align the table. It is in the <iomanip> header. If the include is missing, the program does not compile. Here is the first part of the error that g++ 15 printed when the include was removed:
radix_noiom.cpp: In function ‘int main(int, char**)’:
radix_noiom.cpp:131:27: error: ‘setw’ is not a member of ‘std’The line number in your file may differ. The compiler also prints a hint that names the header to add. Adding #include <iomanip> fixes the error.
Practice
Exercise 1. The words are cat and cats. How many nodes does the plain trie have, and how many does the radix tree have? How many are saved?
Show the answer
The plain trie has five nodes: the root, "c", "ca", "cat" and "cats". The radix tree has three: the root, "cat" (a word end) and "cats" (a word end). The nodes "c" and "ca" each have one child and are not word ends, so they merge. Two nodes are saved. The program prints plain trie nodes: 5, radix nodes: 3, and the saved count is 2.
Exercise 2. The words are dog, dot and dig. How many radix nodes are there, and which node is merged?
Show the answer
There are six radix nodes. The plain trie has seven. The node "di" has one child, "g", and is not a word end, so it merges into the edge "ig". The node "d" has two children, so it stays. The node "do" has two children, so it stays. The program prints:
plain trie nodes: 7
radix nodes: 6
label letters: 6
d
ig (word)
o
g (word)
t (word)Exercise 3. The only word is hello. How many nodes are saved?
Show the answer
The plain trie has six nodes: the root and five letter nodes. The radix tree has two nodes: the root and the word end. Four nodes are saved. The four merged nodes are the prefixes "h", "he", "hel" and "hell", and their letters move into the one edge labelled "hello".
Exercise 4. The words are tomato and tomatoes. What does the radix tree look like?
Show the answer
The shared part "tomato" is one edge, and "es" is the second edge. The program prints:
plain trie nodes: 9
radix nodes: 3
label letters: 8
tomato (word)
es (word)The node for "tomato" is a word end, so it is kept even though it has a child. This is the same rule that the car and card example uses.
Exercise 5. Why does the radix tree in this lesson store the same number of letters as the plain trie?
Show the answer
Each non-root node in a plain trie holds exactly one letter. A radix tree removes some of those nodes, but it moves their letters into edge labels. So the total letter count is the same, and it is always the plain node count minus the root. The saving comes from having fewer node objects, not from storing fewer letters.
Summary
- A radix tree keeps the root, word ends and branch nodes, and merges every other node into an edge with a longer label.
- A word end must be kept even when it has one child, or a stored word is lost.
- The letters are not removed. They move into labels, so the saving is in the number of nodes.
- On the first 1,000 words of the list used here, the radix tree has 1,343 nodes instead of 3,328, a saving of about 60 percent.
- Whether this saves memory depends on the node type. Count the bytes per node and the bytes for labels in the design you use.