Trie

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 search algorithm