A trie can contain a path for a string without storing that string as a key. Each edge contributes one character; the path from the root to a node spells a string. A key node is marked true to say that this complete string is stored. An intermediate node is marked false: its path is only a prefix needed to reach other keys. section 6.2
Figure 6.2 The structure of a trie. Words are encoded in the tree using edges, each edge corresponds to a single character, and each node n is associated with a single word, the one obtained by joining the characters associated with the edges in the path from the root to n. The root node corresponds to the empty string (because no edge is traversed), the leftmost leaf corresponds to “aa”, and so on. Not all the paths make meaningful words, and not all the nodes store the word associated with them. Only filled, black nodes (called “key nodes”) mark words stored in the trie, while hollow nodes, aka “intermediate nodes,” correspond to prefixes of words stored in the trie. Notice that all leaves should be key nodes.
Follow an edge path to its endpoint, then check whether the node is filled. The path supplies the characters; the node’s mark determines whether they form a stored key. section 6.2
The mark controls the main operations:
- Search follows one matching edge per input character. If an edge is missing, the key is absent. After the last character, search returns the current node’s key-node mark; reaching an intermediate node is not a successful lookup. section 6.2.2
- Insert follows the existing path, creates nodes for any missing suffix, and marks the final node as a key node. If the full path already exists, only its final mark needs changing. section 6.2.3
- Remove can simply clear the mark. For an inner node, this preserves paths to longer keys; for a leaf, it can leave a branch containing no key. Pruning removes such dangling nodes but makes removal more involved. section 6.2.4
A key that is also a prefix
If “ant” is stored, its endpoint is a key node. Inserting “anthem” follows that shared path, adds edges for “hem,” and marks the new endpoint. Both words remain stored: a key node need not be a leaf. The root, which represents the empty string, is a key node only when that string is stored. section 6.2 section 6.2.3
The mark adds little information to each node, but intermediate nodes and child links also consume space. Shared prefixes can make a trie economical; few shared prefixes or many unpruned deletions can work against it. Search and insertion follow the input characters rather than comparing complete strings at each node. section 6.2 section 6.2.1 section 6.2.4
