TAOCP 6.3 Exercise 10

Section 6.3: Digital Searching

Exercise 10. [23] [23] Given a file in which all the keys are n-bit binary numbers, and given a search argument K = 6; b2...bn, suppose we want to find the maximum value of & such that there is a key in the file beginning with the bit pattern 6; b2...b,%. How can we do this efficiently if the file is represented as

a) a binary search tree (Algorithm 6.2.2T)?

b) a binary trie (Algorithm T)?

c) a binary digital search tree (Algorithm D)?

Verified: yes
Solve time: 1m28s

---

Solution

Let the keys be $n$-bit binary numbers. For a binary string $X$, write $X[1..k]$ for its prefix of length $k$. The problem asks for the maximum $k$ such that some stored key begins with $K[1..k]$. Equivalently, for each $k$, there exists a key $Y$ in the file whose first $k$ bits equal $K[1..k]$, and we seek the largest such $k$.

For a fixed prefix $P$ of length $k$, the set of all $n$-bit numbers beginning with $P$ forms a contiguous interval in binary order, namely all numbers between $P0\ldots0$ and $P1\ldots1$. This interval characterization will be used in part (a).

a) Binary search tree (Algorithm 6.2.2T)

Let $P = K[1..k]$. Define two $n$-bit keys

$$ L(P) = P00\ldots0, \quad U(P) = P11\ldots1. $$

A key begins with prefix $P$ if and only if it lies in the interval

$$ L(P) \le Y \le U(P) $$

in the binary numeric order used by the binary search tree.

Thus the required condition for a given $k$ is that the search interval $[L(K[1..k]), U(K[1..k])]$ contains at least one node of the binary search tree.

To test this efficiently in a binary search tree, one performs a range search in which each visited node with key $X$ is compared with the interval bounds. If $X < L(P)$, then every key in the left subtree is smaller than $L(P)$ and can be ignored, so only the right subtree is relevant. If $X > U(P)$, only the left subtree is relevant. If $L(P) \le X \le U(P)$, a valid key exists and the prefix condition holds for this $k$.

This procedure yields a decision procedure for each $k$. To obtain the maximum $k$, one applies this test for increasing prefix lengths until the first failure, or equivalently performs a binary search over $k$ using the same interval-existence test as the predicate.

Each test is a standard binary search tree range query, and therefore follows the same path structure as Algorithm 6.2.2T, except that both subtrees may be explored when the current node lies inside the interval.

The maximal $k$ is the largest prefix length for which the interval $[L(K[1..k]), U(K[1..k])]$ intersects the set of stored keys. ∎

b) Binary trie (Algorithm T)

In a binary trie, each node corresponds exactly to a prefix of some stored key, and each level corresponds to one bit position.

Starting at the root, one follows the path determined by the bits of $K$. At level $k$, the traversal uses the $k$th bit of $K$ to select the corresponding branch.

If at some level $k$ the required link is null, then no key in the file has prefix $K[1..k]$, and the process stops. The last successful level is the largest prefix length for which a node exists on the path of $K$.

If all $n$ steps succeed, then the full key $K$ matches a stored key or lies within the trie path structure.

Thus the maximum $k$ is exactly the depth reached during a single trie descent following the bits of $K$, stopping at the first missing link. ∎

c) Binary digital search tree (Algorithm D)

In a binary digital search tree, each node stores a full key, but the branching structure is determined by successive bits encountered during insertion. A search for a key follows the same sequence of bit tests used during construction.

To determine the longest prefix of $K$ that matches some key path, one performs a traversal guided by the bits of $K$ exactly as in Algorithm D, but without requiring full equality at a node.

At a node reached after following the first $k-1$ bit decisions, the next step inspects the $k$th bit of $K$ and moves to the corresponding subtree if the pointer exists. The existence of that pointer guarantees that at least one stored key has the same routing decisions for the first $k$ bits, hence at least one key shares prefix $K[1..k]$.

If at some stage the required child pointer is null, no key in the file can extend the prefix determined by the previous bits, and the process stops.

Therefore the maximal $k$ is the number of successive bit-directed transitions starting from the root that remain defined along the path dictated by $K$. This is precisely the depth reached in the digital search tree when using $K$ as the guiding bit sequence. ∎