# Trie

Invented by Fredkin (1960) edges are labeled by characters; we use a special symbol (\$) to mark the end of word the root corresponds to an empty word and each vertex $v$ corresponds to a word spelled out by edges on the path from root to $v$ thus, root-to-leaf paths represent the words stored in the trie all the operations take $O(|w|)$ time (i.e., time proportional to the length of the word) Patricia tree hash trie burst trie a straightforward implementation where each node stores an array of edges takes too much space