Десятичная кодировка

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

Существует множество способов кодировки деревьев. Рассмотрим одну из простейших кодировок помеченных деревьев с выделенным корнем – десятичную.

Кодируя дерево, придерживаемся следующих правил.

1. Кодировка начинается с корня и заканчивается в корне.

2. Каждый шаг на одну дугу от корня кодируется единицей.

3. В узле выбираем направление на вершину с меньшим номером.

4. Достигнув листа, идем назад, кодируя каждый шаг нулем.

5. При движении назад в узле всегда выбираем направление на непройденную вершину с меньшим номером.

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

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

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

. (14.1)

Рис. 14.2

 

Если корень поместить в любой из висячих вершин, то код такого дерева будет выражаться большим числом. Более того, существует зависимость . Аналогично рассматриваются и цепи (рис. 14.3). Цепи обозначаются как .

Рис. 14.3

 

В звездах только два варианта расположения корня с различными десятичными кодировками. В цепи же число вариантов кодировок в зависимости от положения корня растет с увеличением n. Рассмотрим самый простой вариант, расположив корень в концевой вершине (листе). Для получим двоичную кодировку 10 и десятичную 2, для – 1100 и 12, для – 111000 и 56, для – 11110000 и 240. Общая формула для десятичной кодировки цепи с корнем в концевой вершине имеет вид

. (14.2)

Пример 14.2. Записать десятичный код дерева, изображенного на рис. 14.4, с корнем в вершине 3.

Рис. 14.4

 

Решение. На основании правила кодировки, двигаясь по дереву, проставим в код единицы и нули. При движении из корня 3 к вершине 7 проходим четыре ребра. В код записываем четыре единицы: 1111. Возвращаясь от вершины 7 к вершине 2 (до ближайшей развилки), проходим три ребра. Записываем в код три нуля: 000. От вершины 2 к 5 и далее к 8 (меньший номер): 11; от 8 назад к 5 и от 5 к 9: 01; от 9 к корню 3: 000.

И, наконец, от 3 к 6 и обратно: 10. В итоге, собирая все вместе, получим двоичный код дерева:

1 111 000 110 100 010.

Разбивая число на тройки, переводим полученное двоичное представление в восьмеричное. Получаем . Затем переводим это число в десятичное: .