= Solution
For an <odd integer> $m\geq3$, <ternary Huffman coding> repeatedly merges \b[three] smallest weights.
Start with one <tree leaf> for each source symbol, weighted by its <probability>. While more than one weighted object remains, choose the three objects with least weights, create their common <tree parent> with weight equal to their sum, and replace the three by that <tree parent>. Newly created <tree parents> participate in subsequent choices. Each merge reduces the number of objects by two; an <odd number> of objects therefore reaches three and then one, never an unmergeable pair. The final object is the <tree root> of the <code tree>.
Label the three outgoing <edges> at each internal <vertex> by $0,1,2$ in any order. The digits along the root-to-leaf <graph path> give each symbol's <codeword>. <Tree leaves> cannot be ancestors of other <tree leaves>, so this is a <prefix code>. Ties can be resolved arbitrarily. The <expected codeword length> is measured in <trits>, and equals the sum of all merge weights, because each merge adds one digit to every <codeword> below it.
The structural reason for merging three is that the positive-weight, odd-leaf case has a <full ternary tree>. Its deepest <sibling codeword> triple can receive the three least weights by exchanging <tree leaf> labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.
Back to article page
