A pass-through node is an intermediate, non-key node with exactly one outgoing edge whose parent also has exactly one outgoing edge. Because it carries no branching or key information, the path through these nodes can be compressed into one edge labeled with the concatenated string. section 6.3 section 6.3.4
Use the node condition to guide radix-trie maintenance:
- During compression, merge adjacent edges around pass-through nodes and replace their character labels with one string label. section 6.3
- After deletion, remove dangling branches, test the affected destination and parent, then compress any newly formed pass-through path. section 6.3.4
- Implement the test by checking that the node is not a key node, has one child, and has a parent with one outgoing edge. section 6.3.4
Deleting a key
When deleting “atom,” unmark its terminal node, remove a resulting dangling branch, and inspect its parent. If that parent becomes a pass-through node, remove it and merge the surrounding edges. In the illustrated trie, compression reduces the structure after deletion. section 6.3.4
Figure 6.20 Removing the word “atom” from an example radix trie. (1) Find the node at the end of the path for the key to delete. The path must entirely match the key. (2) Unmark the node, making it an intermediate node. If the node is a leaf, it will create a dangling branch. (3) Remove the dangling branch. If the parent of the node removed had only two children, it now became a pass-through node. (4) Compress the path by removing the pass-through node and merging edges.
Follow the four-stage deletion diagram: find the exact key path, unmark the terminal node, remove the dangling branch, and merge edges after removing the pass-through node. section 6.3.4
