trie

A trie is a digital tree for storing a set of strings in which there is one node for every prefix of every string in the set. The name comes from the word retrieval, and thus is pronounced the same as tree (which leads to much confusion when spoken aloud). The word retrieval is stressed, because a trie has a lookup time that is equivalent to the length of the string being looked up.

If a trie is to store some set of strings $S\subseteq {\mathrm{\Sigma }}^{*}$ (where $\mathrm{\Sigma }$ is an alphabet), then it takes the following form. Each edge leading to non-leaf nodes in the trie is labelled by an element of $\mathrm{\Sigma }$. Any edge leading to a leaf node is labelled by $\$$ (some symbol not in $\mathrm{\Sigma }$). For every string $s\in S$, there is a path from the root of the trie to a leaf, the labels of which when concatenated form $s++\$$ (where $++$ is the string concatenation operator). For every path from the root of the trie to a leaf, the labels of the edges concatenated form some string in $S$.

Example

Suppose we wish to store the set of strings $S:=\{alpha,beta,bear,beast,beat\}$. The trie that stores $S$ would be