trie

(data structure)

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 ...)
tree.

Specialization (... is a kind of me.)
bucket trie, Patricia tree, compact trie.

Note: The name comes from reTRIEval and is pronounced, "tree." See the historical note.

There are many who, in an attempt to verbally distinguish a trie from the more general tree and in contrast to typical English pronunciation (of which calorie, eerie, and reverie are examples, but die, lie, and pie are not), pronounce the name "try".

Author: PEB

Implementation

insert (C) and search (C).

More information

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.

Historical Note
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).

Ed Fredkin

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 22 February 2011.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 22 February 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/trie.html