1
$\begingroup$

I'm ok following the passages generally used to prove this theorem, like in this question concerning the same subject. Anyway i've the unpleasant feeling that the proof lacks something to be completely understood, perhaps because considered obvious by many people.

We know that a binary tree corresponding to the optimal prefix code is full. To produce a proof you start considering a binary tree $T$ corresponding to optimal prefix code, and suppose it's not full. If it's not full, then it must contains at least a node $u$ with just one child $v$. If you replace $u$ with $v$ you end up with a new tree $T'$ whose leafs in the subtree rooted in $u$ require less bits to be encoded: so the average bits per letter of the prefix code corresponding to $T'$ is smaller and this contradicts the optimality of $T$.

enter image description here

As far i can see, with this proof, we know that if we had the possibility to erase useless nodes we would obtain trees with best encoding, and therefore they must be full. But how do we prove that these trees actually exist?

I think that you can always replace nodes that aren't leafs, as stated by the proof, because they are just "auxiliary": you don't loose any information replacing them as long as the structure of the new tree you obtain is still valid to produce a prefix code. So, starting from a tree $T$ that is not full, $T'$ always exists.

Is this interpretation correct?

$\endgroup$
1
$\begingroup$

You can formulate this proof in completely constructive terms. Starting with any prefix code, consider any node $v$ which has exactly one child $w$, and contract the edge $(v,w)$. Repeat this as long as no node has exactly one child. Since each operation decreases the number of nodes, we know that after finitely many iterations we reach a full binary tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.