Given the character frequencies A : 36% B : 25% C : 19% D : 15% E : 5% Using Huffman encoding, what is the code for character E? (Suppose that when constructing a sub tree from 2 nodes we always place node with higher frequency on the left; and the left branch of a node gets value 0, the right one gets value 1)

Đáp án đúng: "101". Huffman luôn gộp hai tần số nhỏ nhất: D 15 phần trăm với E 5 phần trăm thành nút 20, nút nặng hơn đứng bên trái nên D nhận nhánh 0 và E nhận nhánh 1. Hai nhỏ nhất kế tiếp là C 19 và nút 20, gộp thành 39 với nút 20 bên trái, C bên phải. Rồi B 25 với A 36 thành nút 61, A bên trái, B bên phải. Cuối cùng 61 và 39 thành gốc 100, nhánh 0 về phía 61 vì nó nặng hơn, nhánh 1 về phía 39. Đường đi từ gốc tới E vì vậy là 1 rồi 0 rồi 1. "001" chỉ xuất hiện nếu nhánh chứa D và E bị treo bên trái của gốc, trái với quy ước nhánh nặng hơn nằm bên trái. "100" đúng là mã của D, tức nhầm nhánh ở bước tách D với E. "111" không ứng với đường đi nào: sau hai nhánh 1 ta đã tới lá C nên không còn nhánh nào để đi bit thứ ba, mã của C chỉ dài hai bit.