[tieTYT]

I think the article was well written. This is the standard example to use for a Trie. But I never run into any scenarios except for this that make me think, "A Trie is a good fit for this!" What are some other examples where Tries come in handy?

[tmoertel]

I've used prefix trees to represent matching rules for network-routing rulesets. They're also handy when you need to compute intersections because you can perform a parallel depth-first search over two prefix trees and prune from the search any nodes that don't have a corresponding node in the other tree.

For a fun example of this last application, there was a recent Google Code Jam problem called "Alien Languages" [1]. My solution [2] basically counts the leaf nodes in the intersection of two prefix trees. (Note that we can compute the count on the fly during the search and need not actually construct the intersection.)

[1] http://code.google.com/codejam/contest/90101/dashboard#s=p0

[2] https://github.com/tmoertel/practice/blob/master/google-code...

[zb]

When I was developing firmware for Layer 3 network switches we made very heavy use of Patricia Tries (it was originally pronounced like 'tree', BTW... stupid name) for the management of routing tables. They're a good fit because you typically have comparatively long common prefices, especially within your own network.

[jdmichal]

I think the alternate name for tries, radix trees, provides a good hint to potential use-cases. Any problem where the data can be broken down and searched by radix would be a potential good fit. You could even break down data structures with a lot of limited-enumeration fields in a similar way, using a different field at each depth, and gaining deduplication for each node which follows the same path through the structure.

[zem]

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

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.