CODEWITHSUNDEEP
algorithmencodinghuffman-codehuffman-tree
twynb
twynb

Reputation: 41

Does the BRCI algorithm work for *all* Huffman Trees?

I'm trying to create a height-limited Huffman Tree. One algorithm proposed for this is the BRCI Algorithm, which promises a comparatively fast and simple to implement solution.

This means that the algorithm claims to take any huffman tree T and limit its height to a level L (with T having up to L^2 nodes). My problem here is that because huffman trees can theoretically have a shape like (1 (2 (3 (4)))), it's possible that after step 1, only L-1 nodes remain in T1, with T2 containing 2^L - (L-1) leaves. If 2^(L-1) > (L - 1), that would however mean that 2^L - (L - 1) > 2^(L - 1), meaning that to build a T2 with all 2^L - (L - 1) leaves, it must have a height of L. That in turn means you can't add T2 into T1 without resulting in a tree at least L+1 high.

Am I getting something wrong here or is the BRCI algorithm broken for one-sided huffman trees?

As an example, I took a T (1 ((2 3) (4 (5 (6 7))))), which in theory you should be able to limit to a height of 3.

Going through the steps of the BRCI algorithm results in a T1 (1 ([empty] [empty])) and a T2 that looks something like ((2 3) ((4 5) (6 7)). T2 has a height of 3 already (because it contains 6 elements, which you cannot portray in a tree with a height of 2), so the level calculated in step 3 is L - h(T2) - 1 = 3 - 3 - 1 = -1. Even ignoring the level, you cannot append T2 anywhere in T1 (or even create a new root node with T1 and T2 as children) without being at least at a height of 4.

Upvotes: 0

Views: 37

Answers (1)

twynb
twynb

Reputation: 41

Self-Answer: This is in fact an edge case where running the BRCI algorithm once will not result in the desired height.

The solution to making it work anyway is fairly simple: If the level calculated in step 3 is negative, set it to 0 and continue the algorithm. Then run the algorithm again.

As the tree gets flattened with each repetition of the algorithm, you eventually arrive at a tree of the desired height.

Upvotes: 0

Related Questions