next up previous contents
Next: Tries as an Abstract Up: S-Q Course Book Previous: Exercises




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

Dan Ellard
Mon Jul 21 22:30:59 EDT 1997