TAOCP 6.3 Exercise 13

Let each key be a digit string over an alphabet of size $M$, K = k_1 k_2 \dots k_\ell, \qquad 0 \le k_i < M.

taocpmathematicsalgorithmsvolume-3medium

Section 6.3: Digital Searching

Exercise 13. [20] [20] (M-ary digital searching.) Explain how Algorithms T and D can be combined into a generalized algorithm that is essentially the same as Algorithm D when M = 2. What changes would be made to Table 1, if your algorithm is used for M = 30?

  1. [25] Design an efficient algorithm that can be performed just after Algorithm P has terminated successfully, to locate all places where K appears in the TEXT.

Verified: yes
Solve time: 3m02s

Corrected Solution

1. A single unified M-ary digital structure

Let each key be a digit string over an alphabet of size $M$,

$$ K = k_1 k_2 \dots k_\ell, \qquad 0 \le k_i < M. $$

We define a single node structure $P$ as a record containing:

  • $\operatorname{LINK}(P, i)$, for $0 \le i < M$, each either a node or $\Lambda$;
  • $\operatorname{KEY}(P)$, either empty or a full key.

The essential constraint that makes the model well-defined is the following invariant:

Invariant. Each key $K$ is stored in exactly one node $P$, and the path from the root to $P$ is determined solely by successive digits $k_1, k_2, \dots$ via links $\operatorname{LINK}(\cdot, k_i)$. No branching decision ever depends on comparisons between full keys.

Thus the structure is purely digit-directed (as in Algorithm T), while allowing keys to be stored in internal nodes (as in Algorithm D).

2. Combined search algorithm

Search for a key $K = k_1 \dots k_\ell$.

Set $P \leftarrow \text{root}$ and $i \leftarrow 1$.

Repeat:

  1. If $\operatorname{KEY}(P)$ is nonempty and $\operatorname{KEY}(P) = K$, then terminate successfully.
  2. If $i > \ell$, terminate unsuccessfully.
  3. Set $P \leftarrow \operatorname{LINK}(P, k_i)$.
  4. If $P = \Lambda$, terminate unsuccessfully.
  5. Set $i \leftarrow i+1$, and repeat.

3. Why this correctly combines Algorithms T and D

In Algorithm T, keys are associated only with terminal nodes corresponding to complete digit paths, and search succeeds only upon reaching such a terminal node.

In the present algorithm, assume:

  • $\operatorname{KEY}(P)$ is nonempty only at nodes where all outgoing links are $\Lambda$, i.e., terminal nodes.

Then step (1) is effectively executed only at the end of a digit path. The algorithm reduces to:

  • follow digit links $k_1, \dots, k_\ell$,
  • succeed iff the terminal node exists and contains the key.

This is exactly Algorithm T.

Relation to Algorithm D (digital search tree, $M=2$)

In Algorithm D, keys may be stored in internal nodes, but navigation is still determined solely by successive digits of the search key (binary digits when $M=2$).

When $M = 2$:

  • the link vector becomes $\operatorname{LINK}(P,0)$, $\operatorname{LINK}(P,1)$,
  • navigation is identical to binary digit inspection,
  • keys are encountered at internal nodes rather than only leaves.

Our algorithm matches this exactly because:

  • it never uses key comparisons to choose a branch,
  • it only uses digit selection,
  • it only tests equality after arrival at a node.

Thus it is Algorithm D when $M=2$, with the standard DST interpretation.

4. Why the early key test is valid

The key test

$$ \operatorname{KEY}(P) = K $$

does not influence the traversal. It only detects whether the search key has arrived at a node where the stored key matches.

Since traversal depends only on digits $k_i$, not on stored keys, this test cannot alter correctness or path selection. It is therefore consistent with both trie and DST paradigms.

5. Modification of Table 1 for $M = 30$

In Table 1, each node is represented as a record containing link fields indexed by digit values.

For $M = 30$, the following structural changes occur:

  1. Expansion of link fields.

Each node record becomes:

$$ \operatorname{LINK}(P,0), \operatorname{LINK}(P,1), \dots, \operatorname{LINK}(P,29). $$ 2. Digit representation.

All characters used in keys must be encoded in base 30, i.e., as digits in ${0,1,\dots,29}$. 3. Table interpretation.

Each row of Table 1 that previously contained a small number of outgoing branches is replaced by a 30-way branching vector. Empty entries correspond to $\Lambda$. 4. No change in logical structure.

The algorithmic structure of Table 1 remains identical: each node still has exactly one key field and a set of outgoing links indexed by digit value. Only the arity of the branching increases.

Thus Table 1 is transformed from a low-arity schematic representation into a 30-ary radix representation, without altering the underlying node organization or search logic.

Conclusion

The correct combination of Algorithms T and D is obtained by a single digit-directed structure in which:

  • branching is always determined by digit inspection (trie behavior),
  • keys may be stored at internal nodes (DST behavior),
  • successful search is determined by encountering a node whose stored key matches the search key.

For $M=2$, this reduces exactly to Algorithm D. For general $M$, it is an $M$-ary digital search tree with trie-style navigation and generalized arity.