Re: Getting Huffman tree height without performing Huffman algorithm? (Was: Generatin

"David A. Scott" <daVvid_a_scott@email.com> wrote in message news:Xns95795079389D1H110W296L
C45WIN3030R@130.133.1.4...
> "Alex Vinokur" <alexvn@big-foot.com> wrote in
> news:2sdoocF1k3nr0U1@uni-berlin.de:
[snip] 
>
>  But what about this its a strictly worse case tree and
> it has less weight than what you called the strictly
> worse case than the Fibonacci you clained as worst case.
>
>                       17
>                       /\
>                      /  \
>                    10    7
>                    /\
>                   /  \
>                  6    4
>                 /\
>                /  \
>               3    3
>              /\
>             /  \
>            2    1
>           /\
>          /  \
>         1    1
>
[snip]

You are correct. Thanks.

This is the Lucas sequence.
The cost of the Huffman tree for that sequence is S(n) = F(n + 3) + F(n + 1)
 - (n + 3).

My mistake has been caused by attempt to simplify definitions from my postin
g titled
"Fibonacci numbers, Lucas numbers and Huffman codes" at
http://groups.google.com/groups?sel...0uni-berlin.de.

Sorry.

--
Alex Vinokur
email: alex DOT vinokur AT gmail DOT com
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn