TAOCP 6.2.2 Exercise 38

Section 6.2.2: Binary Tree Searching

Exercise 38. [M20] [M20] Explain why Theorem M holds in general, although we have only proved it in the case so < 81 < 82 <++: < Sn.

Verified: yes
Solve time: 1m27s

Solution

Let $s_0, s_1, \ldots, s_n$ be arbitrary distinct keys. Let $r(s_i)$ denote the rank of $s_i$ in increasing order, so that ${r(s_0),\ldots,r(s_n)}={1,\ldots,n+1}$ and $s_i < s_j$ if and only if $r(s_i) < r(s_j)$.

Consider Algorithm T, where all comparisons are of the form $K < \mathrm{KEY}(P)$ or $K > \mathrm{KEY}(P)$. Replace each key $s_i$ by its rank $r(s_i)$. Every comparison between keys is preserved under this replacement, since the ordering relation is unchanged by the rank map.

During insertion, the path taken by a key $K$ depends only on the outcomes of comparisons with existing node keys. Since replacing each key by its rank preserves every comparison outcome, the sequence of links followed by each insertion is identical to the sequence obtained when inserting the ordered keys $1,2,\ldots,n+1$ in the same relative order.

Hence the binary search tree produced from ${s_0,\ldots,s_n}$ is isomorphic, as an ordered binary tree, to the tree produced from ${1,\ldots,n+1}$ with the same insertion sequence. In particular, corresponding nodes occur at identical positions in the two trees, and every search path length is unchanged under the relabeling.

The statement of Theorem M depends only on the structure of the tree produced by Algorithm T and on the comparison outcomes along search paths, both of which are invariant under order-preserving relabeling of keys. Therefore, a proof established for the special case $s_0 < s_1 < \cdots < s_n$ applies to arbitrary distinct keys after applying the rank transformation.

This completes the proof. ∎