Lemma: Let $a$ and $b$ be two characters that are sibling leaves of maximum depth $T $, and $x$ and $y$ are the two charachterts of the minimum frequency $f(\cdot)$. WLOG, assume that $f[x] <f[y]<f[a]<f[b]$. Then we must have $d_T(x) = d_T(y) =d_T(a) =d_T(b)$.

Definitions: $d_T(x)$ is the depth of a character in the tree. We can define the cost as the number of bits needed to encode tree $B(T)=\Sigma_{\forall c \in C}f(c)\times d_T(c)$.

We can exchange characters of $x$ and $a$. This exchange yeilds another tree $T'$, so the difference of cost $B(T) - B(T')$ yeilds that $(f[a] - f[x])(d_T(a)-d_T(x)) \ge 0$. Then we can show that $d_T(a)=d_T(x)$$\blacksquare$.

Problem: Why we assume in the beginning that $d_T(x) = d_T(y) =d_T(a) =d_T(b)$ please given that $x$ has the least frequency and thus has the maximum depth $d_T(x)$, so I am not sure why it was assumed depths are equal and then we also indeed proved they are?

enter image description here

  • 1
    $\begingroup$ That's not assumed, it's stated by the lemma. $\endgroup$
    – Pål GD
    Oct 12 at 18:56

Your Answer

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

Browse other questions tagged or ask your own question.