Question
Store sequences of integers so a shared beginning occupies one path. A plain trie uses one node per integer. Here, a run of nodes that each have only one child is stored as one edge. ## Requirements - Insert shares an edge when two sequences start the same way. A sequence with nothing in common gets its own branch. - Inserting a shorter sequence after a longer one must cut the long edge. - To cut an edge, walk until the new sequence disagrees. The shared head stays on the parent edge. The old tail becomes one child. The new tail becomes another. - A disagreement on the first integer splits that edge into a one-integer head plus two children. - Exact membership is true only for a sequence that was inserted, not for a proper head of one. - The longest stored head of a query returns that head, or empty when the start is missing. - A full listing returns every inserted sequence, including both a short one and a longer one that extends it. ## Review checklist 1. After a split, do both the old tail and the new tail remain reachable? 2. Is a proper head reported as absent from exact membership? 3. Does the longest-head query return the longest inserted head, not a longer sequence that was never inserted? 4. Does listing include both a short sequence and a longer sequence that extends it? ## Staged follow-ups 1. Define what a duplicate insert does. 2. Add a use count on a shared edge and say when the count changes. 3. Support delete, and drop an edge only when nothing still needs it. 4. When memory is full, drop the least recently used branches and state what a later lookup does.