| Alex Vinokur 2004-10-05, 3:55 pm |
|
"David A. Scott" <daVvid_a_scott@email.com> wrote in message news:Xns95795079389D1H110W296LC45WIN3030
R@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 posting 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
|