= Trie terminal marker
A <trie terminal marker> records that the path to a <trie> node is a complete stored key, independently of whether that node has children. Store `to` and `top`: the node after `to` must be terminal even though its `p` child continues to `top`. Testing only for leaf nodes would incorrectly report that `to` is absent.
Insertion sets the marker at the end of the key; membership requires both a matching path and a terminal marker. Deletion clears the marker and may prune nodes that have neither a marker nor children. The initial node can itself be terminal if the empty <string> is a stored key. A symbol outside the key alphabet can implement an explicit end marker instead, but it must be distinguished from ordinary key characters. These conventions separate exact-key lookup from <string prefix>[prefix] lookup and permit correct enumeration of keys that are <string prefix>[prefixes] of other keys.
Back to article page
