Trie

data-structures string-algorithms

Definition

Trie

A trie is a rooted tree that represents a finite set $S\subseteq {\Sigma }^{\ast }$ of strings over an alphabet $\Sigma$.

Each edge is labelled by one letter from $\Sigma$, and outgoing edges of the same node have pairwise distinct labels. The root represents the empty string $\epsilon$. For any node $v$, the concatenation of edge labels on the path from the root to $v$ is the prefix represented by $v$.

A node is marked as terminal iff its represented prefix is a string in $S$.

Compressed Trie

Definition

Compressed Trie

A compressed trie is a trie where non-branching chains are contracted into single edges.

Edges may be labelled by whole strings, and terminal nodes are preserved.

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.