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= W₁P₁+ W₂P₂+…..+ W_nP_n
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 W₁, W₂,…., W_n
2. Take two minimum weights and create a sub-tree. Suppose W₁ and W₂ are first two minimum weights then sub-tree will be –
3. Now, the remaining weights will be W₁+ W₂, W₃, W₄,….., W_n
4. Create all sub-trees at the last weight.