TAOCP 6.3 Exercise 14

We consider the Patricia trie organization described in Section 6.

taocpmathematicsalgorithmsvolume-3medium

Section 6.3: Digital Searching

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

Verified: no
Solve time: 10m55s

Solution

We consider the Patricia trie organization described in Section 6.3.3. The trie consists of internal nodes (each containing a bit index and two links) and external nodes (each containing a pointer to a key stored in the array TEXT[1..N]). Duplicate keys are handled by chaining the corresponding external nodes via a LINK field in each external node. Algorithm P (the Patricia search algorithm) takes a key K and terminates successfully with a pointer to the first external node for K.

The following algorithm, executed immediately after a successful termination of Algorithm P, deletes all occurrences of K from TEXT and removes the associated external nodes from the trie. We assume the existence of a back‑pointer array BP[1..N] where BP[i] points to the external node that references TEXT[i]; this array is easily maintained during insertion and is standard for efficient deletion in Patricia.

Algorithm D (Delete all K).

  1. Let X be the external node returned by Algorithm P.
  2. While X ≠ Λ: a. i ← KEY(X) (the index in TEXT of the key for this external node). b. If i < N: - TEXT[i] ← TEXT[N]. - Y ← BP[N] (the external node that pointed to TEXT[N]). - KEY(Y) ← i. - BP[i] ← Y. c. N ← N - 1. d. X' ← LINK(X); return node X to AVAIL; X ← X'.
  3. Remove the primary external node (the one found by Algorithm P) from the trie. Since the search path from the root to this node is still available from Algorithm P's execution (e.g., in a stack or via parent pointers), retrace it to the parent internal node P. Let the sibling of the primary external node be S (if the other link of P points to an external node) or Λ (if the other link points to an internal node or is Λ). Replace the appropriate link of P by S. Return the primary external node to AVAIL.

Invariant. At the start of each iteration of step 2, the set of keys in TEXT[1..N] is exactly the original set minus the keys already deleted; each remaining key has exactly one external node pointing to it, as maintained by the back‑pointer updates in step 2b. The LINK chain starting at X contains precisely the external nodes for K not yet processed.

Termination. The loop in step 2 processes each external node in the finite LINK chain exactly once. Step 3 performs a single trie traversal of length at most the height of the trie.

Complexity. Let c be the number of occurrences of K. Step 2 runs c times, each iteration taking O(1) time. Step 3 takes O(log N) time (height of the trie) or O(1) if a parent pointer was retained during the search. Total time is O(c + log N).

This completes the proof. ∎

Notes

The back‑pointer array BP is essential for the O(1) update in step 2b; without it one would need a linear scan to find the external node corresponding to the moved key, increasing the complexity to O(cN). In a typical Patricia implementation that supports deletion, BP is maintained during insertion and is the standard way to achieve efficient removal.