Trie

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
[You can download the application for offline viewing.]

References

  • E. Fredkin. Trie memory. Communications of the ACM, 3(9):490-499, 1960. [bib] [pdf]
  • D.R. Morrison. Patricia—practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM (JACM), 15(4):514-534, 1968. [bib] [pdf]
  • Franklin Mark Liang. Word hy-phen-a-tion by com-put-er. PhD thesis, Stanford, CA, USA, 1983. [bib] [pdf]