Trie Algorithm

A trie is a search-tree algorithm and structure purpose-built to store and retrieve strings, organizing its keys not by comparing whole strings against each other the way a binary search tree does but by branching one character at a time, so every string sharing a given prefix shares the same path through the tree down to the point where the strings diverge. Searching for a string, inserting one, or deleting one all take time proportional only to the length of the string itself rather than to how many strings the trie holds, and because strings that share a prefix share the nodes along it, a trie can store a large collection of similar strings, such as a dictionary, far more compactly than storing each one separately. A trie also needs no hash function and has no possibility of the collisions that can slow down a hash table, and it can list its stored strings back out in sorted order, which a hash table cannot do directly. The abstract idea appears in a 1912 paper by Axel Thue; Rene de la Briandais brought it into computer science in 1959, and Edward Fredkin independently described and named the structure in 1960, coining trie as a reference to information retrieval, though the word is conventionally pronounced like "try" rather than like "tree" to distinguish it in speech.