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 prefix lookup and permit correct enumeration of keys that are prefixes of other keys.