TAOCP 6.3 Exercise 2
Let $K$ be the search argument, and assume it is represented as a sequence of characters ending with the blank symbol used in Algorithm T.
Section 6.3: Digital Searching
Exercise 2. [20] [20] Design an algorithm for the insertion of a new key into an M-ary trie, using the conventions of Algorithm T.
Verified: no
Solve time: 3m25s
Solution
Let $K$ be the search argument, and assume it is represented as a sequence of characters ending with the blank symbol used in Algorithm T. Let $P$ denote a pointer to a node of the trie, and let $k$ denote the current character index as in Algorithm T.
The insertion procedure follows the same digit-by-digit access pattern as Algorithm T until either a missing link is encountered or an existing key is reached at a node entry. In both cases a local modification of the trie structure suffices, since all nodes are vectors indexed by characters in the range $0 \le k < M$.
We first describe the behavior while descending the trie. At each stage, the algorithm reads the next character of $K$, forms $k$, and inspects $X \leftarrow \mathrm{NODE}(P)[k]$. If $X$ is a link, descent continues unless the link is null. If $X$ is null, a new subtree must be created that stores the remaining suffix of $K$ as a unique path ending in a key. If $X$ is a key, a collision occurs and the existing key must be separated from $K$ by introducing additional nodes at the first position where the two strings differ.
Algorithm I (Trie insertion). A new key $K$ is inserted into an $M$-ary trie whose nodes follow the conventions of Algorithm T.
$I1$. [Initialize.] Set $P$ to point to the root of the trie. Set $i \leftarrow 1$.
$I2$. [Next character.] Let $k$ be the $i$th character of $K$. Let $X \leftarrow \mathrm{NODE}(P)[k]$.
$I3$. [Null link case.] If $X = \Lambda$, allocate a new path for the suffix $K[i+1], K[i+2], \dots$ by repeated node creation. For each remaining character, create a new node whose only non-null outgoing entry corresponds to the next character of $K$. At the final character (the terminating blank), store $K$ as a key in the corresponding node entry of the last created node. Terminate the algorithm.
$I4$. [Follow link case.] If $X$ is a link, set $P \leftarrow X$, set $i \leftarrow i+1$, and return to step $I2$.
$I5$. [Key collision case.] If $X$ is a key $Y$, then $Y$ and $K$ agree on the prefix determined by the path to $P$ followed by the character $k$, and they differ at some later position. Let $j$ be the smallest index such that $K[j] \ne Y[j]$, where both strings are extended to include the terminating blank symbol.
Construct a new node $Q$ to replace the entry $\mathrm{NODE}(P)[k]$. From $Q$, create a chain of nodes corresponding to the common prefix of $K$ and $Y$ starting at position $i+1$ up to position $j-1$, if any such positions exist. At position $j$, allocate a node $R$ with two outgoing entries: one leading to a subtree for the suffix of $K$ starting at $j$, and one leading to a subtree for the suffix of $Y$ starting at $j$. Replace $\mathrm{NODE}(P)[k]$ by a link to $Q$. Terminate the algorithm.
The construction in step $I5$ is well-defined since the first position of disagreement determines a unique branching point, and both suffixes beyond that position define valid continuations in the trie representation.
Each insertion modifies at most one path from the root and introduces new nodes only along the suffix that is not already represented, or at a single branching point where an existing key is split into two distinct paths.
This completes the solution. ∎