Представление деревьев с помощью массивов

При этом представлении каждый элемент массива A[i] является указателем или курсором на родителя узла i. Корень дерева имеет нулевой указатель.

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

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

Для реализации оператора LEBEL можно использовать другой массив, в котором хранить метку узла i.

О

1	2	3	4	5	6	7	8	9	10
0	1	1	2	2	5	5	5	3	3

днако, используя такое представление, трудно для заданного узла найти его сыновей или определить его высоту. Кроме того, в этом случае невозможно определить порядок сыновей узла если не поддерживать специальный порядок в массиве, например, левые сыновья должны иметь меньший индекс в массиве, чем правые.

Представление деревьев с использованием списков сыновей

В этом представлении для каждого узла дерева формируется список сыновей. Эти списки можно представить любым способом. Вот как будет выглядеть наше дерево при таком представлении

П редставление левых сыновей и правых братьев (левый ребенок – правый сосед)

В каждом узле хранится:

1. указатель на родителя,

2. указатель на самого левого сына узла,

3. указатель на ближайшего справа (следующего по старшинству) брата узла.

Узел x тогда и только тогда не имеет сыновей, когда указатель

left_child(x) = NULL.

Если узел x – самый правый сын родителя, то right_sibling(x) = NULL.

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

В компьютерных науках часто используются деревья, в которых все вершины имеют ограниченное сверху количество потомков.

Например, если это число 2, то любая вершина содержит не более двух (2,1 или 0) потомков, такие деревья называются бинарными или двоичными.

Реализация с помощью указателей на «левого ребенка» и «правого ребенка».

Коды Хаффмана

Примером применения двоичных деревьев в качестве структур данных могут служить коды Хаффмана.

Они широко используются при сжатии информации (выигрыш может составить от 20% до 90% в зависимости от типа файла). Алгоритм Хаффмана находит оптимальные коды символов исходя из частоты использования этих символов в сжимаемом тексте с помощью жадного выбора.

Предположим, в файле длиной 100 000 встречаются только латинские буквы от а до f и известны их частоты.

	A	B	C	D	E	F
Количество в тысячах	45	13	12	16	9	5
Равномерный код	000	001	010	011	100	101
Неравномерный код	0	101	100	111	1101	1100

Мы хотим построить двоичный код, в котором каждый символ представляется в виде конечной последовательности битов, называемой кодовым словом.

При использовании равномерного кода, в котором все кодовые слова имеют одинаковую длину, на каждый символ надо потратить как минимум 3 бита.

На весь файл уйдет 300 000 бит.

Но если часто встречающиеся символы закодировать короткими последова-тельностями битов, а редко встречающиеся – длинными, то можно построить более экономный неравномерный код.

В приведенном примере неравномерного кода на весь файл уйдет 224 000 бит, что дает около 25% экономии.

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

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

При кодировании каждый символ заменяется на свой код. Например, строка ABC запишется как 0101100. Для префиксного кода декодирование однозначно и выполняется слева направо.

Для эффективной реализации декодирования надо хранить информацию о коде в удобной форме.

Одна из возможностей – представить код в виде двоичного дерева, листья которого соответствуют кодируемым символам. При этом путь от вершины дерева до кодируемого символа определяет кодирующую последовательность битов: поворот налево дает 0, а поворот направо – 1.

Оптимальному коду (для данного файла) всегда соответствует двоичное дерево, в котором всякая вершина, не являющаяся листом, имеет двоих детей. Такое свойство позволяет легко доказать, что дерево оптимального префиксного кода для файла, в котором используются все символы из некоторого множества С и только они, содержит только |С| листьев и ровно |C| –1 узлов, не являющихся листьями.

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

Алгоритм строит дерево Т, соответствующее оптимальному коду, снизу вверх, начиная с множества из |С| листьев и делая |С| –1 “слияний”. Предполагаем, что для каждого символа из С задана его частота f[c]. Для нахождения двух объектов, подлежащих слиянию, может быть использована очередь с приоритетами Q, использующая частоты f в качестве рангов – сливаются два объекта с наименьшими частотами. В результате слияния получается новый объект, частота которого считается равной сумме частот двух сливаемых объектов.

Пример применения алгоритма Хаффмана.

F:5

E:9

C:12

B:13

D:16

A:45