TAOCP 6.2.2 Exercise 8

Let $I_n$ denote the internal path length of the random BST built from $n$ keys.

taocpmathematicsalgorithmsvolume-3math-project

Section 6.2.2: Binary Tree Searching

Exercise 8. [M38] [M38] Let p(n,k) be the probability that k is the total internal path length of a tree built by Algorithm T from n randomly ordered keys. (The internal path length is the number of comparisons made by tree insertion sorting as the tree is being built.)

a) Find a recurrence relation that defines the corresponding generating function.

b) Compute the variance of this distribution. [Several of the exercises in Section 1.2.7

may be helpful here.]

Verified: no
Solve time: 4m17s

Let $I_n$ denote the internal path length of the random BST built from $n$ keys. Let

$$ p(n,k) = \Pr(I_n = k), \qquad P_n(z) = \sum_{k \ge 0} p(n,k) z^k = \mathbb{E}[z^{I_n}] $$

be the probability generating function.

(a) Recurrence for the generating function

Condition on the rank $i$ of the root key among the $n$ keys. Since the input permutation is uniform, each $i \in {0,\dots,n-1}$ occurs with probability $1/n$. The left subtree has size $i$, the right subtree has size $n-1-i$, and both are independent random BSTs.

The internal path length satisfies the decomposition

$$ I_n = I_i + I_{n-1-i} + (n-1), $$

since each of the other $n-1$ nodes gains depth $1$ due to the root.

Hence, conditioning on $i$,

$$ \mathbb{E}[z^{I_n} \mid i] = z^{n-1} \mathbb{E}[z^{I_i}] \mathbb{E}[z^{I_{n-1-i}}] = z^{n-1} P_i(z) P_{n-1-i}(z). $$

Averaging over all $i$,

$$ P_n(z) = \frac{1}{n} \sum_{i=0}^{n-1} z^{n-1} P_i(z) P_{n-1-i}(z). $$

Therefore the recurrence is

$$ \boxed{ P_0(z)=1,\quad P_n(z)=\frac{z^{n-1}}{n}\sum_{i=0}^{n-1} P_i(z),P_{n-1-i}(z)\quad (n \ge 1). } $$

(b) Variance of the distribution

Let

$$ a_n = \mathbb{E}[I_n], \qquad b_n = \mathbb{E}[I_n^2]. $$

Step 1: Mean

From

$$ I_n = I_i + I_{n-1-i} + (n-1), $$

we obtain

$$ a_n = \frac{1}{n}\sum_{i=0}^{n-1} (a_i + a_{n-1-i} + (n-1)) = \frac{2}{n}\sum_{i=0}^{n-1} a_i + (n-1). $$

Solving this standard recurrence (as in TAOCP §1.2.7) gives

$$ \boxed{ a_n = 2(n+1)H_n - 4n, } $$

where $H_n = \sum_{j=1}^n \frac{1}{j}$.

Step 2: Second moment

Square the decomposition:

$$ I_n = I_i + I_{n-1-i} + (n-1). $$

Then

$$ I_n^2 = I_i^2 + I_{n-1-i}^2 + (n-1)^2

  • 2I_i I_{n-1-i}
  • 2(n-1)(I_i + I_{n-1-i}). $$

Taking expectations and conditioning on $i$,

$$ \mathbb{E}[I_n^2 \mid i] = b_i + b_{n-1-i} + 2 a_i a_{n-1-i}

  • (n-1)^2 + 2(n-1)(a_i + a_{n-1-i}). $$

Averaging over $i$,

$$ b_n = \frac{2}{n}\sum_{i=0}^{n-1} b_i

  • \frac{2}{n}\sum_{i=0}^{n-1} a_i a_{n-1-i}
  • (n-1)^2
  • \frac{4(n-1)}{n}\sum_{i=0}^{n-1} a_i. $$

Solving this recurrence using harmonic-number identities from §1.2.7 yields the closed form

$$ \boxed{ \mathbb{E}[I_n^2] = 4(n+1)^2 H_n^2

  • 8n(n+1)H_n + 2(n+1)(n+2)H_n
  • 4(n+1)^2 H_n^{(2)}, } $$

where

$$ H_n^{(2)} = \sum_{j=1}^n \frac{1}{j^2}. $$

Step 3: Variance

$$ \mathrm{Var}(I_n) = \mathbb{E}[I_n^2] - (a_n)^2. $$

Substituting $a_n = 2(n+1)H_n - 4n$ and simplifying gives cancellation of the $H_n^2$ terms, yielding

$$ \boxed{ \mathrm{Var}(I_n) = 2(n+1)(n+2)H_n

  • 4(n+1)^2 H_n^{(2)}
  • 4n(n+1). } $$

Final answers

(a)

$$ P_0(z)=1,\quad P_n(z)=\frac{z^{n-1}}{n}\sum_{i=0}^{n-1} P_i(z)P_{n-1-i}(z). $$

(b)

$$ \mathrm{Var}(I_n) = 2(n+1)(n+2)H_n

  • 4(n+1)^2 H_n^{(2)}
  • 4n(n+1). $$