Given the character frequencies B : 32% C : 28% D : 16% E : 6% F : 18% Using Huffman encoding, what is the code for character D? (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: "100". Dựng cây Huffman bằng cách ghép hai tần số nhỏ nhất, luôn đặt nút tần số lớn hơn sang trái, nhánh trái mang bit 0 và nhánh phải mang bit 1. Hai nhỏ nhất là E 6% và D 16%, ghép thành nút 22% với D bên trái, E bên phải. Hai nhỏ nhất kế tiếp là F 18% và nút 22%, ghép thành nút 40% với nút 22% bên trái vì 22 lớn hơn 18, F bên phải. Còn lại B 32% và C 28% ghép thành nút 60% với B bên trái. Cuối cùng ghép 60% bên trái với 40% bên phải. Lần đường từ gốc tới D: sang phải tới nút 40% được 1, sang trái tới nút 22% được 0, sang trái tới D được 0, vậy D = 100. "101" là mã của E, lá còn lại dưới nút 22%. "01" là mã của C và chỉ dài hai bit; D có tần số 16% thấp hơn C 28% nên không thể được mã ngắn bằng C. "001" đòi D treo dưới nút mang mã 00, nhưng 00 đã là lá B.