 Huffman sibling contraction

Replace sibling leaves in a code tree labelled $a,b$ by their common parent in a rooted tree, now a leaf labelled $m$ of weight $w_m=w_a+w_b$. All other codewords stay fixed; each of $a,b$ loses one bit. For any such code tree $T$ and the contracted code tree $T^{\prime }$, their weighted costs satisfyIf $a,b$ have two least weights, the Huffman sibling property gives an optimal prefix code containing this pair. Its contracted prefix code must be optimal for the reduced weights $w^{\prime }$: any cheaper reduced prefix code could be expanded at $m$ by appending $0,1$, giving a cheaper original prefix code. Conversely, expanding any optimal reduced prefix code adds precisely $w_a+w_b$ and attains the original minimum. This is optimal substructure, the justification for repeating the merge in Huffman coding. ^[ref]

In the exchange diagram, $C,D$ contract to weight $0.3$ at leaf depth in a code tree $2$. The reduced expected codeword length is $0.4\cdot 1+0.3\cdot 2+0.3\cdot 2=1.6$ bits; expanding restores $1.6+0.3=1.9$ bits. For $n=2$, the reduction leaves one symbol: allow its temporary codeword to be empty, of cost zero, so expansion gives the two one-bit codewords. This convention is only the terminal reduced problem; the original source has at least two symbols.