TAOCP 6.3 Exercise 44

Let $\Sigma$ be an ordered alphabet corresponding to the $M$ characters used in Section 6.

taocpmathematicsalgorithmsvolume-3hard

Section 6.3: Digital Searching

Exercise 44. [30] [30] (J. L. Bentley and R. Sedgewick.) Explore a ternary representation of tries, in which left and right links correspond to the horizontal branches of (2) while middle links correspond to the downward branches.

Verified: yes
Solve time: 1m41s

Setup

Let $\Sigma$ be an ordered alphabet corresponding to the $M$ characters used in Section 6.3, with a total order $<$ consistent with MIX character codes.

Let $S$ be a finite set of keys, each key $K \in S$ being a finite string over $\Sigma$. The corresponding trie is defined as in Algorithm T, where each node at level $i$ represents all keys sharing a common prefix of length $i$.

A ternary representation replaces each trie node vector by a binary-search structure on characters occurring at a fixed depth, with an additional pointer advancing to the next character position.

A ternary node contains a character field $\mathrm{ch}(v) \in \Sigma$, together with three links:

$$ \mathrm{left}(v), \quad \mathrm{mid}(v), \quad \mathrm{right}(v), $$

where left and right correspond to horizontal branching in the sense of comparing characters, and mid corresponds to descending one level in the original trie.

The search argument is a key $K = k_1 k_2 \cdots k_r$, and comparison is performed sequentially on characters $k_i$.

Solution

The ternary search trie (TST) is defined recursively as follows.

Each node $v$ stores a character $c = \mathrm{ch}(v)$ corresponding to some position $i$ in at least one key of $S$. The structure satisfies:

  1. All keys whose $i$th character is less than $c$ are stored in the subtree rooted at $\mathrm{left}(v)$.
  2. All keys whose $i$th character is greater than $c$ are stored in the subtree rooted at $\mathrm{right}(v)$.
  3. All keys whose $i$th character equals $c$ proceed to $\mathrm{mid}(v)$, where comparison continues at position $i+1$.

The empty key position (end-of-word marker) is treated as a distinguished character smaller than all elements of $\Sigma$, so termination can be handled uniformly.

The search procedure for a key $K = k_1 \cdots k_r$ starts at the root $v$. At a node $v$ corresponding to position $i$, the algorithm compares $k_i$ with $\mathrm{ch}(v)$.

If $k_i < \mathrm{ch}(v)$, the search continues at $\mathrm{left}(v)$ with the same index $i$. If $k_i > \mathrm{ch}(v)$, it continues at $\mathrm{right}(v)$ with the same index $i$. If $k_i = \mathrm{ch}(v)$, the search proceeds at $\mathrm{mid}(v)$ with index $i+1$. When $i = r+1$, the end-of-word symbol is used as the next character.

This structure simulates a trie level-by-level while replacing each $M$-way vector at a trie node by a binary search tree on the character values appearing at that level.

To establish correctness, define a mapping from trie nodes to TST states. Each trie node corresponds to a prefix $p = k_1 \cdots k_i$. In the TST, the sequence of $\mathrm{mid}$ transitions corresponds exactly to consuming characters of $p$ in order. Each $\mathrm{left}$ or $\mathrm{right}$ step preserves the current depth $i$ and refines the search among characters competing at position $i$.

The search terminates successfully in the TST if and only if it reaches a node $v$ with $\mathrm{ch}(v) = k_r$ and then follows a $\mathrm{mid}$ transition into the terminal marker representing end-of-word. This corresponds exactly to reaching a terminal trie node for $K$.

Unsuccessful termination occurs either when a required pointer is null or when a mismatch at the final character fails to reach the terminal condition. In both cases no path in the trie can represent $K$, since every trie path corresponds to a unique sequence of equal-character matches at successive depths.

The ternary structure is therefore equivalent to the original trie in the sense that it recognizes exactly the same set of keys.

Verification

At each step of the search, exactly one of the relations $k_i < \mathrm{ch}(v)$, $k_i = \mathrm{ch}(v)$, or $k_i > \mathrm{ch}(v)$ holds, since the alphabet order is total. The algorithm chooses the corresponding unique branch, so the path is well defined until a null link or terminal condition is reached.

Along any sequence of consecutive $\mathrm{mid}$ transitions, the index $i$ increases by $1$ at each step, matching exactly the progression along a single root-to-leaf path in the trie. No $\mathrm{left}$ or $\mathrm{right}$ transition changes $i$, so horizontal navigation corresponds only to resolving which character occupies a given trie level.

If a key $K$ is in $S$, the trie contains a path spelling $K$. At each level $i$, the node storing $k_i$ exists, hence the ternary search reaches a node with $\mathrm{ch}(v)=k_i$ and follows $\mathrm{mid}$ at every level, reaching the terminal marker. If $K$ is not in $S$, either some prefix is absent in the trie, or a mismatch occurs at some level $i$, and at that level the ternary search necessarily diverges via $\mathrm{left}$ or $\mathrm{right}$ into a subtree that contains no completion of $K$, since such completions would contradict the trie partition property at level $i$.

The correspondence between trie nodes and ternary search paths preserves membership of keys exactly, so the structure implements the same dictionary as Algorithm T.

This completes the proof. ∎

Notes

The ternary representation replaces an $M$-way branching table by a binary decision structure at each level. The middle links encode descent in the original trie, while left and right links encode a local ordered search among competing characters at that depth.

This construction is equivalent to what is now called a ternary search trie (TST). Its performance interpolates between binary search trees on characters and full tries: space is reduced relative to explicit $M$-ary nodes, while search time depends on both key length and the shape of the character comparison trees at each level.

Variants arise by balancing the left-right structure at each node or by storing multiple characters per node, but the essential invariant remains the separation between horizontal character selection and vertical prefix advancement.