|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Prefix Tree (Trie): Efficient String Storage and Search. More...
#include <iostream>#include <iomanip>#include <string>#include <vector>#include <chrono>#include <prefix-tree.H>#include <tclap/CmdLine.h>Go to the source code of this file.
Functions | |
| void | demo_basic_operations () |
| Demonstrate basic trie operations. | |
| void | demo_prefix_search () |
| Demonstrate prefix search - the trie's killer feature. | |
| void | demo_spell_checker () |
| Practical example: Spell checker suggestions. | |
| void | demo_command_autocomplete () |
| Practical example: Command-line autocomplete. | |
| void | demo_trie_structure () |
| Show trie structure visualization. | |
| void | demo_performance (int n) |
| Performance comparison vs hash set. | |
| int | main (int argc, char *argv[]) |
Prefix Tree (Trie): Efficient String Storage and Search.
This example demonstrates the Trie (also called prefix tree or digital tree), a tree-like data structure optimized for string storage and retrieval. Tries excel at prefix-based operations and are fundamental to many text processing applications.
A trie is a tree data structure where:
Trie storing words: "cat", "car", "card", "dog"
Key insight: Words sharing prefixes share nodes, making tries space-efficient for datasets with many common prefixes.
For a word/key of length k:
| Operation | Complexity | Notes |
|---|---|---|
| Insert | O(k) | One node per character |
| Search (exact) | O(k) | Traverse path |
| Prefix search | O(k) | Find prefix node |
| Delete | O(k) | Remove nodes if unused |
| Longest prefix match | O(k) | Find longest matching prefix |
Note: Complexity is O(k) where k is key length, NOT O(log n)! This makes tries especially efficient for short keys.
✅ Fast lookups: O(k) where k is key length (not dependent on dataset size!) ✅ Prefix operations: Excellent for prefix matching ✅ Memory efficient: Shared prefixes save space ✅ Ordered: Keys are naturally sorted (inorder traversal)
❌ Memory overhead: Each node stores pointers (can be large) ❌ Cache performance: Pointer chasing (not cache-friendly) ❌ Sparse: Many nodes may be empty (wasted space)
| Structure | Lookup | Prefix Search | Memory | Best For |
|---|---|---|---|---|
| Trie | O(k) | O(k) | High | Prefix operations |
| Hash Table | O(1) | No | Medium | Exact lookup |
| BST | O(log n) | O(n) | Low | General purpose |
Trie wins when: Prefix operations are common, keys are short
Definition in file trie_example.C.
| void demo_basic_operations | ( | ) |
Demonstrate basic trie operations.
Definition at line 227 of file trie_example.C.
References Aleph::maps(), root(), and Aleph::HTList::size().
Referenced by main().
| void demo_command_autocomplete | ( | ) |
Practical example: Command-line autocomplete.
Definition at line 424 of file trie_example.C.
References Aleph::maps(), root(), and Aleph::HTList::size().
Referenced by main().
| void demo_performance | ( | int | n | ) |
Performance comparison vs hash set.
Definition at line 529 of file trie_example.C.
References Aleph::maps(), Aleph::prefix(), root(), and Aleph::HTList::size().
| void demo_prefix_search | ( | ) |
Demonstrate prefix search - the trie's killer feature.
Definition at line 278 of file trie_example.C.
References FunctionalMethods< Container, T >::length(), Aleph::maps(), Aleph::prefix(), root(), and Aleph::HTList::size().
Referenced by main().
| void demo_spell_checker | ( | ) |
Practical example: Spell checker suggestions.
Definition at line 356 of file trie_example.C.
References FunctionalMethods< Container, T >::length(), Aleph::maps(), Aleph::prefix(), root(), and Aleph::HTList::size().
Referenced by main().
| void demo_trie_structure | ( | ) |
Show trie structure visualization.
Definition at line 486 of file trie_example.C.
References Aleph::maps(), and root().
Referenced by main().
| int main | ( | int | argc, |
| char * | argv[] | ||
| ) |
Definition at line 604 of file trie_example.C.
References demo_basic_operations(), demo_command_autocomplete(), demo_performance(), demo_prefix_search(), demo_spell_checker(), demo_trie_structure(), and Aleph::maps().