Tries

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 prefixes of multiple keys. Each inner node contains one symbol, and the sequence of symbols from the root to a given inner node is the prefix of all keys in the subtree rooted at that node. Searching for a key therefore consists of following a path from the root dictated by successive symbols of the key until either finding a prefix that is not present in the trie (meaning that the key is not present) or reaching a leaf, which may then be compared with the key. At any given inner node, the child to look at next is either the inner node that contains the next symbol in the key, or the leaf node that has that symbol as its k^th character, where k+1 is the depth of the leaf node.

To insert a new key, we find the point at which this search procedure ends, and then either insert a new leaf directly or else insert one or more inner nodes corresponding to the prefixes of the new key that already exist. To delete a key, we remove its leaf, and (working up from the removal point) any inner nodes that have less than two keys under them as a result.

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. Here, we use "*".

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 delete keys by double-clicking them.