Sign in to follow this  
DevFred

degenerate dynamic huffman tree

Recommended Posts

What is the maximum number of transitions from a leaf to the root in a dynamic huffman tree in the worst case when I call update at most 65,280 times? This text leads me to believe it is 25 since fib(26) = 75,025 is the lowest fibonacci number above 65,280. It would be great if someone could confirm this because 25 fits nice into a single integer and it would make my BitStack implementation a lot simpler than it currently is.

Share this post


Link to post
Share on other sites
I'm not sure of the terminology you are using.. but I am well versed in huffman encoders.

Your worst-case tree depth is indeed 25.

You might want to check out http://coding.derkeiler.com/Archive/General/comp.theory/2004-09/0431.html

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this