Trie

Definition

Trie

A trie stores a finite set $S\subseteq {\Sigma }^{\ast }$ of strings over an alphabet $\Sigma$ as a rooted tree, with one node per distinct prefix:

$$\begin{array}{rl}V& =\{\epsilon \}\cup \{u:u\text{ is a prefix of some }s\in S\},\\ E& =\{u\stackrel{a}{\to }ua:u,ua\in V,a\in \Sigma \},\\ F& =S\subseteq V.\end{array}$$

The root represents the empty string $\epsilon$. Each edge appends one letter, so reading a root-to-node path spells the prefix represented by that node. Outgoing edges have distinct labels: a next letter selects at most one child.

The terminal nodes $F$ mark complete stored strings. Reaching a node means the path exists; reaching a terminal node means the string is stored. A terminal node may still have children. Shared prefixes use the same path, rather than separate copies.

The node labels above explain the paths; an implementation need not store a full prefix string at every node. If $\epsilon \in S$, the root is terminal. For $S=\varnothing$, only the non-terminal root remains.

Compressed Trie

Definition

Compressed Trie

A compressed trie represents the same set of strings as a trie, but removes every non-root, non-terminal node with exactly one child. Each resulting chain becomes one edge whose label concatenates the original labels:

$$u\stackrel{a_1}{\to }{v}_1\stackrel{a_2}{\to }\cdots \stackrel{a_r}{\to }v⟼u\stackrel{a_1{a}_2\cdots a_r}{\to }v.$$

The root, branching nodes, and terminal nodes remain. Edges carry non-empty strings, and outgoing edges still have distinct first characters. Reading a root-to-node path spells the same string before and after compression; membership still requires ending at a terminal node.

In the diagram, a, b, and ba disappear, but an remains because it is stored. Compression shortens paths in edges, not in characters: an edge labelled bar still requires checking three characters.

Link to original

Examples

Word membership

Let $S=\{\text{to},\text{tea},\text{ten},\text{inn}\}$.

The string $\text{tea}$ is in $S$ because the path

$$\epsilon \stackrel{t}{\to }\text{t}\stackrel{e}{\to }\text{te}\stackrel{a}{\to }\text{tea}$$

ends in a terminal node. The string $\text{te}$ is not in $S$ if the node for $\text{te}$ is not terminal, even though it is a prefix of stored strings.

Shared prefixes

The strings $\text{tea}$ and $\text{ten}$ share the prefix $\text{te}$. In a trie, the path for this prefix is stored once, and the two strings branch only at the last edge.

A standard trie groups strings by prefixes, not by suffixes.