Trie
Introduction
A trie is a rooted tree data structure for storing strings. Each edge is labeled by one character. For a string
\[ s=s_0s_1\cdots s_{m-1}, \]
the path
\[ \text{root}\to s_0\to s_1\to\cdots\to s_{m-1} \]
represents the string. Thus common prefixes of different strings are stored only once.
Trie is useful when the operation depends on prefixes rather than on the whole string as an indivisible key. The usual operations are insertion, exact search, prefix search, and enumeration of strings under a prefix.
Explanation
Let $\Sigma$ be a finite alphabet. Each trie node $v$ stores an array or map
\[ \operatorname{next}_v:\Sigma\to V\cup{\varnothing}, \]
where $\operatorname{next}_v(c)$ is the child reached by character $c$. It also stores whether the path ending at $v$ is a complete word. Often we store two counters:
-
pass: the number of inserted strings whose path passes through this node; -
term: the number of inserted strings ending at this node.
To insert a string $s$, start from the root.
For each character $c$ of $s$, create the missing child if necessary and move to that child.
Increase pass along the path and increase term at the final node.
To search for an exact string, follow the same path.
If some edge is missing, the string is not present.
If the path exists, the string is present exactly when the final node has positive term.
To search for a prefix, follow the path of the prefix.
If the path exists, all strings stored in the subtree of the final node have that prefix.
The number of such strings is pass of that node if the counter is maintained.
The visualizer below shows insertion and search in a small trie. It is useful here because the point of the data structure is precisely the sharing of prefix paths.
Complexity
Let $L$ be the length of the string. With an array of size $\abs{\Sigma}$ at every node, each transition is $O(1)$. Insertion, exact search, and prefix search take
\[ O(L) \]
time. If a map is used instead, each transition costs the map access time.
The total number of trie nodes is at most
\[ 1+\sum_{s\in S}\abs{s}, \]
where $S$ is the set of inserted strings. Thus the memory usage is linear in the total length of the stored strings.
Code
The following implementation assumes lowercase English letters.
The same structure works for any fixed alphabet after changing A.
struct Trie {
static const int A = 26;
struct Node {
int next[A];
int pass;
int term;
Node() : pass(0), term(0) {
fill(next, next + A, -1);
}
};
vector<Node> t;
Trie() {
t.push_back(Node());
}
void insert(const string& s) {
int v = 0;
t[v].pass++;
for(char ch : s) {
int c = ch - 'a';
if(t[v].next[c] == -1) {
t[v].next[c] = (int)t.size();
t.push_back(Node());
}
v = t[v].next[c];
t[v].pass++;
}
t[v].term++;
}
bool contains(const string& s) const {
int v = 0;
for(char ch : s) {
int c = ch - 'a';
if(t[v].next[c] == -1) return false;
v = t[v].next[c];
}
return t[v].term > 0;
}
int count_prefix(const string& p) const {
int v = 0;
for(char ch : p) {
int c = ch - 'a';
if(t[v].next[c] == -1) return 0;
v = t[v].next[c];
}
return t[v].pass;
}
};
If duplicate strings should not be counted, replace term and pass by boolean or set-like counters according to the problem.
Applications
- Prefix queries on a dictionary
- Autocomplete
- Lexicographic enumeration of strings
- Counting strings with a given prefix
- Bitwise trie for maximum xor queries
- Aho–Corasick automaton construction
