| Invented by | Fredkin (1960) | |
| Idea: |
- 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
|
| Advantages: | all the operations take \(O(|w|)\) time (i.e., time proportional to the length of the word) |
| Variations: |
- Patricia tree
- hash trie
- burst trie
|
| Disadvantages: | a straightforward implementation where each node stores an array of edges takes too much space |