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."

There are some who, in a sadly misguided 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), Darius Bacon's functional implementation (Scheme)

More information

Explanations of and comparisons between tries and suffix trees.

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.

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

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

Entry modified 5 January 2006.
HTML page formatted Mon Sep 11 10:07:28 2006.

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. 5 January 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/trie.html