A tree in which each path from the root spells out a prefix of a stored string, so that words sharing a prefix share the same path; used for fast prefix search, autocomplete and dictionary lookups.
Facts
Origin YearAn abstract form of the idea was described by Axel Thue in 1912; the term trie was coined independently by Edward Fredkin in 1960. Core PrincipleA tree-shaped data structure for storing and retrieving strings in which a node's position, rather than its contents, encodes the key: each edge represents one character, so strings sharing a prefix share the same path from the root. 1 Connections
In Field
Invented
Edward Fredkin coined the term trie and described the structure in his 1960 paper Trie Memory.
Sources
1. Wikipedia: Trie
Wikimedia FoundationHistory, etymology and pronunciation section
Tries were first described in a computer context by René de la Briandais in 1959.
Lead section, first paragraph
Unlike a binary search tree, nodes in a trie do not store their associated key. Instead, each node's position within the trie determines its associated key, with the connections between nodes defined by individual characters rather than the entire key.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.