TAOCP 6.2.2 Exercise 7

Let keys $1,2,\dots,n$ be inserted in random order to form a binary search tree by Algorithm T.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.2: Binary Tree Searching

Exercise 7. [M25] [M25] (S. R. Arora and W. T. Dent.) After n elements have been inserted into an initially empty tree, in random order, what is the average number of comparisons needed by Algorithm T to find the mth largest element, given the key of that element?

Verified: yes
Solve time: 1m16s

Solution

Let keys $1,2,\dots,n$ be inserted in random order to form a binary search tree by Algorithm T. Let $X_m$ denote the node containing the $m$th largest key. The $m$th largest key has rank $k = n-m+1$ when keys are ordered increasingly.

The number of comparisons needed to find a node equals $1$ plus its depth in the tree. Let $D_k$ denote the depth of the node of rank $k$. The required average number of comparisons is

$$ C_{n,m} = 1 + \mathbb{E}[D_k], \quad k = n-m+1. $$

The depth $D_k$ equals the number of ancestors of $k$. For each $i \ne k$, define the indicator variable $I_{i,k}$ which is $1$ if $i$ is an ancestor of $k$ and $0$ otherwise. Then

$$ D_k = \sum_{i \ne k} I_{i,k}, \quad \mathbb{E}[D_k] = \sum_{i \ne k} \mathbb{P}(i \text{ is ancestor of } k). $$

For $i < k$, the keys $i$ and $k$ are separated by $k-i-1$ keys. The key $i$ becomes an ancestor of $k$ exactly when $i$ is the first among the set ${i,i+1,\dots,k}$ to be inserted. Since all $(k-i+1)$ elements of this set are equally likely to be the first inserted among them,

$$ \mathbb{P}(i \text{ is ancestor of } k) = \frac{1}{k-i+1}. $$

For $i > k$, the same argument applied to the set ${k,k+1,\dots,i}$ gives

$$ \mathbb{P}(i \text{ is ancestor of } k) = \frac{1}{i-k+1}. $$

Hence

$$ \mathbb{E}[D_k] = \sum_{i=1}^{k-1} \frac{1}{k-i+1} + \sum_{i=k+1}^{n} \frac{1}{i-k+1}. $$

Reindexing the first sum by $j = k-i+1$ gives $j = 2,\dots,k$, so

$$ \sum_{i=1}^{k-1} \frac{1}{k-i+1} = \sum_{j=2}^{k} \frac{1}{j} = H_k - 1. $$

Reindexing the second sum by $j = i-k+1$ gives $j = 2,\dots,n-k+1$, so

$$ \sum_{i=k+1}^{n} \frac{1}{i-k+1} = \sum_{j=2}^{n-k+1} \frac{1}{j} = H_{n-k+1} - 1. $$

Thus

$$ \mathbb{E}[D_k] = H_k + H_{n-k+1} - 2. $$

Since a successful search requires one additional comparison,

$$ C_{n,m} = 1 + \mathbb{E}[D_k] = H_k + H_{n-k+1} - 1. $$

Substituting $k = n-m+1$ yields

$$ C_{n,m} = H_{n-m+1} + H_m - 1. $$

Therefore,

$$ \boxed{H_{m} + H_{n-m+1} - 1}. $$

This completes the proof. ∎