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.]