Двоичное кодирование и бинарные деревья

Двоичное кодирование удобно представлять в виде бинарного кодового дерева. Если условиться сопоставлять любой левой ветви бинарного дерева нуль, а любой правой – единицу, то каждой вершине дерева будет однозначно соответствовать некоторый набор двоичных знаков, показывающий, в какой последовательности нужно сворачивать налево и направо, добираясь до этой вершины из корня дерева. Любой из таких наборов может быть выбран в качестве кодового слова. Например, рассмотренному выше коду соответствует дерево, приведенное на рис. 1.4.

Рис.1.4

Пример кодового дерева примитивного префиксного кода

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

Процесс двоичного кодирования можно интерпретировать следующим образом. На каждом шаге движения по кодовому дереву, начиная от корня, происходит выбор одного из двух поддеревьев: правого и левого. Это соответствует разбиению множества знаков алфавита на два подмножества – правое и левое – с присвоением им очередных двоичных знаков (единицы и нуля). Так, в рассмотренном примере множество {0,…,9} было разбито на два подмножества {0,1} и {2,3,…,9}. При дальнейшем движении вправо множество {2,3,…,9} в свою очередь было разбито на два подмножества {2,3,4} и {5,6,…,9}, а при движении влево множество {0,1} было разбито на два подмножества {0} и {1} и т.д. до тех пор, пока во всех подмножествах не осталось по одному элементу.

Таким образом, двоичные коды, соответствующие вершинам кодового дерева, характеризуют «историю» последовательного разбиения исходного множества знаков на правые и левые подмножества.