№59 Основные структуры данных – деревья, бинарные деревья. Основные
операции. Примеры использования
Основные
определения
Дерево - это граф, который характеризуется
следующими свойствами:
Граф - это сложная нелинейная многосвязная динамическая структура,
отображающая свойства и связи сложного объекта.
Название "дерево" проистекает из логической
эквивалентности древовидной структуры абстрактному дереву в теории
графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ.
Те узлы, которые не ссылаются ни на какие другие узлы дерева,
называются ЛИСТЬЯМИ (или терминальными вершинами)(рис. 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. Изображения
бинарных деревьев
Бинарные деревья, изображенные на рис.6.13(a) и
6.13(d), представляют собой разные позиционные деревья, хотя они не
являются разными упорядоченными деревьями.
В позиционном бинарном дереве каждая вершина
представлена единственным образом посредством строки символов над
алфавитом {0,1}, при этом корень характеризуется пустой строкой. Любой
сын вершины "u" характеризуется строкой, префикс (начальная часть)
которой является строкой, характеризующей "u".
Примером бинарного дерева является фамильное дерево
с отцом и матерью человека в качестве его потомков. Еще один пример -
это арифметическое выражение с двухместными операциями, где каждая
операция представляет собой ветвящийся узел с операндами в качестве
поддеревьев.
Представить m-арное дерево в памяти ЭВМ сложно, т.к.
каждый элемент дерева должен содержать столько указателей, сколько
ребер выходит из узла (при m-3,4.5.6... соответствует 3,4,5,6...
указателей). Это приведет к повышенному расходу памяти ЭВМ,
разнообразию исходных элементов и усложнит алгоритмы обработки дерева.
Поэтому m-арные деревья, лес необходимо привести к бинарным для
экономии памяти и упрощению алгоритмов. Все узлы бинарного дерева
представляются в памяти ЭВМ однотипными элементами с двумя указателями
(см.разд. 6,2,5), кроме того, операции над двоичными деревьями
выполняются просто и эффективно.
Дерево и лес любого вида можно преобразовать
единственным образом в эквивалентное бинарное дерево.
Правило построения бинарного дерева из любого
дерева:
В результате преобразования любого дерева в бинарное
получается дерево в виде левого поддерева, подвешенного к корневой
вершине.
В процессе преобразования правый указатель каждого
узла бинарного дерева будет указывать на соседа по уровню. Если
такового нет, то правый указатель NIL. Левый указатель будет указывать
на вершину следующего уровня. Если таковой нет, то указатель
устанавливается на NIL.
Рис.6.14. Исходное дерево
Рис.6.15 Промежуточный
результат перестройки дерева
Рис. 6.16. Представление
дерева в виде бинарного
Описанный выше метод представления произвольных
упорядоченных деревьев посредством бинарных деревьев можно обобщить на
представление произвольного упорядоченного леса.
Правило построения бинарного дерева из леса: корни
всех поддеревьев леса соединить горизонтальными связями. В полученном
дереве узлы в данном примере будут располагаться на трех уровнях. Далее
перестраивать по ранее рассмотренному плану: в начале поддерево с
корнем А, затем В и затем Н. В результате преобразования упорядоченного
леса в бинарное дерево получается полное бинарное дерево с левым и
правым поддеревом.
рис.6.17. Упорядоченный лес
Рис.6.18. Промежуточный
результат перестройки леса
Рис. 6.19. Представление леса
в виде 2-го дерева
В результате преобразования упорядоченного леса в
бинарное дерево получается полное бинарное дерево с левым и правым
поддеревом.
Деревья можно представлять с помощью связных списков
и массивов (или последовательных списков).
Чаще всего используется связное представление
деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение
состоит в том, что задается связь от отца к сыновьям. В бинарном дереве
имеется два указателя, поэтому удобно узел представить в виде
структуры:
где LPTR - указатель на левое поддерево, RPTR -
указатель на правое поддерево, DATA - содержит информацию, связанную с
вершиной.
Рассмотрим машинное представление бинарного дерева,
изображенного на рис. 6.20.
Рис. 6.20. Логическое
представление дерева
Рис. 6.21. Машинное связное
представление дерева представленного на рис.6.20
Рассмотрим последовательное представление деревьев.
Оно удобно и эффективно в случае, если древовидная структура в течение
времени своего существования не подвергается значительным изменениям,
за счет включения вершин, удаления вершин и т.д.
Выбор метода последовательного представления
деревьев определяется также набором тех операций, которые должны быть
выполнены над древовидными структурами. (Пример статистической
древовидной структуры - пирамидальный метод сортировки). Простейший
метод представления дерева в виде последовательной структуры
заключается во введении вектора FATHER, задающего отбор для всех его
вершин. Этот метод можно использовать также для представления леса.
Недостаток метода - он не отображает упорядочения вершин дерева. Если в
предыдущем примере поменять местами вершины 9 и 10, последовательное
представление останется тем же.
Рис. 6.22. Диаграммы дерева:
а) исходное б) перестройка в бинарное
Последовательное представление дерева, логическая
диаграмма которого дана на рис. 6.22 , задается следующим образом:
i 1 2 3 4 5 6 7 8 9 10
FATHER [i] 0 1 1 1 2 3 3 7 4 4 ,
где ветви определяются как
{(FATHER[i],i)}, i = 2,3,...,10.
Вершины 2,3,4 являются сыновьями вершины 1, вершина
5 - сыном вершины 2, вершины 6,7 - сыновьями вершины 3, вершина 8 имеет
отца вершина 7 и вершины 9 и 10 - сыновья вершины 4.
Числовые поля данных используются здесь, чтобы
упростить представление дерева. Корневая вершина не имеет отца, поэтому
вместо отца для нее задается нулевое значение.
Общее правило: если T обозначает индекс корневой
вершины дерева, то FATHER[T] = 0.
Другой метод последовательного представления
деревьев заключается в использовании физической смежности элементов
машинной памяти вместо одного из полей LPTR или RPTR, например, способ
опускания полей, т.е. чтобы вершины появлялись в нисходящем порядке.
Дерево (рис.6.22б), можно описать как:
Рис. 6.23. Последовательное
представление дерева методом опускания полей
где RPTR,DATA и TAG представляют векторы. В данном
методе указатель LPTR не требуется, т.к. если бы он не был пуст, то
указывал бы на вершину, стоящую непосредственно справа от данной.
Вектор TAG - бинарный вектор, в котором единицы отмечают концевые
вершины исходного дерева. При таком представлении имеются значительные
потери памяти, т.к. свыше половины указателей RPTR оказываются пустыми.
Эти пустые места можно использовать путем установки указателя RPTR
каждой данной вершины на вершину, которая следует непосредственно за
поддеревом, расположенном под ней. В таком представлении поле RPTR
переименовывается в RANGE:
Рис. 6.24. Последовательное
представление дерева с размещением вершин в возрастающем порядке
В этом случае поле TAG не требуется поскольку
концевой узел определяется условием RANGE(P) = P + 1.
Третий метод состоит в представлении дерева общего
вида на основе его восходящего обхода. Такое представление состоит из
двух векторов: один вектор описывает все вершины дерева в восходящей
последовательности, а второй - задает полустепени исхода этих вершин
(см. рис.6.25). Восходящий метод представления удобен для вычисления
функцией, заданных на определенных вершинах дерева ( например,
использование таких функций для генерации объектного кода по обратной
польской записи некоторого выражения ).
Рис. 6.25. Последовательное
представление дерева на основе восходящего обхода
В заключении приведем два важных понятия.
Подобие бинарных деревьев - два дерева подобны, если
они имеют одинаковую структуру ( форму ).
Эквивалентные бинарные деревья - два дерева
эквивалентные, если они подобны, и если соответствующие вершины у них
содержат одинаковую информацию.
Над деревьями определены следующие основные
операции, для которых приведены реализующие их программы.
Приведенные ниже программы процедур и функций могут
быть непосредственно использованы при решении индивидуальных задач.
Кроме выше указанных процедур приведены следующие процедуры и функции:
Для прошитых деревьев:
- функция нахождения сына данного узла ( Inson );
- функция нахождения отца данного узла ( Inp );
-
ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ).
Нужная вершина в дереве ищется по ключу. Поиск в
бинарном дереве осуществляется следующим образом.
Пусть построено некоторое дерево и требуется
найти звено с ключом X. Сначала сравниваем с X ключ, находящийся в
корне дерева. В случае равенства поиск закончен и нужно возвратить
указатель на корень в качестве результата поиска. В противном случае
переходим к рассмотрению вершины, которая находится слева внизу, если
ключ X меньше только что рассмотренного, или справа внизу, если ключ X
больше только что рассмотренного. Сравниваем ключ X с ключом,
содержащимся в этой вершине, и т.д. Процесс завершается в одном из двух
случаев:
- 1) найдена вершина, содержащая ключ, равный ключу
X;
- 2) в дереве отсутствует вершина, к которой нужно
перейти для выполнения очередного шага поиска.
В первом случае возвращается указатель на найденную
вершину. Во втором - указатель на звено, где остановился поиск, (что
удобно для построения дерева ). Реализация функции Find приведена в
программном примере 6.2.
{=== Программный пример 6.2. Поиск звена по ключу === }
Function Find(k:KeyType;d:TreePtr;var rez:TreePtr):bollean;
{ где k - ключ, d - корень дерева, rez - результат }
Var
p,g: TreePtr;
b: boolean;
Begin
b:=false; p:=d; { ключ не найден }
if d <> NIL then
repeat q: =p; if p^.key = k then b:=true { ключ найден }
else begin q:=p; { указатель на отца }
if k < p^.key then p:=p^.left { поиск влево }
else p:=p^.right { поиск вправо}
end; until b or (p=NIL);
Find:=b; rez:=q;
End; { Find }
ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ).
Для включения записи в дерево прежде всего нужно
найти в дереве ту вершину, к которой можно "подвести" (присоединить)
новую вершину, соответствующую включаемой записи. При этом
упорядоченность ключей должна сохраняться.
Алгоритм поиска нужной вершины, вообще говоря, тот
же самый, что и при поиске вершины с заданным ключом. Эта вершина будет
найдена в тот момент, когда в качестве очередного указателя,
определяющего ветвь дерева, в которой надо продолжить поиск, окажется
указатель NIL ( случай 2 функции Find ). Тогда процедура вставки
записывается так, как в программном примере 6.3.
{=== Программный пример 6.3. Добавление звена ===}
Procedure Dob (k:KeyType; var d:TreePtr; zap:data);
{ k - ключ, d - узел дерева, zap - запись }
Var
r,s: TreePtr;
t: DataPtr;
Begin
if not Find(k,d,r) then
begin (* Занесение в новое звено текста записи *)
new(t); t^:=zap; new(s); s^.key:=k;
s^.ssil:=t; s^.left:=NIL; s^.right:=NIL;
if d = NIL then d:=s (* Вставка нового звена *)
else if k < r^.key
then r^.left:=s
else r^.right:=s;
end; End; { Dop }
