1
$\begingroup$

Consider the following Huffman trees:
enter image description here

I was asked if those trees can have the same corpus. My answer was no, based on these calculations:

For the right tree:
$a_1 \le a_2$
$a_1 + a_2 \le a_5$
$a_3 \le a_4$
$a_1 + a_2 + a_5 \le a_3 + a_4$

For the left tree:
$a_1 \le a_2$
$a_3 \le a_4$
$a_1 + a_2 + a_3 + a_4 \le a_5$

Adding the last equations from each tree we have that:
$2a_1 + 2a_2 \le 0$ Which is a contradiction because frequency cannot be negative.

Nevertheless, I understood that there is a possibility that the two trees would have the same corpus. For instance, consider $1,1,1,2,3$.

So, where do my calculations go wrong?

$\endgroup$
1
$\begingroup$

Your inequalities are based on the assumption that the left child of an inner node is not bigger than the right child. However, this does not hold. (Note that the condition is violated for the root of the right tree.)

Instead we do know that whenever the algorith chose to unite two nodes, there were no nodes with smaller weight present. For the left tree we find:

  • $a_1$ ad $a_2$ were joined before $a_5$ was joined to another node, so $$a_1 \leq a_5\text{ and }a_2\leq a_5.$$
  • We do not know, if $a_1$ and $a_2$ were joined before or after $a_3$ and $a_4$, but in case the latter pair was joined first, we find $a_1 \leq a_3+a_4$ and $a_2\leq a_3+a_4$. If the former pair was joined first, we find $a_1\leq a_3$, $a_2\leq a_3$, $a_1\leq a_4$, and $a_2 \leq a_4$. These inequalities imply those of the first case, so we can conclude that $$a_1 \leq a_3+a_4 \text{ and } a_2\leq a_3+a_4.$$

Can you go on from here?

$\endgroup$
4
  • $\begingroup$ I still don't see why my assumption is wrong (Including the root of the right tree). The left node must not be greater than the right one. $\endgroup$ – AnnieOK Mar 10 '14 at 12:27
  • $\begingroup$ @AnnieOK In the root of the right tree, the left child has weight $1+1+3=5$, while the right child has weight $1+2=3$. $\endgroup$ – FrankW Mar 10 '14 at 12:35
  • $\begingroup$ How can you mention numbers? They are only variables, you cannot know for sure. $\endgroup$ – AnnieOK Mar 10 '14 at 13:49
  • $\begingroup$ @AnnieOK I have taken the numbers from the example you give in the question. $\endgroup$ – FrankW Mar 10 '14 at 14:23

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.