[Solved]: Not understand exchanging argument proof for optimal prefix code

Problem Detail: 

I am currently reading the Algorithm Design textbook by Kleinberg and Tardos and I am having difficulty understanding a proof using an exchange argument

Statement: A binary tree corresponding to the optimal prefix code is full

Proof: This is easy to prove using an exchange argument. Let $T$ denote the binary tree corresponding to the optimal prefix code, and suppose it contains a node $u$ with exactly one child $v$. Now convert $T$ into a tree $T′$ by replacing node $u$ with $v$. To be precise, we need to distinguish two cases. If $u$ was the root of the tree, we simply delete node $u$ and use $v$ as the root. If $u$ is not the root, let $w$ be the parent of $u$ in T. Now we delete node $u$ and make $v$ be a child of $w$ in place of $u$. This change decreases the number of bits needed to encode any leaf in the subtree rooted at node $u$, and it does not affect other leaves. So the prefix code corresponding to $T′$ has a smaller average number of bits per letter than the prefix code for $T$, contradicting the optimality of $T$.

Number of things I do not understand.

1) I thought in an exchange argument, you assume you have a solution T and an optimal solution $T^{*}$ and you prove that your solution T is no worse than $T^{*}$ implying T is an optimal solution, but they're not doing that here.

2) They also state that they will "convert $T$ into a tree $T'$ by replacing node $u$ with $v$" but they don't assume that $T'$ is an optimal solution. Why?

3) How does contradicting optimality of $T$ prove that "A binary tree corresponding to the optimal prefix code is full"?

Asked By : user2635911

Answered By : Yuval Filmus

What Kleinberg and Tardos show is that given a tree $T$ containing a node with a single child, they can come up with a strictly better tree $T'$, showing that $T$ isn't optimal. Therefore an optimal tree cannot have a node with a single child. Whether this qualifies as an exchange argument or not is not so important.

More generally, the form of the argument is "if X doesn't satisfy P then X is not optimal; hence any optimal X satisfies P". In order to show that X not satisfying P cannot be optimal, they modify X to obtain a better X'. This is a common enough pattern which doesn't usually have a name attached to it.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/31965