A tree-like data structure for efficient retrieval of keys in a dataset of strings.
A Trie, also known as a prefix tree or digital tree, is a specialized tree structure used for storing a dynamic set of strings. Unlike a binary search tree, where nodes store keys, the position of a node in a trie defines the key associated with it. All descendants of a node share a common prefix of the string associated with that node, while the root represents an empty string. Each node typically contains an array of pointers (one for each character in the alphabet) and a boolean flag indicating if the node represents the end of a word. This structure makes tries extremely efficient for prefix-based operations. Searching for a string of length `k` or its prefix takes O(k) time, independent of the number of strings stored in the trie. Inserting a string of length `k` also takes O(k) time. This efficiency makes them the data structure of choice for applications like autocomplete features in search engines, spell checkers, and IP routing tables. The main drawback of a trie is its space consumption, as each node may have many null pointers, but this can be mitigated with more compact implementations like a compressed trie or a ternary search tree.