word games are definitely the big one [a dawg, which is a packed form of a trie, is even better; it trades off space efficiency for being 'final' in that you ca

word games are definitely the big one [a dawg, which is a packed form of a trie, is even better; it trades off space efficiency for being 'final' in that you cannot modify it once packed. http://www.wutka.com/dawg.html http://www.wutka.com/dawg.html]. but i've used a trie once to good effect to replace a red-black tree with a depth-3 trie whose leaves were red-black trees, trading off the increased space usage for the ability to update the rbtree entries in parallel.