*3. Постройте дерево Хаффмана для одной из следующих фраз: 1) МАМА МЫЛА РАМУ 2) ШЛА САША ПО ШОССЕ 3) ТКЁТ ТКАЧ ТКАНИ 4) КАРЛ У КЛАРЫ УКРАЛ КОРАЛЛЫ

Выберем фразу «МАМА МЫЛА РАМУ». Пробел не учитываем при построении дерева.

1. Подсчитаем частоты букв: А — 4, М — 3, Р — 1, Ы — 1, Л — 1, У — 1.
2. Соединим две наименее частые буквы Р и Ы: получим узел с весом 2.
3. Соединим узел РЫ (2) и Л (1): получим узел с весом 3.
4. Соединим этот узел и У (1): получим узел с весом 4.
5. Соединим М (3) и узел весом 4: получим узел с весом 7.
6. Наконец, соединим А (4) и узел весом 7: корень дерева имеет вес 11.

Приписывая левым рёбрам 0, а правым 1, получаем один из возможных вариантов кодов:

А — 0; М — 10; У — 110; Л — 1110; Р — 11110; Ы — 11111.

Дерево Хаффмана может иметь и другие варианты при равных весах узлов; они также корректны, если коды остаются префиксными.