An internal node is a trie node with one or more children. It represents a prefix on paths to stored strings but, unlike a key node, does not necessarily represent a stored word itself. The root is an internal node for the empty string unless the empty string is stored. section 6.2 section 6.3
Use the node’s children and key marker to distinguish its roles:
- A branching internal node has multiple children, showing that stored keys share its prefix and then diverge. section 6.3
- A pass-through internal node has one child and stores no key; it is a forced step that can be compressed in a radix trie. section 6.3
- A key node may also have children, because one stored word can be a prefix of longer stored words. section 6.2
Deletion and pruning
Removing a stored key can simply clear the terminal node’s key marker, turning it into an internal node. If that node is a leaf, the change leaves a dangling branch; a pruning implementation backtracks and removes nodes that no longer lead to keys. section 6.2.4
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.
Use the trie diagram to follow prefixes encoded by edges and distinguish filled key nodes from hollow internal nodes. section 6.2
