Представление префиксных кодов в форме бинарных деревьев

Дерево T, в котором каждый узел, не являющийся листовым, имеет не более двух дочерних узлов, называется бинарным деревом. Допустим, количество листовых узлов равно размеру алфавита S, а каждый лист помечен одной из букв S.

Такое бинарное дерево T естественно описывает префиксный код. Для каждой буквы X S отслеживается путь от корня до листа с меткой х; каждый раз, когда путь переходит от узла к его левому дочернему узлу, в результирующую цепочку битов записывается 0, а при переходе к правому узлу — 1. Полученная цепочка битов рассматривается как кодировка х.

Отметим следующий факт:

(4.27) Кодировка алфавита S, построенная на основе T, представляет собой префиксный код.

Доказательство. Чтобы кодировка х была префиксом кодировки у, путь от корня к узлу X должен быть префиксом пути от корня к узлу у. Но для этого узел х должен лежать на пути от корня к у, а это невозможно, если узел х является ли- стовым. ■

Отношения между бинарными деревьями и префиксными кодами также ра- ботают и в обратном направлении: для префиксного кода γ можно рекурсивно построить бинарное дерево. Начните с корня; все буквы х S, кодировка которых начинается с 0, будут представлены листовыми узлами в левом поддереве, а все
буквы у

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Представление префиксных кодов в форме бинарных деревьев:

  1. Далее следует объяснение наиболее распространенных речевых кодов.
  2. Далее следует объяснение наиболее распространенных речевых кодов.
  3. Часть третья Использование кодов для определения типа характера
  4. Часть третья Использование кодов для определения типа характера
  5. Примеры парных кодов:
  6. 3.11.10. Облако и Дерево
  7. О друзьях-деревьях
  8. Построение дерева целей.
  9. Дерево упало
  10. Над деревьями
  11. И НА КАМНЯХ РАСТУТ ДЕРЕВЬЯ
  12. ИДЕЯ 41 ДЕРЕВО, СПОСОБНОЕ ВЫДЕРЖАТЬ УРАГАН
  13. 1. Общие положения о форме сделок
  14. Глава 12 О ТОМ, КАК ТВОРИТ ДЕРЕВО
  15. Призыв к пробуждению от Красных Деревьев
  16. Предложение №2 Полазай по своему дереву
  17. Статья 207. Требования к письменной форме сделки