TAOCP 6.2.1 Exercise 25

Section 6.2.1: Searching an Ordered Table

Exercise 25. [M25] [M25] Suppose that a binary tree has az internal nodes and by external nodes on level k, for k = 0, 1, .... (The root is at level zero.) Thus in Fig. 8 we have (ao, QA1,---5 as) = (1, 2,4, 4, 1,0) and (bo, bi, sey bs) = (0, 0, 0,4, 7, 2).

a) Show that a simple algebraic relationship holds between the generating functions A(z) = do, anz* and B(z) = Yo, bez".

b) The probability distribution for a successful search in a binary tree has the generating function g(z) = zA(z)/N, and for an unsuccessful search the generating function is h(z) = B(z)/(N +1). (Thus in the text’s notation we have Cy = mean(g), Cy, = mean(h), and Eq. (2) gives a relation between these quantities.) Find a relation between var(g) and var(h).

Verified: yes
Solve time: 1m42s

Solution

Let $a_k$ and $b_k$ denote the numbers of internal and external nodes on level $k$, respectively. Let

$$ T_k = a_k + b_k . $$

Each internal node has exactly two children, and each external node has none, so every node on level $k+1$ arises as a child of an internal node on level $k$. Hence

$$ T_{k+1} = 2a_k \quad (k \ge 0). $$

Introduce generating functions

$$ A(z) = \sum_{k \ge 0} a_k z^k, \qquad B(z) = \sum_{k \ge 0} b_k z^k, \qquad T(z) = \sum_{k \ge 0} T_k z^k . $$

Multiplying $T_{k+1} = 2a_k$ by $z^{k+1}$ and summing over $k \ge 0$ yields

$$ \sum_{k \ge 0} T_{k+1} z^{k+1} = 2z \sum_{k \ge 0} a_k z^k . $$

The left-hand side equals $T(z) - T_0$, so

$$ T(z) - T_0 = 2zA(z). $$

Since $T(z) = A(z) + B(z)$, it follows that

$$ A(z) + B(z) = T_0 + 2zA(z), $$

hence

$$ B(z) = T_0 + (2z - 1)A(z). $$

In the binary tree normalization used in the section, the root is a single internal node and no external node appears at level $0$, so $a_0 = 1$, $b_0 = 0$, and $T_0 = 1$. Therefore

$$ \boxed{B(z) = 1 + (2z - 1)A(z)} . $$

Let

$$ g(z) = \frac{zA(z)}{N}, \qquad h(z) = \frac{B(z)}{N+1}. $$

Define $G(z) = g(z)$ and $H(z) = h(z)$. Since $G(1) = H(1) = 1$, both are probability generating functions.

From $G(z) = zA(z)/N$, one obtains

$$ A(z) = \frac{N}{z} G(z). $$

Substituting into $B(z) = 1 + (2z - 1)A(z)$ gives

$$ B(z) = 1 + (2z - 1)\frac{N}{z}G(z). $$

Hence

$$ H(z) = \frac{1}{N+1} + \frac{N}{N+1}(2z - 1)\frac{G(z)}{z}. $$

Set $\alpha = \frac{N}{N+1}$ and define $F(z) = \frac{G(z)}{z}$. Then

$$ H(z) = \frac{1}{N+1} + \alpha(2z - 1)F(z). $$

Since $G(1)=1$, it follows that $F(1)=1$.

Differentiate $F(z)$:

$$ F'(z) = \frac{G'(z)z - G(z)}{z^2}, $$

$$ F'(1) = G'(1) - 1. $$

Let $\mu_g = G'(1)$. Then

$$ F'(1) = \mu_g - 1. $$

Differentiate again:

$$ F''(z) = \frac{G''(z)z^2 - 2z(G'(z)z - G(z))}{z^4}, $$

$$ F''(1) = G''(1) - 2G'(1) + 2G(1). $$

Since $G(1)=1$,

$$ F''(1) = G''(1) - 2\mu_g + 2. $$

Differentiate $H(z)$:

$$ H'(z) = \alpha\bigl(2F(z) + (2z - 1)F'(z)\bigr). $$

Evaluating at $z=1$,

$$ \mu_h = H'(1) = \alpha\bigl(2 + (\mu_g - 1)\bigr) = \alpha(\mu_g + 1). $$

Differentiate again:

$$ H''(z) = \alpha\bigl(4F'(z) + (2z - 1)F''(z)\bigr), $$

$$ H''(1) = \alpha\bigl(4(\mu_g - 1) + (G''(1) - 2\mu_g + 2)\bigr) = \alpha\bigl(G''(1) + 2\mu_g - 2\bigr). $$

For a probability generating function $P(z)$,

$$ \operatorname{var}(P) = P''(1) + P'(1) - (P'(1))^2. $$

Thus

$$ \operatorname{var}(g) = G''(1) + \mu_g - \mu_g^2, $$

and

$$ \operatorname{var}(h) = H''(1) + \mu_h - \mu_h^2. $$

Substituting $\mu_h = \alpha(\mu_g + 1)$ and $H''(1)$,

$$ \operatorname{var}(h) = \alpha(G''(1) + 2\mu_g - 2) + \alpha(\mu_g + 1) - \alpha^2(\mu_g + 1)^2. $$

Expanding and regrouping terms gives

$$ \operatorname{var}(h) = \alpha\bigl(G''(1) + \mu_g - \mu_g^2\bigr)

\alpha(1-\alpha)\mu_g^2 + 2\alpha(1-\alpha)\mu_g

\alpha(1+\alpha). $$

Using $\operatorname{var}(g) = G''(1) + \mu_g - \mu_g^2$, this becomes

$$ \operatorname{var}(h) = \alpha,\operatorname{var}(g)

\alpha(1-\alpha)(\mu_g^2 + 2\mu_g)

\alpha(1+\alpha). $$

Since $\alpha = \frac{N}{N+1}$ and $1-\alpha = \frac{1}{N+1}$, this relation is fully determined in terms of $N$ and the first moment $\mu_g$.

This completes the solution. ∎