Заданы частоты для всех букв, встречающихся в сообщении:
А - 70, Т - 80, Н - 90,
Е - 90, О - 150
Определите длину самого короткого кодового слова в коде Хаффмана.

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

1. Создание узлов для символов: Начнем с создания узлов для каждого символа, указав частоту для каждого из них:

• А: 70
• Т: 80
• Н: 90
• Е: 90
• О: 150

2. Построение дерева Хаффмана: Следующий шаг — это построение дерева Хаффмана. В начале выбираются два узла с наименьшими частотами, объединяются в один новый узел с частотой, равной сумме частот этих двух узлов. Процесс повторяется до тех пор, пока не останется один узел — корень дерева. Этот узел будет представлять собой полное дерево, где каждое поддерево описывает код для определенного символа.

3. Шаги построения дерева:

   • Возьмем два узла с минимальными частотами: А (70) и Т (80). Объединим их в один узел с частотой 150.
   • Далее сравним оставшиеся узлы: Н (90), Е (90), О (150), и новый узел с частотой 150. Два узла с минимальными частотами — Н (90) и Е (90) — объединяются в новый узел с частотой 180.
   • Теперь сравним: О (150), новый узел (150), и новый узел (180). Выберем два минимальных: О (150) и узел (150), объединяем их в новый узел с частотой 300.
   • Последний шаг: сравним оставшиеся узлы: новый узел (180) и новый узел (300). Объединяем их, получаем корневой узел с частотой 480.

4. Назначение кодов: Теперь, когда дерево построено, можно присвоить коды символам. Для этого двигаемся по дереву: при переходе влево добавляем "0", при переходе вправо — "1". Поскольку код Хаффмана оптимален, символы с более высокой частотой будут иметь более короткие кодовые слова.

5. Анализ длины самого короткого кодового слова: Символ "О" с самой высокой частотой (150) будет располагаться ближе всего к корню, так как его кодовое слово должно быть максимально коротким. В нашем случае "О" будет на втором уровне дерева, следовательно, длина его кодового слова — 2 бита.

Таким образом, длина самого короткого кодового слова в коде Хаффмана равна 2.