1. Деревья. Основные определения. Логическое представление и изображение деревьев. Бинарные деревья. Машинное представление деревьев в памяти эвм. Алгоритмы прохождения деревьев.

Дерево - это граф, который характеризуется следующими свойствами:

1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент - и который называется КОРНЕМ (рис. 6.8, 6.9 - A,G,M - корни).

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

3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Название "дерево" проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами)(рис. 6.8, 6.9 - b,k,l,h - листья). Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной).

Для ориентированного графа число ребер, исходящих из некоторой начальной вершины V, называется ПОЛУСТЕПЕНЬЮ ИСХОДА этой вершины. Число ребер, для которых вершина V является конечной, называется ПОЛУСТЕПЕНЬЮ ЗАХОДА вершины V, а сумма полустепеней исхода и захода вершины V называется ПОЛНОЙ СТЕПЕНЬЮ этой вершины.

рис. 6.8. Дерево

рис. 6.9. Лес

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

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

Вершина ориентированного дерева, полустепень исхода которой равна нулю, называется КОНЦЕВОЙ (ВИСЯЧЕЙ) вершиной или ЛИСТОМ; все остальные вершины дерева называют вершинами ветвления. Длина пути от корня до некоторой вершины называется УРОВНЕМ (НОМЕРОМ ЯРУСА) этой вершины. Уровень корня ориентированного дерева равен нулю, а уровень любой другой вершины равен расстоянию (т.е. модулю разности номеров уровней вершин) между этой вершиной и корнем. Ориентированное дерево является ациклическим графом, все пути в нем элементарны.

Во многих приложениях относительный порядок следования вершин на каждом отдельном ярусе имеет определенное значение. При представлении дерева в ЭВМ такой порядок вводится автоматически, даже если он сам по себе произволен. Порядок следования вершин на некотором ярусе можно легко ввести, помечая одну вершину как первую, другую - как вторую и т.д. Вместо упорядочивания вершин можно задавать порядок на ребрах. Если в ориентированном дереве на каждом ярусе задан порядок следования вершин, то такое дерево называется УПОРЯДОЧЕННЫМ ДЕРЕВОМ.

Введем еще некоторые понятия, связанные с деревьями. На рис.6.10 показано дерево:

Узел X называется ПРЕДКОМ (или ОТЦОМ), а узлы Y и Z называются НАСЛЕДНИКАМИ (или СЫНОВЬЯМИ) их соответственно между собой называют БРАТЬЯМИ. Причем левый сын является старшим сыном, а правый - младшим. Число поддеревьев данной вершины называется СТЕПЕНЬЮ этой вершины. ( В данном примере X имеет 2 поддерева, следовательно СТЕПЕНЬ вершины X равна 2).

рис.6.10. Дерево

Если из дерева убрать корень и ребра, соединяющие корень с вершинами первого яруса, то получится некоторое множество несвязанных деревьев. Множество несвязанных деревьев называется ЛЕСОМ (рис. 6.9).

Логическое представление и изображение деревьев.

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

МЕТОД ВЛОЖЕННЫХ СКОБОК

(V0(V1(V2(V5)(V6))(V3)(V4))(V7(V8)(V9(V10))))

Рис.6.11. Представление дерева : а)- исходное дерево, б)- оглавление книг, в)- граф, г)- диаграмма Венна

Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребительному термину "дерево".

Бинарные деревья.

Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой вершины в точности равна либо m, либо нулю, то такое дерево называется ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ.

При m=2 такие деревья называются соответственно БИНАРНЫМИ, или ПОЛНЫМИ БИНАРНЫМИ.

На рисунке 6.12(a) изображено бинарное дерево, 6.12(b)- полное бинарное дерево, а на 6.12(c) показаны все четыре возможных расположения сыновей некоторой вершины бинарного дерева.

Рис. 6.13. Изображения бинарных деревьев

Машинное представление деревьев в памяти ЭВМ.

Деревья можно представлять с помощью связных списков и массивов (или последовательных списков).

Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от отца к сыновьям. В бинарном дереве имеется два указателя, поэтому удобно узел представить в виде структуры:

LPTR DATA RPTR

где LPTR - указатель на левое поддерево, RPTR - указатель на правое поддерево, DATA - содержит информацию, связанную с вершиной.

Рассмотрим машинное представление бинарного дерева

Логическое представление дерева

Машинное связное представление дерева

Алгоритмы на деревьях

Сортировка с прохождением бинарного дерева

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

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

Исходный массив:

14,15,4,9,7,18,3,5,16,4,20,17,9,14,5

3

Рис. 6.15. Сортировка по возрастанию с прохождением бинарного дерева.

Сортировка методом турнира с выбыванием

Приведем другой алгоритм сортировки, основанный на использовании бинарных деревьев. Данный метод получил название турнира с выбыванием. Пусть имеется исходный массив 10, 20, 3, 1, 5, 0, 4, 8. Сортировка начинается с создания листьев дерева. В качестве листьев бинарного дерева создаются узлы, в которых записаны значения элементов исходного массива. Дерево строится от листьев к корню. Для двух соседних узлов строится общий предок, до тех пор, пока не будет создан корень. В узел-предок заносится значение, являющееся наименьшим из значений в узлах-потомках.

В результате построения такого дерева наименьший элемент попадает сразу в корень. Далее начинается извлечение элементов из дерева. Извлекается значение из корня. Данное значение является первым элементом в результирующем массиве. Извлеченное значение помещается в отсортированный массив и заменяется в дереве на специальный символ.

После этого происходит повторное занесение значений в родительские элементы от листьев к корню. При сравнениях специальный символ считается большим по отношению к любому другому значению. После повторного заполнения из корня извлекается очередной элемент и итерация повторяется. Извлечения элементов продолжаются до тех пор, пока в дереве не останутся одни специальные символы. В результате получим отсортированный массив 0, 1, 3, 4, 5, 8, 10, 20. Описанный алгоритм иллюстрируют рис. 6.16-6.19.

0

1

Рис. 6.16. Построение дерева сортировки.

*

Рис. 6.17. Замена извлекаемого элемента на специальный символ

Рис. 6.18. Повторное заполнение дерева сортировки.

0,1,3,4,5,8,10,20

20

Рис. 6.19. Извлечения элементов из дерева сортировки.

Применение бинарных деревьев для сжатия информации

Бинарные деревья применяются в задачах сжатия информации. Рассмотрим пример. Имеется текстовая строка S, состоящая из 10 символов S = ABCCCDDDDD. При кодировании одного символа одним байтом для строки потребуется 10 байт. Попробуем сократить требуемую память. Рассмотрим, какие символы действительно требуется кодировать. В данной строке используются всего 4 символа. Поэтому можно использовать укороченный код.

A 00

B 01

C 10

D 11

b = 00011010101111111111 (20 бит)

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

Построение кодовой таблицы происходит с использованием бинарного дерева (рис. 6.20). В корне дерева помещаются все символы и их суммарная частота повторения. Далее выбирается наиболее часто используемый символ и помещается со своей частотой повторения в левое поддерево. В правое поддерево помещаются оставшиеся символы с их суммарной частотой. Затем описанная операция проводится для всех вершин дерева, которые содержат более одного символа.

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

ABCD, 10

D, 5

Рис. 6.20. Построение кодовой таблицы.

Для строки S будет получен следующий код b=11011110101000000. Длина кода составляет 17 бит, что меньше по сравнению с укороченным кодом. Алгоритм распаковки можно сформулировать следующим образом:

1. i:=0, j:=0;

2. если i > n, то стоп строка распакована, иначе i:=i+1;

3. node:= root;

4. если b(i) = 0, то node:=left(node), иначе node:=right(node)

5. если left(node) = 0 и right(node) = 0, то j:=j+1, s(j):= str(node),

перейти к шагу 2, иначе i:=i+1, перейти к шагу 4

В алгоритме корень дерева обозначен как root, а left(node) и right(node) обозначают левый и правый потомки узла node.

На практике такие способы упаковки используются не только для текстов, но и для произвольных двоичных данных. Любой файл можно рассматривать как последовательность байт. Тогда дерево кодирования можно построить не для символов, а для значений байт, встречающихся в кодируемом файле (рис. 6.21). Поскольку байт может принимать 256 значений, то соответствующее дерево будет иметь не более 256 листьев.

D

j

Рис. 6.21. Процесс распаковки кода.

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

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

С помощью деревьев можно представлять произвольные арифметические выражения (рис. 6.22-6.23). Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу - операция. В общем случае дерево при этом может оказаться не бинарным. Однако если число операндов любой операции будет меньше или равно двум, то дерево будет бинарным. Причем если все операции будут иметь два операнда, то дерево окажется строго бинарным.

*

-x

Рис. 6.22. Представление арифметического выражения произвольного вида в виде дерева.

f(a+b,sin c)

a

Рис. 6.23. Представление арифметического выражения в виде бинарного дерева.

Бинарные деревья могут быть использованы не только для представления выражений, но и для их вычисления (рис. 6.24). В листьях записываются значения операндов. Затем от листьев к корню производится выполнение операций. В процессе выполнения в узел операции записывается результат ее выполнения. В конце вычислений в корень будет записано значение, которое и будет являться результатом вычисления выражения.

(1+10)*5

*

Рис. 6.24. Вычисление арифметического выражения с помощью бинарного дерева.

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

&

((aVb)&(cVd))&(e&fVa&b)

&

d

Рис. 6.25. Представление логического выражения в виде бинарного дерева.

5.Сравнительный анализ алгоритмов поиска: линейный, двоичный

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

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

Линейный поиск. Единственно возможным методом поиска элемента по значению ключа, находящегося в неупорядоченном наборе данных, является последовательный (линейный) просмотр каждого элемента, который продолжается до тех пор, пока не будет найден искомый элемент. Если просмотрен весь набор, но элемент не найден, искомый ключ отсутствует. Для последовательного поиска в среднем требуется (n+1)/2 сравнений и порядок алгоритма линейный O(n).

Программная иллюстрация линейного поиска в неупорядоченном массиве приведена ниже, где aList – исходный массив, aItem – искомый ключ; функция возвращает индекс найденного элемента или -1, если элемент отсутствует.

{ Линейный поиск в неотсортированном массивом }

function LineNonSortedSearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

var i: Integer;

begin

Result:=-1;

for i:=0 to aList.Count-1 do

if aCompare(aList.List[i],aItem) = 0 then

begin

Result:=i;

Break;

end;

end;

Последовательный поиск для отсортированного массива ничем не отличается от приведенного и имеет линейный порядок алгоритма O(n).

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

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

Процесс продолжается до тех пор, пока не найден требуемый ключ или не станет пустым интервал, в котором осуществляется поиск. Чтобы найти элемент, в худшем случае требуется log₂(N) сравнений, что значительно лучше, чем при последовательном поиске. Программная иллюстрация бинарного поиска в упорядоченном массиве приведена ниже.

{ Двоичный поиск }

function BinarySearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

var L, R, M, CompareResult: Integer;

begin

{ Значения индексов первого и последнего элементов }

L:=0; R:=aList.Count-1;

while L <= R do

begin

{ Индекс среднего элемента }

M:=(L + R) div 2;

{ Сравнить значение среднего элемента с искомым }

CompareResult:=aCompare(aList.List[M], aItem);

{ Если значение среднего элемента меньше искомого -

переместить левый индекс на позицию до среднего индекса }

if CompareResult < 0 then

L:=M+1 else

{ Если значение среднего элемента больше искомого -

переместить правый индекс на позицию после среднего индекса }

if CompareResult > 0 then

R:=M-1 else

begin

Result:=M;

Exit;

end;

end;

Result:=-1;

end;