Huffman tree definition and example

A Huffman tree is a binary tree built from a set of symbols with weights (frequencies), such that the weighted external path length Σ (weight × depth of leaf) is minimum. It is used to produce an optimal prefix code for lossless data compression: frequent symbols get short codes and rare symbols get long codes.

Properties

1. It is a strictly (full) binary tree: every internal node has exactly two children. For n symbols there are n leaves and n − 1 internal nodes.
2. Each symbol is a leaf. An internal node holds the sum of the weights of its two children; the root weight is the total frequency.
3. Symbols of higher frequency are at a smaller depth (shorter code); the two least frequent symbols are siblings at the deepest level.
4. Labelling left edges 0 and right edges 1 gives a prefix code: no code is the prefix of another, so decoding is unambiguous.
5. The tree is not unique when weights tie, but all Huffman trees give the same minimum average code length.
6. Built greedily in O(n log n) with a min-heap.

Example

Symbols with frequencies: A = 5, B = 9, C = 12, D = 13, E = 16, F = 45.

            100
           /    \
        F:45     55
                /    \
              25      30
             /  \    /   \
          C:12 D:13 14    E:16
                   /  \
                A:5   B:9

Codes (left = 0, right = 1): F = 0, C = 100, D = 101, A = 1100, B = 1101, E = 111.

Average length = (45×1 + 12×3 + 13×3 + 5×4 + 9×4 + 16×3)/100 = 224/100 = 2.24 bits per symbol, against 3 bits for fixed-length codes.