There are still some interesting applications of tries (and dictionary automata). E.g., if you want to find all words given a prefix (wildcard searches). If the

There are still some interesting applications of tries (and dictionary automata). E.g., if you want to find all words given a prefix (wildcard searches). If the dictionary is static, you could use an array with binary search, however for dynamic dictionaries this gives you O(n) insertion. Ternary search trees are really great and relatively compact. A while ago, I compared memory use of storing a dictionary (the SOWPODS word list) in Rust using various tries (as measured with the heapsize crate): - Trie, using a HashMap to store edges: 691MB - Trie, using a sorted Vec to store edges: 44MB - Ternary search tree: 18MB A typical ternary search trie is even more compact, but I implemented randomized ternary search tries, which uses two extra member variables in each node for bookkeeping (in these measurements u16s).