Trie

A trie or prefix tree is a data structure that is used in computer science to search for strings. This is a special search tree for the simultaneous storage of multiple strings.

The word trie was recommended by Edward Fredkin and was derived from the English expression from information retrieval.

In a trie, each edge of the tree represents an additional letter. Each node corresponds to the string that results from concatenating all edges of letters. The root node of a trie corresponds to an empty string.

To store data in compressed form in a trie, Patricia trie are used.