TAOCP 5.2.3 Exercise 38

The subtree sizes of a complete binary tree with \(N\) internal nodes (or equivalently, of a heap of \(N\) elements) satisfy the following recurrence.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.2.3: Sorting by Selection

Exercise 38. [M21] Find a simple recurrence relation for the multiset $M_N$ of subtree sizes in a heap or in a complete binary tree with $N$ internal nodes.

5.2.4. Sorting by Merging

Merging (or collating) means the combination of two or more ordered files into a single ordered file. For example, we can merge the two files 503 703 765 and 087 512 677 to obtain 087 503 512 677 703 765. A simple way to accomplish this is to compare the two smallest items, output the smallest, and then repeat the same process. Starting with

$$\left{ \begin{array}{l} 503\ 703\ 765 \ 087\ 512\ 677 \end{array} \right.$$

we obtain

$$087 \left{ \begin{array}{l} 503\ 703\ 765 \ 512\ 677 \end{array} \right.$$

then

$$087\ 503 \left{ \begin{array}{l} 703\ 765 \ 512\ 677 \end{array} \right.$$

and

$$087\ 503\ 512 \left{ \begin{array}{l} 703\ 765 \ 677 \end{array} \right.$$

and so on. Some care is necessary when one of the two files becomes exhausted; a detailed description of the process appears in the following algorithm:

Algorithm M (Two-way merge). This algorithm merges nonempty ordered files $x_1 \le x_2 \le \cdots \le x_m$ and $y_1 \le y_2 \le \cdots \le y_n$ into a single file $z_1 \le z_2 \le \cdots \le z_{m+n}$.

M1. [Initialize.] Set $i \leftarrow 1$, $j \leftarrow 1$, $k \leftarrow 1$.

M2. [Find smaller.] If $x_i \le y_j$, go to step M3, otherwise go to M5.

Verified: no
Solve time: 14m22s

The subtree sizes of a complete binary tree with (N) internal nodes (or equivalently, of a heap of (N) elements) satisfy the following recurrence.

Let (M_N) be the multiset of subtree sizes (number of internal nodes in the subtree) for all (N) internal nodes.

  • (M_1 = {1}).
  • For (N > 1), the tree consists of a root (size (N)), a left subtree with (L(N)) internal nodes, and a right subtree with (R(N)) internal nodes, where (L(N)+R(N)=N-1).
    The multisets for the left and right subtrees are again of the same form, so [ M_N = {N} \cup M_{L(N)} \cup M_{R(N)}. ]

The values (L(N)) and (R(N)) are determined by the structure of the complete binary tree.
Let (h = \lfloor \log_2(N+1) \rfloor) be the height of the tree (number of levels of internal nodes in the corresponding full tree).
The last level of internal nodes contains (N - (2^{h-1}-1)) nodes, and the left subtree receives the first (\min(2^{h-2},, N - 2^{h-1}+1)) of them. Hence [ L(N) = 2^{h-2} - 1 + \min\bigl(2^{h-2},; N - 2^{h-1} + 1\bigr), \qquad R(N) = N - 1 - L(N). ]

Equivalently, with (m = 2^{\lfloor \log_2 N \rfloor}), [ L(N) = \min!\bigl(m-1,; N - m/2\bigr), \qquad R(N) = N - 1 - L(N). ]

This recurrence completely defines the multiset (M_N) for all (N\ge 1).

∎