# 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
re*trie*val, 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