0
$\begingroup$

Question. There's guarantee to be codeword of length 1 if some characters occur frequency > 2/5.

hypothetical tree with no codewords of length 1

Proof: Assume for the purpose of obtaining a contradiction that there is no codeword of length $1$. Then both children of the root can not be leaves. Let the left child of the root be $L$, right child $R$, and the two children of each subtree $a, b$, and $c, d$ respectively.

Without loss of generality assume that the character with frequency greater than $2/5$ appears in the subtree $a$ of the left child of the root. The right subtree $R$ will have to have combined weight more than $2/5$, since otherwise $R$ being smaller than $a$ would be joined first with $b$. The combined weight on $b$ will be less than $1/5$ since the total sum of frequencies has to add up to $1$.

I understand the first paragraph of the proof. But I'm having trouble understanding the second paragraph. Why frequency of $R$ has to be $< 3/5$ just because frequency of $a$ $> 2/5$? My understanding is $R$ can be greater than $a$ but less than $L$.

At the same time, the right subtree has to have cumulative weight less than $3/5$, since one of the elements in $L$ has frequency in excess of $2/5$. One of the two subtrees of $R$ has to have weight less then $3/10$, but then it would be combined with subtree $b$, since the total weight of $R$ is greater than $2/5$ and so the other subtree of $R$ would have weight greater than that of $b$.

This is a contradiction, since $b$ was joined with $a$, so there is guaranteed to be a codeword of length $1$.

I appreciate your explanation.

$\endgroup$
0
$\begingroup$

The total weight of all the elements is $1$. The total weight of $R$ is the sum of the weights of its elements, and the total weight of $L$ is the sum of the weights of its elements, and every element is in exactly one of these subtrees, so the weight of $R$ plus the weight of $L$ must be $1$. Let $r$ be the weight of $R$ and $\ell$ the weight of $L$. $L$ has an element whose weight is more than $\frac25$, so $\ell>\frac25$, and therefore

$$r=1-\ell<1-\frac25=\frac35\;.$$

$\endgroup$
  • $\begingroup$ That clears up. Thanks!! $\endgroup$ – user3273345 Oct 22 '15 at 20:02
  • $\begingroup$ @user3273345: You’re welcome! $\endgroup$ – Brian M. Scott Oct 22 '15 at 20:02

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.