A
trie is a
tree data structure that is used for searching a key/value map. In the case of a trie, the keys are restricted to strings whose alphabet has limited cardinality (e.g. the
English alphabet[?]). Each node has at most N+1 children (where N is the cardinality of the alphabet), and all of the children of that node share a common prefix denoted by the node's position and value in the tree.
See also search algorithm.