A *trie* (pronounced ``try'') is a data structure that supports
efficient FIND, INSERT, and DELETE operations for keys that can be
represented by a unique string. In fact, the time complexity of *
any* of these operations is *O*(1) with respect to the number of keys
present in the trie. The factor that determines the worst-case time
it takes to perform any of these operations on a trie is the length of
the key. For example, if we used a trie to implement a telephone
directory, it would take the same amount of time to find ``Ellard,
Dan'' whether we were looking in the Harvard telephone book or a
telephone book for the entire United States. It could take twice as
long to look up ``Titmouse, Barneswoggle'', however, simply because
this name is twice the length of ``Ellard, Dan''.

- Tries as an Abstract Data Type
- Tries as a Data Structure
- Implementing Tries
- Reducing Memory Requirements: Eliminating Nodes
- Reducing Memory Requirements: Smaller Nodes
- More Trie Operations
- Exercises

Mon Jul 21 22:30:59 EDT 1997