Trie Data Structure
A Trie Data Structure is a tree-based data structure that stores an associative array (of strings) to facilitate fast prefix-based retrieval operationss, character-by-character insertion operations, and key-specific deletion operations.
- AKA: Prefix Tree.
- Context:
- It can (typically) be used to store and manage strings to facilitate fast retrieval, insertion, and deletion operations.
- It can (often) enable efficient prefix searches, allowing for the quick lookup of all strings that share a common prefix.
- It can be represented as a collection of nodes, where each node represents a single character or part of a string.
- It can have linked nodes so that each path from the root node to a leaf node represents a string stored in the trie.
- It can use the structure of the trie to reduce the search space for a query, making operations faster compared to flat data structures like arrays or linked lists.
- It can be particularly useful in applications involving large dictionaries, such as autocomplete features, spell checking, and network routing.
- It can (often) be optimized into a Compact Prefix Tree or a Radix Tree to reduce memory usage by merging nodes that are the only child of their parent.
- ...
- Example(s):
- One to support a Spell Checker, where each node represents a letter and paths from the root to a leaf node spell out words in the dictionary.
- One to enable quick suggestions of search terms based on user-typed prefixes.
- One to support fast lookup of contacts by typing the initial letters of the name.
- One used in a Routing Table for a network router, where IP addresses are stored for efficient routing of data packets.
- One to find valid words based on partial inputs, for example, in a crossword puzzle application.
- ...
- Counter-Example(s):
- Binary Search Tree, as it is not optimized for prefix searching and string operations.
- Hash Table, since it does not inherently support ordered data or prefix searches.
- Stack, as it does not hierarchically represent data or facilitate string-based operations.
- See: Finite State Automata, Dictionary-based String Matching Task, Aho-Corasick Algorithm, Deterministic Acyclic Finite State Automaton, Radix Tree, Binary Search Tree, Compact Prefix Tree, Deterministic Finite Automaton.
References
2024
- (Wikipedia, 2024) ⇒ https://en.wikipedia.org/wiki/Trie Retrieved:2024-3-6.
- In computer science, a trie , also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key.
Unlike a binary search tree, nodes in the trie do not store their associated key. Instead, a node's position in the trie defines the key with which it is associated. This distributes the value of each key across the data structure, and means that not every node necessarily has an associated value.
All the children of a node have a common prefix of the string associated with that parent node, and the root is associated with the empty string. This task of storing data accessible by its prefix can be accomplished in a memory-optimized way by employing a radix tree.
Though tries can be keyed by character strings, they need not be. The same algorithms can be adapted for ordered lists of any underlying type, e.g. permutations of digits or shapes. In particular, a bitwise trie is keyed on the individual bits making up a piece of fixed-length binary data, such as an integer or memory address. The key lookup complexity of a trie remains proportional to the key size. Specialized trie implementations such as compressed tries are used to deal with the enormous space requirement of a trie in naive implementations.
- In computer science, a trie , also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first, following the links between nodes, which represent each character in the key.
2016
- (Wikipedia, 2016) ⇒ http://wikipedia.org/wiki/Trie Retrieved:2016-2-23.
- In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as prefixes can search them), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. ...
2012
- http://en.wikipedia.org/wiki/Trie#Dictionary_representation
- A common application of a trie is storing a dictionary, such as one found on a mobile telephone. Such applications take advantage of a trie's ability to search for, insert, and delete entries quickly; however, if storing dictionary words is all that is required (i.e. storage of information auxiliary to each word is not required), a minimal acyclic deterministic finite automaton would use less space than a trie. This is because an acyclic deterministic finite automaton can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored.
Tries are also well suited for implementing approximate matching algorithms, including those used in spell checking and hyphenation software.
- A common application of a trie is storing a dictionary, such as one found on a mobile telephone. Such applications take advantage of a trie's ability to search for, insert, and delete entries quickly; however, if storing dictionary words is all that is required (i.e. storage of information auxiliary to each word is not required), a minimal acyclic deterministic finite automaton would use less space than a trie. This is because an acyclic deterministic finite automaton can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored.