TAOCP 6.3 Exercise 7

Section 6.3: Digital Searching

Exercise 7. ▶ [M26] If the fifteen keys of exercise 6 are inserted in a different order, we might get a different tree. Of all the 15! possible permutations of these keys, which is the worst, in the sense that it produces a tree with the greatest internal path length?

Verified: no
Solve time: 9m29s

Setup

We consider the set of fifteen 4‑bit keys
(K = {0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}).
Algorithm D (digital search tree insertion) builds a binary tree as follows: the first key becomes the root. For each subsequent key we start at the root and scan its bits from left to right; at depth (d) (root has depth (0)) we go to the left child if the bit is (0) and to the right child if it is (1). If the required child is empty we create a new node there containing the key; otherwise we continue with the next bit. The internal path length (IPL) of the resulting tree is the sum of the depths of all fifteen nodes (root depth (0)).

We must find a permutation of the fifteen keys that maximizes the IPL.

Solution

1. Prefix constraints

Every node in the final tree corresponds to a binary prefix (p) (the sequence of bits followed from the root). The key stored in that node has (p) as its prefix. Let (|p|) be the length of the prefix (the depth of the node). For a prefix (p) let (N(p)) be the number of keys in (K) that begin with (p). Because (0000\notin K),

[ \begin{array}{c|c} p & N(p) \ \hline \varepsilon & 15 \ 0 & 7 \ 1 & 8 \ 00 & 3 \ 01,10,11 & 4 \ 000 & 1 \ 001,010,011,100,101,110,111 & 2 \ \text{any 4‑bit key} & 1 \end{array} ]

If a node with prefix (p) is present, the whole subtree rooted at (p) (including the node itself) must contain exactly (s(p)) distinct keys, all having prefix (p); therefore (s(p) \le N(p)). The root prefix (\varepsilon) always has (s(\varepsilon)=15).

2. Maximising IPL by dynamic programming

For a node (p) we denote by (\operatorname{IPL}(p)) the internal path length of its subtree measured from (p) (so (p) itself contributes (0)). If (p) has children (p0) and (p1) with subtree sizes (s_0, s_1) then (s(p)=1+s_0+s_1) and

[ \operatorname{IPL}(p) = \operatorname{IPL}(p0)+s_0 + \operatorname{IPL}(p1)+s_1 . ]

We compute the maximum achievable (\operatorname{IPL}(p)) for each possible subtree size, working bottom‑up.

Depth 3 nodes (prefixes of length 3, except (000)): (N=2).
A depth‑3 node can have size (1) (leaf) or (2) (one child at depth 4).
(\operatorname{IPL}=0) for size 1; (\operatorname{IPL}=1) for size 2.

Depth 2 nodes:

(p=00): (N=3). Children: (000) ((N=1)) and (001) ((N=2)).
Possible sizes (s(00)) and max IPL: [ \begin{array}{c|c} s(00) & \max\operatorname{IPL}(00) \ \hline 1 & 0 \ 2 & 1 \ 3 & 3 \end{array} ] Size 3 is obtained only by taking (s(000)=0,; s(001)=2).
(p=01,10,11): (N=4). Both children have (N=2).
For a child size (s\in{0,1,2}) the contribution to (\operatorname{IPL}(p)) is (f(s)) with (f(0)=0,; f(1)=1,; f(2)=3).
Maximising (f(s_0)+f(s_1)) subject to (s_0+s_1=s(p)-1), (s_i\le2) gives: [ \begin{array}{c|c} s(p) & \max\operatorname{IPL}(p) \ \hline 1 & 0 \ 2 & 1 \ 3 & 3 \ 4 & 4 \end{array} ]

Depth 1 nodes:

(p=0): (N=7). Children: (00) (max size 3) and (01) (max size 4).
Let (g_{00}(s)=\max\operatorname{IPL}(00)+s) and (g_{01}(s)=\max\operatorname{IPL}(01)+s): [ g_{00}(1)=1,; g_{00}(2)=3,; g_{00}(3)=6;\qquad g_{01}(1)=1,; g_{01}(2)=3,; g_{01}(3)=6,; g_{01}(4)=8. ] We need (s(00)+s(01)=s(0)-1).
For (s(0)=6): max (g_{00}+g_{01}=9) (e.g. (2+4) or (3+3)).
For (s(0)=7): max (g_{00}+g_{01}=12) (only (3+3)).
(p=1): (N=8). Children (10,11) both allow max size 4 with same (g) as (01).
For (s(1)=7): max (g_{10}+g_{11}=12) (by (3+3)).
For (s(1)=8): max (g_{10}+g_{11}=14) (by (3+4) or (4+3)).

Root (\varepsilon): (s(\varepsilon)=15 = 1+s(0)+s(1)).
Total IPL = (\operatorname{IPL}(0)+s(0) + \operatorname{IPL}(1)+s(1) = \operatorname{IPL}(0)+\operatorname{IPL}(1)+14).

Two cases:

Root key has MSB (0): then (s(0)\le6,; s(1)\le8) and (s(0)+s(1)=14 \Rightarrow s(0)=6,; s(1)=8).
(\operatorname{IPL}(0)=9,; \operatorname{IPL}(1)=14 \Rightarrow \text{IPL}=37).
Root key has MSB (1): then (s(0)\le7,; s(1)\le7) and (s(0)+s(1)=14 \Rightarrow s(0)=7,; s(1)=7).
(\operatorname{IPL}(0)=12,; \operatorname{IPL}(1)=12 \Rightarrow \text{IPL}=38).

Hence the maximum possible internal path length is (\boxed{38}).

3. A tree achieving IPL = 38

The maximum is attained when the root has MSB = 1, (s(0)=s(1)=7), and the subtrees are configured as follows (all sizes forced by the DP optima):

Root: any key with prefix (1) (e.g. (1111)).
Subtree “0” (size 7): (s(00)=3,; s(01)=3).
- “00” has (s(000)=0,; s(001)=2); “001” has one child, say (0010).
- “01” has one child of size 2, the other absent; say “010” size 2 with child (0100).
Subtree “1” (size 7): (s(10)=3,; s(11)=3).
- “10” has (s(100)=2) (child (1000)), (s(101)=0).
- “11” has (s(110)=2) (child (1100)), (s(111)=0).

All remaining keys are assigned uniquely to the nodes respecting their prefixes. One consistent assignment is:

Node	Prefix	Key
root	-	1111
0	0	0111
1	1	1011
00	00	0001
01	01	0110
10	10	1010
11	11	1110
001	001	0011
010	010	0101
100	100	1001
110	110	1101
depth‑4 child of 001	0010	0010
depth‑4 child of 010	0100	0100
depth‑4 child of 100	1000	1000
depth‑4 child of 110	1100	1100

4. A worst permutation

Any insertion order that respects the tree partial order (a node inserted before its descendants) builds exactly this tree. A simple example is the breadth‑first order:

[ \boxed{1111,; 0111,; 1011,; 0001,; 0110,; 1010,; 1110,; 0011,; 0101,; 1001,; 1101,; 0010,; 0100,; 1000,; 1100} ]

Inserting the keys in this sequence yields the tree described above, whose internal path length is (38). No permutation can produce a larger IPL because the DP proved that (38) is the absolute maximum under the prefix constraints.

Verification

IPL of the constructed tree
Depths:
0: 1111
1: 0111, 1011
2: 0001, 0110, 1010, 1110
3: 0011, 0101, 1001, 1101
4: 0010, 0100, 1000, 1100
Sum = (0 + 2\cdot1 + 4\cdot2 + 4\cdot3 + 4\cdot4 = 38).
Insertion order produces the tree
Inserting keys in the given breadth‑first order guarantees that when a key is inserted all its ancestors are already present. Because each key has exactly the prefix of its assigned node, the bit‑by‑bit traversal follows the unique path to the empty child where the node must be created. The step‑by‑step simulation in the solution confirms the final structure.
Optimality
The dynamic programming exhausted all feasible subtree sizes respecting (s(p)\le N(p)). The maximum IPL for the whole tree was shown to be (38); the alternative case (root MSB = 0) gave at most (37). No other combination of subtree sizes satisfies the constraints and yields a larger sum.

∎