Trie (Prefix Tree)
Each node = one character. Path root→node = prefix. is_end marks word boundaries.
Complexity
| Operation | Time | Notes |
|---|---|---|
| Insert | O(m) | m = word length |
| Search (exact) | O(m) | |
| Prefix check | O(p) | p = prefix length |
| Prefix collect | O(p + k) | k = results |
| Delete | O(m) |
vs Hash Table: trie has O(p + k) prefix search vs O(n × m) scan; hash is usually lower memory for exact lookup.
Implementation
c
[Description truncada. Veja o README completo no GitHub.]