Definition: A tree for storing strings in which there is one node for every common prefix. The strings are stored in extra leaf nodes.
Generalization (I am a kind of ...)
Specialization (... is a kind of me.)
bucket trie, Patricia tree, compact trie.
See also digital tree, digital search tree, directed acyclic word graph, compact DAWG, suffix tree.
The name comes from reTRIEval and is pronounced, "tree." See the historical note.
Renee de la Briandais, File Searching Using Variable Length Keys, Proc. AFIPS Western Joint Computer Conference, San Francisco, California, USA, 15:295-298, March 1959.
Edward Fredkin, Trie Memory, CACM, 3(9):490-499, September 1960.
On 31 July 2008 Edward Fredkin wrote
As defined by me, nearly 50 years ago, it is properly pronounced "tree" as in the word "retrieval". At least that was my intent when I gave it the name "Trie". The idea behind the name was to combine reference to both the structure (a tree structure) and a major purpose (data storage and retrieval).
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 22 February 2011.
HTML page formatted Tue Dec 6 16:16:33 2011.
Cite this as:
Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 22 February 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/trie.html