TAOCP 2.3.4.5 Exercise 2

Section 2.3.4.5: Path Length

Exercise 2. [**] [17] Draw an extended binary tree with terminal nodes containing the weights 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, having minimum weighted path length.

Verified: yes
Solve time: 2m42s

---

Solution to Exercise 2.3.4.5.2

We are asked to draw an extended binary tree with terminal nodes having weights

$$ 1,4,9,16,25,36,49,64,81,100 $$

such that the weighted path length is minimal.

Step 1: Apply Huffman's algorithm

To minimize the weighted path length, we construct a Huffman tree. Arrange the weights in nondecreasing order:

$$ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. $$

Huffman's algorithm repeatedly combines the two smallest weights into a new internal node whose weight is the sum of the two. We record each combination:

1. Combine $1$ and $4$ to form $5$:

$$ 5,9,16,25,36,49,64,81,100 $$

1. Combine $5$ and $9$ to form $14$:

$$ 14,16,25,36,49,64,81,100 $$

1. Combine $14$ and $16$ to form $30$:

$$ 25,30,36,49,64,81,100 $$

1. Combine $25$ and $30$ to form $55$:

$$ 36,49,55,64,81,100 $$

1. Combine $36$ and $49$ to form $85$:

$$ 55,64,81,85,100 $$

1. Combine $55$ and $64$ to form $119$:

$$ 81,85,100,119 $$

1. Combine $81$ and $85$ to form $166$:

$$ 100,119,166 $$

1. Combine $100$ and $119$ to form $219$:

$$ 166,219 $$

1. Combine $166$ and $219$ to form $385$, which is the total weight of the root.

Step 2: Construct the tree

We now reconstruct the extended binary tree from the merge sequence. Each internal node corresponds to one of the combined weights above, with two children being the weights that were combined.

We label internal nodes by the sum of the weights of their subtrees, and terminal nodes by the original weights:

1. Internal node $5$ has children $1$ and $4$.
2. Internal node $14$ has children $5$ (from step 1) and $9$.
3. Internal node $30$ has children $14$ (from step 2) and $16$.
4. Internal node $55$ has children $25$ and $30$ (from step 3).
5. Internal node $85$ has children $36$ and $49$.
6. Internal node $119$ has children $55$ (from step 4) and $64$.
7. Internal node $166$ has children $81$ and $85$ (from step 5).
8. Internal node $219$ has children $100$ and $119$ (from step 6).
9. Root node $385$ has children $166$ and $219$ (from steps 7 and 8).

This specifies a unique extended binary tree.

Step 3: Tree diagram

We can represent the extended binary tree in a textual form as follows, showing the hierarchy:

                  [385]
                 /     \
             [166]      [219]
            /    \     /     \
          81     [85] 100    [119]
                /   \       /     \
              36     49   [55]    64
                             / \
                           25   [30]
                                /  \
                             [14] 16
                             /  \
                           [5]   9
                          /   \
                        1      4

• Square brackets [ ] denote internal nodes with weight equal to the sum of their subtree.
• Leaves are the terminal nodes with the original weights.

This is a valid extended binary tree with the specified terminal nodes.

Step 4: Verification

• The number of leaves is $10$, matching the number of given weights.
• Each internal node has exactly two children.
• The weighted path length is minimized because Huffman's algorithm was used.

Thus the constructed tree satisfies the exercise requirements.

∎