1
$\begingroup$

How to prove that for a full (each node that's not a leaf has 2 nodes) binary tree $T$ of $n$ leaves there's a series of frequencies $f_1,f_2,...,f_n$ such that if we use Huffman algorithm on the series we'll get $T$?

First in order to get frequencies from $T$ we can assign the probability of $\frac{1}{2^d}$ to each node where $d$ is the depth of a given node. The root node will have the probability of $1$ which means $100$%. After one traversal of $T$ we could fill the array with the frequencies of the leaves of $T$ (only leaves correspond to the the actual values to be encoded).

I'm not sure how to prove that if we apply Huffman algorithm to the frequencies one of the trees will happen to be $T$. It seems like if we build a tree from the frequencies each time such that the new tree is different (if possible) from the previous tree we'll eventually build $T$. Also we know that Huffman tree is always a full tree.

The Huffman algorithm is as follows (as described in Algorithm Design by Jon Kleinberg, Eva Tardos):

Huffman(S) {
  if |S|=2 {
    return tree with root and 2 leaves
  } else {
    let y and z be lowest-frequency letters in S
    S’ = S
    remove y and z from S’
    insert new letter ω in S’ with f_ω=f_y+f_z
    T’ = Huffman(S’) 
    T=add two children y and z to leaf ω from T’ 
    return T
  } 
}
$\endgroup$
  • $\begingroup$ What do you mean by "one of the Huffman trees"? What is a Huffman tree of a series? The details matter here! $\endgroup$ – Yuval Filmus Nov 20 '17 at 12:32
  • $\begingroup$ @YuvalFilmus What I meant is that for any full binary tree there's a series of frequencies such that using Huffman algorithm on the frequencies will produce the original tree. Let me know if this makes sense. $\endgroup$ – Yos Nov 20 '17 at 12:35
  • $\begingroup$ There are many possible variants of Huffman's algorithm, so we need to know which variant you are using. Also, the formulation of the question suggests that you're using a nondeterministic variant of Huffman's algorithm which could produce many different trees for the same distribution. $\endgroup$ – Yuval Filmus Nov 20 '17 at 12:36
  • $\begingroup$ The Huffman algorithm I was referring to is the one described on page 172 (chpater 4) of the book Algorithm Design by Jon Kleinberg, Eva Tardos. $\endgroup$ – Yos Nov 20 '17 at 12:38
  • $\begingroup$ Some of us don't have Kleinberg and Tardos's book. If you want those of us to help you with this exercise, you will have to describe this variant of the algorithm in your post. $\endgroup$ – Yuval Filmus Nov 20 '17 at 12:40
1
$\begingroup$

The proof is by induction. The case $n = 1$ is clear. For $n > 1$, choose two leaves at maximal depths, and merge them. Huffman's algorithm could have chosen these two leaves at the first step and merged them. Now apply the inductive hypothesis to complete the proof.

Note that Huffman's algorithm, as described in your textbook, is non-deterministic in the sense that at any step there could be many valid choices. Any actual implementation of the algorithm will use a tie-breaking rule to arbitrarily choose which two leaves of minimal probability to merge at any given step.

$\endgroup$
  • $\begingroup$ So essentially I can claim that Huffman algorithm "could have chosen" the two leaves because it's one of the possible options? Do we know how many options there are? $\endgroup$ – Yos Nov 20 '17 at 14:23
  • 1
    $\begingroup$ If there are $m>1$ elements of minimum probability, then there are $m(m-1)$ options (or $\binom{m}{2}$ if you don't care about the order). If there is one element of minimum and $m$ of second minimum probability, then there are $2m$ options (or $m$ if you don't care about the order). $\endgroup$ – Yuval Filmus Nov 20 '17 at 14:24
  • $\begingroup$ if we're interested in order why is it not Perm(m,2)? $\endgroup$ – Yos Nov 20 '17 at 14:29
  • $\begingroup$ I have no idea what Perm(m,2) is. $\endgroup$ – Yuval Filmus Nov 20 '17 at 14:30
  • 1
    $\begingroup$ You can check that $P(m,2) = m(m-1)$. $\endgroup$ – Yuval Filmus Nov 20 '17 at 14:35

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.