Trie
A trie is a tree-based data structure that stores sequences by sharing nodes for common prefixes, enabling efficient key and prefix lookup.
Advanced Algorithms and Data Structures
A trie is a tree-based data structure that stores strings by sharing nodes for common prefixes and supports efficient prefix-based lookup.
- How it is used
- Supports string-dictionary lookup, prefix queries, and spell-checking where keys often share beginnings.
- How deep it goes
- Develops node representation, recursive search, prefix traversal, and complexity trade-offs, then extends lookup to edit-distance suggestions.
- Examples
- Uses stored-word diagrams, recursive search listings, prefix enumeration, and a spell-checker that distinguishes candidate paths from dictionary words.
- What you can do after
- Build it from scratch for exact and prefix lookup, and apply it to dictionary-based typo detection.
Read how Advanced Algorithms and Data Structures explains trie →
Fabulous Adventures in Data Structures and Algorithms
A trie, or prefix tree, is a tree-shaped data structure that stores strings by sharing nodes representing common prefixes.
- How it is used
- Supports word membership tests and prefix completions for large word lists.
- How deep it goes
- Develops C# insertion and query algorithms with complexity and memory analysis, then defers suffix deduplication to DAWGs.
- Examples
- Uses a nine-word trie, incremental insertion of “car” and “care,” and measurements from the ENABLE word list.
- What you can do after
- Build it from scratch and use it for membership checks and prefix enumeration while assessing its memory costs.
Read how Fabulous Adventures in Data Structures and Algorithms explains trie →
Related concepts
- k-ary treekind of · A k-ary tree is a tree in which each node has at most k children.
- autocompleteused by · Autocomplete is an interactive input feature that suggests or completes likely continuations of partially entered text, code, commands, or other values.
- binary search treecontrasts with · A binary search tree is a binary tree whose nodes follow an ordering relation placing keys in designated left and right subtrees relative to each node.
- Mapimplements · A map is an associative data structure that stores key-value pairs and supports retrieving values by key.
- stringuses · A string is a programming-language value representing an ordered sequence of characters or character units as text.
- data structurekind of · A data structure is an organized representation of data and its relationships that supports defined operations for storing, accessing, or modifying it.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.