TAOCP 6.2.2 Exercise 10
Let the incoming keys be $K_1, K_2, \ldots, K_n$, arriving in an arbitrary order.
Section 6.2.2: Binary Tree Searching
Exercise 10. [22] [22] (R. W. Floyd.) Perhaps we are not interested in the sorting property of Algorithm T, but we expect that the input will come in nonrandom order. Devise a way to keep tree search efficient, by making the input “appear to be” in random order.
Verified: yes
Solve time: 1m15s
Solution
Let the incoming keys be $K_1, K_2, \ldots, K_n$, arriving in an arbitrary order. The goal is to transform this stream into an insertion order that is uniformly random, so that Algorithm $T$ behaves as in the analysis of Section 6.2.2.
Introduce an auxiliary array $A[1:n]$. After processing the first $i$ keys, the array will store a permutation of $K_1, \ldots, K_i$, and each of the $i!$ permutations will occur with equal probability.
For each incoming key $K_i$, perform the assignment $A[i] \leftarrow K_i$. Choose an integer $J$ uniformly at random from ${1,2,\ldots,i}$ and interchange $A[i] \leftrightarrow A[J]$. After this interchange, insert $A[i]$ into the binary search tree using Algorithm $T$.
The correctness depends on the distribution of the element moved to position $i$. After the interchange, $A[i]$ is equally likely to be any of $K_1,\ldots,K_i$, since the swap target $J$ is chosen uniformly from $1$ to $i$. Hence, conditioned on the first $i-1$ steps, every element among the first $i$ inputs has probability $1/i$ of occupying position $i$.
Assume inductively that after step $i-1$, the array $A[1],\ldots,A[i-1]$ is uniformly distributed over all $(i-1)!$ permutations of $K_1,\ldots,K_{i-1}$. After placing $K_i$ into position $i$ and performing the random interchange, every element of ${K_1,\ldots,K_i}$ is equally likely to occupy position $i$, and the remaining $i-1$ positions retain a uniform permutation of the remaining elements. Each permutation of $i$ elements can be obtained by exactly $i$ choices of the element placed in position $i$ together with a permutation of the other $i-1$ elements, so each of the $i!$ permutations occurs with probability $1/i!$. This preserves the induction hypothesis.
Thus the sequence $A[1], A[2], \ldots, A[n]$ is a uniformly random permutation of the input keys. Feeding these elements into Algorithm $T$ yields exactly the random insertion model used in Section 6.2.2, so the resulting binary search tree has the same probabilistic behavior and the expected search cost remains on the order of $2 \ln N$ comparisons.
This completes the construction of a method that makes arbitrary input behave as if it were randomly ordered by generating a uniform random permutation online before insertion. ∎