It seems you'd get more mileage out of a trie if you also compared it with a sort of zipper approach. The idea being that if I type "a", I should just focus the

It seems you'd get more mileage out of a trie if you also compared it with a sort of zipper approach. The idea being that if I type "a", I should just focus the trie around "A". If I next type "l", then I focus the "l" around my new root, so I find all strings starting "Al". It doesn't change the complexity class of completion, but maybe the small optimisation is worth it.