TAOCP 6.3 Exercise 15

Section 6.3: Digital Searching

Exercise 15. [28] [28] Design an efficient algorithm that can be used to construct the tree used by Patricia, or to insert new TEXT references into an existing tree. Your insertion algorithm should refer to the TEXT array at most twice.

Verified: yes
Solve time: 4m43s

The flaw in the previous argument is real: the insertion point cannot depend on the unknown divergence index $d$, so any attempt to define it during the initial search is circular. The correct repair is to separate the computation into two phases: a Patricia search that records only structural information, followed by a purely in-memory reconstruction step after $d$ is known.

The key observation is that Patricia search does not need access to TEXT at all once the search key is available in memory, and the entire search path is determined solely by bit tests and node indices. This allows us to record enough information during the descent to reconstruct the insertion position later.

Correct solution

Each leaf of the Patricia tree stores an index into the array TEXT. Each internal node $v$ stores only an integer $i(v)$ and two child pointers. No node contains expanded key material.

We assume that during the insertion operation, the new key $K$ is made available in a working buffer with at most one access to TEXT. This is consistent with the requirement that TEXT is referenced at most twice in total.

Step 1: Patricia search with path recording

We perform the standard Patricia search for $K$, starting at the root, but we do not access TEXT during this process.

At each internal node $v$, we examine bit $K[i(v)]$ and follow the corresponding child pointer. We maintain a record of the full search path:

$$ (v_0, b_0), (v_1, b_1), \dots, (v_t, b_t), $$

where $v_0$ is the root, each $b_j \in {0,1}$ records whether we took the left or right edge, and $v_t$ is the leaf reached. This path record uses only in-memory information from the tree structure.

Let the final leaf be $v_t$, containing a TEXT index $p$. The corresponding stored key is $X = \mathrm{TEXT}[p]$.

Step 2: TEXT access and divergence computation

We now perform the second TEXT access to retrieve $X$.

At this point, both keys $K$ and $X$ are fully available in memory. We compute the first differing bit position:

$$ d = \min { i \ge 1 : K[i] \ne X[i] }, $$

with $d$ undefined if $K = X$. If $K = X$, no insertion is performed.

At this stage, no further access to TEXT will occur.

Step 3: locating the insertion position (resolved without circularity)

The earlier error was assuming we could identify the insertion point during search using $d$. Instead, we use the recorded path.

Along the recorded search path, the node indices satisfy the Patricia invariant: if we traverse from root to leaf, the indices $i(v_0), i(v_1), \dots$ are strictly increasing along any segment where the search descends according to bit tests.

This implies that the correct insertion point is determined purely by comparing $d$ with the node indices along the recorded path.

We scan the recorded path (in order from root toward the leaf) and find the last node $v_k$ such that

$$ i(v_k) < d. $$

Such a node always exists at least at the root level in the standard Patricia construction with a head node, and the monotonicity of indices ensures uniqueness of this “last valid predecessor.”

Let $v_{k+1}$ be the next node on the recorded path, or the leaf if $k+1 = t$.

The correct insertion position is between $v_k$ and $v_{k+1}$, specifically on the edge that was followed from $v_k$ toward $v_{k+1}$.

This step is valid because all decisions in the Patricia search depend only on bits $K[i(v)]$, and for all indices $i(v) < d$, the keys $K$ and $X$ agree. Hence the recorded path is exactly the correct traversal for both keys up to level $< d$, and divergence occurs strictly after this point.

Step 4: insertion

We create a new internal node $u$ with

$$ i(u) = d. $$

Let $b = K[d]$. Then we attach:

if $b = 0$, left child of $u$ is the new leaf for $K$, right child is $v_{k+1}$,
if $b = 1$, the roles are reversed.

Finally, we replace the child pointer of $v_k$ that previously pointed to $v_{k+1}$ with a pointer to $u$. If $v_k$ is the special head node case, $u$ becomes the new root.

Correctness

Let $X$ be the existing key at the reached leaf. By construction of $d$, we have $K[i] = X[i]$ for all $i < d$, and $K[d] \ne X[d]$.

Therefore, for every internal node $v$ with $i(v) < d$, the Patricia search decisions for $K$ and $X$ coincide. Hence the recorded path is simultaneously valid for both keys up to level $< d$.

For any node $v$ with $i(v) \ge d$, the branching decisions for $K$ and $X$ may differ, and thus insertion must occur strictly above such nodes. This is exactly ensured by selecting the last node on the path with index less than $d$.

Replacing a single edge by a new internal node preserves the invariant that indices strictly increase along any root-to-leaf path, since $i(u) = d$ is strictly larger than all indices in the upper portion of the path and strictly smaller than any index below the insertion point along the original structure.

All other subtrees remain unchanged, so all previously stored keys remain correctly located.

TEXT access bound

The algorithm performs exactly two accesses to TEXT:

One access to load the new key $K$ into a working buffer.
One access to retrieve the existing key $X$ from the leaf via its TEXT pointer.

All other operations, including search, path recording, computation of $d$, and insertion restructuring, use only in-memory data.

Thus the TEXT array is referenced at most twice, as required.