Weight Balanced Tree in Data Structure

Weight Balanced Tree:

Suppose every external node has some weight W, then the weighted path length for the external node will be –
P= W1P1+ W2P2+…..+ WnPn
Where W denotes the weight and P denotes the path length of an external node.

Now, we can see that three different trees have different path lengths. So, the problem arises of obtaining a unique tree that has a minimum weighted path length. This extended binary tree can be obtained by the Huffman Algorithm.

Huffman Algorithm:

1. Let us take there are n weights W1, W2,…., Wn
2. Take two minimum weights and create a sub-tree. Suppose W1 and W2 are first two minimum weights then sub-tree will be –
3. Now, the remaining weights will be W1+ W2, W3, W4,….., Wn
4. Create all sub-trees at the last weight.