TAOCP 6.3 Exercise 32
Let keys be infinite binary sequences generated by independent unbiased bits.
Section 6.3: Digital Searching
Exercise 32. [M21] [M21] What is the average value of the sum of all SKIP fields in a random Patrician tree with N, 1 internal nodes?
Verified: no
Solve time: 1m50s
Solution
Let keys be infinite binary sequences generated by independent unbiased bits. The Patrician tree is the compressed binary trie in which each internal node stores a SKIP value equal to the number of bit positions advanced from its parent’s test position to its own test position.
Let $L_N$ denote the external path length of the corresponding full binary trie built from the same $N$ keys before path compression. Each comparison in the full trie corresponds to advancing exactly one bit position, hence $L_N$ counts the total number of bit tests made when all keys are inserted into the uncompressed structure.
In the Patrician tree, each internal node replaces a maximal unary chain in the full trie by a single node. If an internal node has SKIP value $s$, then in the full trie the corresponding path contributes $s$ unit edges instead of $1$ node transition in the compressed representation. The compression reduces each such chain by $s-1$, hence each internal node contributes a reduction of exactly $s-1$ to the total bit-advance count.
Let $S_N$ be the sum of all SKIP fields. Summing over all internal nodes gives
$$ L_N = S_N + (N-1), $$
since a binary Patrician tree with $N-1$ internal nodes has exactly $N-1$ compressed transitions replacing the full trie structure.
Therefore,
$$ S_N = L_N - (N-1). $$
For a random binary trie on $N$ keys, the expected external path length satisfies
$$ \mathbb{E}[L_N] = N H_N, $$
where $H_N = \sum_{k=1}^N \frac{1}{k}$, by the standard decomposition of external path length into contributions of independent bit levels and the fact that at level $j$ each key contributes $1$ unless separated earlier, yielding harmonic accumulation over occupancy probabilities.
Taking expectations in $S_N = L_N - (N-1)$ gives
$$ \mathbb{E}[S_N] = \mathbb{E}[L_N] - (N-1) = N H_N - (N-1). $$
Thus the average value of the sum of all SKIP fields is
$$ \boxed{N H_N - (N-1)}. $$
This completes the proof. ∎