A trie is a search-tree structure that provides for insertion, search, and removal of keys in time proportional to the length of the key, regardless of the quantity of data stored in the trie. Here, the definition of "length" depends on the type of data. Anything that can be treated as a sequence of symbols from some finite alphabet can serve as a key. Strings are the usual keys, but since a number may be represented as a sequence of digits (or of bits), numbers also qualify. Indeed, it is possible to turn essentially anything into bits, the simplest alphabet.
The keys in the trie occupy the leaf nodes. Inner nodes correspond to
There is a slight problem if a key is also a prefix of another key (consider a trie containing both "clan" and "clank"). We could modify the strategy and tag inner nodes that also represent keys. Another technique (used here) is to terminate every key with a unique symbol (found only at the end of keys), thus guaranteeing that no key is also a prefix of another.
In this demonstration, leaf nodes are represented by rectangles and inner nodes are circular. You can insert new keys by typing them into the "New key" space, and can keys by double-clicking them.
|
|
Fast | Slow |
New key: |