= Shape of minimum-cost positive-weight ternary prefix trees
For a finite source <alphabet> with at least two symbols and strictly positive weights, every <ternary prefix code> minimizing weighted <codeword length> has all internal <vertices> of <outdegree> three, except possibly one of <outdegree> two whose <tree children> are deepest <tree leaves>.
To prove this, let $L$ be the greatest <tree leaf> depth. A missing <tree child> at any depth $n<L$ would permit moving a deepest <tree leaf> into that vacant branch, strictly reducing its positive weighted cost. Thus all internal <vertices> above depth $L-1$ have three <tree children>. <Tree parents> at depth $L-1$ have only <tree leaves> as <tree children>; one <tree child> would permit contraction and strict improvement. If two such <tree parents> each had two <tree children>, move one <tree child> of the second into the first <tree parent>'s third slot, preserving its depth, and contract the second <tree parent>'s remaining <tree child>. This again strictly improves cost. There is therefore at most one binary <tree parent>. If the number of symbols is an <odd number>, the leaf-count formula for a <full ternary tree> forces $N_2$ to be an <even integer>; since $N_2\leq1$, there is no binary <tree parent>.
Strict positivity matters. For <probabilities> $(1,0,0)$, the <prefix code> $(0,10,110)$ minimizes <expected codeword length> at one <trit>, yet has unary <vertices> and a deepest <tree leaf> without a <sibling codeword>. Removing or rearranging zero-weight branches can select a reduced minimizer, but arbitrary minimizers need not have the positive-weight shape.
Back to article page
