Trie
In computer science, a trie (confusingly pronounced "tree") is an ordered tree data structure that is used to store an associative array where the keys are strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree shows what key it is associated with. All the descendants of any one node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that happen to correspond to keys of interest.In the above example, keys are listed in the nodes and values below them. Each complete English word has an integer value associated with it. Tries can be seen as a determinstic finite automaton, although the symbol on each edge is often implicit in the order of the branches.
Although it seems restrictive to say a trie's key type must be a string, many common data types can be seen as strings; for example, an integer can be seen as a string of bits. Integers with common bit prefixes occur as map keys in many applications such as routing tables and address translation tables.
Tries have the additional advantage that they make it efficient to associate a particular value with a group of keys that have a common prefix. They also make longest-prefix matching or lookup efficient.
Tries are most useful when the keys are of varying lengths and we expect some key lookups to fail, because the key is not present. If we have fixed-length keys, and expect all lookups to succeed, then we can improve key lookup by combining every node with a single child (such as "i" and "in" above) with its child, producing a Patricia trie. This is particularly useful in maps where many keys have a long common prefix.
External Links
See also search algorithm.
