| Каталог | Индекс раздела |
| Назад | Оглавление | Вперед |
Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.
Многосвязная структура обладает следующими свойствами:
В узлах графа содержится информация об элементах объекта. Связи между узлами задаются ребрами графа. Ребра графа могут иметь направленность, показываемую стрелками, тогда они называются ориентированными, ребра без стрелок - неориентированные.
Граф, все связи которого ориентированные, называется ориентированным графом или орграфом; граф со всеми неориентированными связями - неориентированным графом; граф со связями обоих типов - смешанным графом. Обозначение связей: неориентированных - (A,B), ориентированных -
а).((A,B),(B,A)) и б).(< A,B >,< B,A >).
Рис.6.1. Граф неориентированный (а) и ориентированный (б).
Для ориентированного графа число ребер, входящих в узел, называется полустепенью захода узла, выходящих из узела -полустепенью исхода. Количество входящих и выходящих ребер может быть любым, в том числе и нулевым. Граф без ребер является нуль-графом.
Если ребрам графа соответствуют некоторые значения, то граф и ребра называются взвешенными. Мультиграфом называется граф, имеющий параллельные (соединяющие одни и те же вершины) ребра, в противном случае граф называется простым.
Путь в графе - это последовательность узлов, связанных ребрами; элементарным называется путь, в котором все ребра различны, простым называется путь, в котором все вершины различны. Путь от узла к самому себе называется циклом, а граф, содержащий такие пути - циклическим.
Два узла графа смежны, если существует путь от одного из них до другого. Узел называется инцидентным к ребру, если он является его вершиной, т.е. ребро направлено к этому узлу.
Логически структура-граф может быть представлена матрицей смежности или матрицей инцидентности.
Матрицей смежности для n узлов называется квадратная матрица adj порядка n. Элемент матрицы a(i,j) равен 1, если узел j смежен с узлом i (есть путь < i,j >), и 0 -в противном случае (рис.6.2).
Рис.6.2. Графа и его матрица смежности
Если граф неориентирован, то a(i,j)=a(j,i), т.е. матрица симметрична относительно главной диагонали.
Матрицы смежности используются при построении матриц путей, дающих представление о графе по длине пути: путь длиной в 1 - смежный участок -
Рис.6.3. Матрицы путей
Матрицы инцидентности используются только для орграфов. В каждой строке содержится упорядоченная последовательность имен узлов, с которыми данный узел связан ориетрированными (исходящими) ребрами. На рис.6.4 показана матрица инцидентности для графа рис. 6.2.
Рис.6.4. Матрицы инцидентности
Существуют два основных метода представления графов в памяти ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зависит от природы данных и операций, выполняемых над ними. Если задача требует большого числа включений и исключений узлов, то целесообразно представлять граф связными списками; в противном случае можно применить и матричное представление.
МАТРИЧНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ.
При использовании матриц смежности их элементы представляются в памяти ЭВМ элементами массива. При этом, для простого графа матрица состоит из нулей и единиц, для мультиграфа - из нулей и целых чисел, указывающих кратность соответствующих ребер, для взвешенного графа - из нулей и вещественных чисел, задающих вес каждого ребра.
Например, для простого ориентированного графа, изображенного на рис.6.2 массив определяется как:
mas:array[1..4,1..4]=((0,1,0,0),(0,0,1,1),(0,0,0,1),(1,0,1,0))
Матрицы смежности применяются, когда в графе много связей и матрица хорошо заполнена.
СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ ОРГРАФОВ.
Орграф представляется связным нелинейным списком, если он часто изменяется или если полустепени захода и исхода его узлов велики. Рассмотрим два варианты представления орграфов связными нелинейными списковыми структурами.
В первом варианте два типа элементов - атомарный и узел связи (см. раздел 5.5). На рис.6.5 показана схема такого представления для графа рис.6.2. Скобочная запись связей этого графа:
( < A,B >, < B,C >, < C,D >, < B,D >, < D,C > )
Рис.6.5. Машинное представление графа элементами двух типов
Более рационально представлять граф элементами одного формата, двойными: атом-указатель и указатель-указатель или тройными: указатель-data/down-указатель (см.раздел 5.5). На рис.6.6 тот же граф представлен элементами одного формата.
Рис.6.6. Машинное представление графа однотипными элементами
Многосвязная структура - граф - находит широкое применение при организации банков данных, управлении базами данных, в системах программного иммитационного моделирования сложных комплексов, в системах исскуственного интеллекта, в задачах планирования и в других сферах. Алгоритмы обработки нелинейных разветвленных списков, к которым могут быть отнесены и графы, даны в разделе 5.5.
В качестве примера приведем программу, находящую кратчайший путь между двумя указанными вершинами связного конечного графа.
Пусть дана часть каpты доpожной сети и нужно найти наилучший маpшpут от города 1 до города 5. Такая задача выглядит достаточно пpостой, но "наилучший" маpшpут могут опpеделять многие фактоpы. Например: (1) pасстояние в километpах; (2) вpемя пpохождения маpшpута с учетом огpаничений скоpости; (3) ожидаемая пpодолжительность поездки с учетом доpожных условий и плотности движения; (4) задеpжки, вызванные пpоездом чеpез гоpода или объездом гоpодов; (5) число гоpодов, котоpое необходимо посетить, напpимеp, в целях доставки гpузов. Задачи о кpатчайших путях относятся к фундаментальным задачам комбинатоpной оптимизации.
Сpеди десятков алгоpитмов для отыскания кpатчайшего пути один из лучших пpинадлежит Дейкстpе. Алгоpитм Дейкстpы, опpеделяющий кpатчайшее pасстояние от данной веpшины до конечной, легче пояснить на пpимеpе. Рассмотpим гpаф, изобpаженный на pис.6.7, задающий связь между гоpодами на каpте доpог. Пpедставим гpаф матpицей смежности A, в котоpой: A(i,j)-длина pебpа между узлами i и j. Используя полученную матрицу и матрицы, отражающие другие факторы, можно определить кратчайший путь.
Рис.6.7. Часть дорожной карты, представленная в виде взвешенного графа и его матрицы смежности
{========== Программный пример 6.1 ==============}
{ Алгоритм Дейкстры }
Program ShortWay;
Const n=5; max=10000;
Var a: Array [1..n,1..n] of Integer;
v0,w,edges: Integer;
from,tu,length: Array [1..n] of Integer;
Procedure adjinit;
{ Эта пpоцедуpа задает веса pебеp гpафа посpедством
опpеделения его матpицы смежности A pазмеpом N x N }
Var i,j: Integer;
Begin
{ "Обнуление" матpицы (веpшины не связаны) }
For i:=1 to n do
For j:=1 to n do a[i,j]:=max;
For i:=1 to n do a[i,i]:=0;
{ Задание длин pебеp, соединяющих смежные узлы гpафа }
a[1,2]:=12; a[1,3]:=18; a[1,4]:=10;
a[2,1]:=12; a[2,3]:=6; a[2,5]:=9;
a[3,1]:=18; a[3,2]:=6; a[3,4]:=7; a[3,5]:=3;
a[4,1]:=10; a[4,3]:=7; a[4,5]:=15;
a[5,2]:=9; a[5,3]:=3; a[5,4]:=15;
End;
Procedure printmat;
{ Эта пpоцедуpа выводит на экpан дисплея матpицу
смежности A взвешенного гpафа }
Var i,j: Integer;
Begin writeln;
writeln('Матpица смежности взвешенного гpафа (',n,'x',n,'):');
writeln;
For i:=1 to n do
Begin write ('Ё');
For j:=1 to n do
If a[i,j]=max Then write(' ----') Else write(a[i,j]:6);
writeln(' Ё')
End; writeln;
writeln (' ("----" - pебpо отсутствует)')
End;
Procedure dijkst;
{ Эта пpоцедуpа опpеделяет кpатчайшее pасстояние от начальной веpшины V0 до конечной веpшины W в связном гpафе с неотpицательными весами с помощью алгоpитма, пpинадлежащего Дейкстpе.
Результатом pаботы этой пpоцедуpы является деpево кpатчайших путей с коpнем V0.
| ---- Входные и выходные пеpеменные --- | |
|---|---|
| A(I,J) | длина pебpа, соединяющего веpшины I и J. Если pебpо отсутствует, то A(I,J)=10000 (пpоизвольному большому числу). |
| V0 | начальная веpшина. |
| W | конечная веpшина. |
| N | веpшины в гpафе пpонумеpованы 1,...,N. |
| FROM(I) TU(I) |
содеpжит I-е pебpо в деpеве кpатчайших путей от веpшины FROM(I) к веpшине TU(I) |
| LENGTH(I) | длины LENGTH(I). |
| EDGES | число pебеp в деpеве кpатчайших путей на данный момент. |
| --- Внутpенние пеpеменные --- | |
|---|---|
| DIST(I) | кpатчайшее pасстояние от UNDET(I) до частичного деpева кpатчайших путей. |
| NEXT | очеpедная веpшина, добавляемая к деpеву кpатчайших путей. |
| NUMUN | число неопpеделенных веpшин. |
| UNDET(I) | список неопpеделенных веpшин. |
| VERTEX(I) | веpшины частичного деpева кpатчайших путей, лежащие на кpатчайшем пути от UNDET(I) до V0. } |
Label stpoint;
Var dist,undet,vertex: array[1..n] of Integer;
next,numun,i,j,k,l,jk: Integer;
Begin
edges:=0; next:=v0; numun:=n-1;
For i:=1 to n do
Begin undet[i]:=i; dist[i]:=a[v0,i]; vertex[i]:=v0 End;
undet[v0]:=n; dist[v0]:=dist[n];
goto stpoint;
Repeat
{ Исключение вновь опpеделенной веpшины из списка неопpеделенных}
dist[k]:=dist[numun]; undet[k]:=undet[numun];
vertex[k]:=vertex[numun];
{ Остались ли неопpеделеные веpшины ? }
dec(numun);
{ Обновление кpатчайшего pасстояния до всех неопpеделенных веpшин }
For i:=1 to numun do
Begin j:=undet[i]; jk:=l+a[next,j];
If dist[i] > jk Then Begin vertex[i]:=next; dist[i]:=jk End
End;
stpoint:{Запоминание кpатчайшего pасст.до неопpеделенной веpшины}
k:=1; l:=dist[1];
For i:=1 to numun do
If dist[i] < l Then Begin l:=dist[i]; k:=i End;
{ Добавление pебpа к деpеву кpатчайших путей }
inc(edges); from[edges]:=vertex[k]; tu[edges]:=undet[k];
length[edges]:=l; next:=undet[k]
Until next = w { Достигли ли мы w }
End;
Procedure showway;
{ Эта пpоцедуpа выводит на экpан дисплея кpатчайшее pасстояние между
веpшинами V0 и W взвешенного гpафа, опpеделенное пpоцедуpой dijkst }
Var i: Integer;
Begin
writeln; writeln('Кpатчайшее pасстояние между');
writeln('узлами ',v0,' и ',w,' pавно ',length[edges])
End;
{ Основная пpогpамма }
Begin
adjinit; printmat; v0:=1;w:=5;
dijkst; showway; readln
End.Дерево - это граф, который характеризуется следующими свойствами:
Название "дерево" проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами)(рис. 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 | DATA | RPTR |
где 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. Последовательное представление дерева на основе восходящего обхода
В заключении приведем два важных понятия.
Подобие бинарных деревьев - два дерева подобны, если они имеют одинаковую структуру ( форму ).
Эквивалентные бинарные деревья - два дерева эквивалентные, если они подобны, и если соответствующие вершины у них содержат одинаковую информацию.
Над деревьями определены следующие основные операции, для которых приведены реализующие их программы.
Приведенные ниже программы процедур и функций могут быть непосредственно использованы при решении индивидуальных задач. Кроме выше указанных процедур приведены следующие процедуры и функции:
Для прошитых деревьев:
ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ).
Нужная вершина в дереве ищется по ключу. Поиск в бинарном дереве осуществляется следующим образом.
Пусть построено некоторое дерево и требуется найти звено с ключом X. Сначала сравниваем с X ключ, находящийся в корне дерева. В случае равенства поиск закончен и нужно возвратить указатель на корень в качестве результата поиска. В противном случае переходим к рассмотрению вершины, которая находится слева внизу, если ключ X меньше только что рассмотренного, или справа внизу, если ключ X больше только что рассмотренного. Сравниваем ключ X с ключом, содержащимся в этой вершине, и т.д. Процесс завершается в одном из двух случаев:
В первом случае возвращается указатель на найденную вершину. Во втором - указатель на звено, где остановился поиск, (что удобно для построения дерева ). Реализация функции 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 }
ОБХОД ДЕРЕВА.
Во многих задачах, связанных с деревьями, требуется осуществить систематический просмотр всех его узлов в определенном порядке. Такой просмотр называется прохождением или обходом дерева.
Бинарное дерево можно обходить тремя основными способами: нисходящим, смешанным и восходящим ( возможны также обратный нисходящий, обратный смешанный и обратный восходящий обходы). Принятые выше названия методов обхода связаны с временем обработки корневой вершины: До того как обработаны оба ее поддерева (Preorder), после того как обработано левое поддерево, но до того как обработано правое (Inorder), после того как обработаны оба поддерева (Postorder). Используемые в переводе названия методов отражают направление обхода в дереве: от корневой вершины вниз к листьям - нисходящий обход; от листьев вверх к корню - восходящий обход, и смешанный обход - от самого левого листа дерева через корень к самому правому листу.
Схематично алгоритм обхода двоичного дерева в соответствии с нисходящим способом может выглядеть следующим образом:
Для примера рассмотрим возможные варианты обхода дерева (рис.6.26).
При обходе дерева представленного на рис.6.26 этими тремя методами мыполучим следующие последовательности: ABCDEFG ( нисходящий ); CBAFEDG ( смешанный ); CBFEGDA ( восходящий ).
Рис.6.26. Схема дерева
НИСХОДЯЩИЙ ОБХОД (Preorder, r_Preorder).
В соответствии с алгоритмом, приведенным выше, текст процедуры имеет вид:
{=== Программный пример 6.4. Нисходящий обход ===}
Procedure Preorder (t: TreePtr);
Type
Stack=^Zveno;
Zveno = record
next: Stack;
el: pointer;
end;
Var
st: stack;
p: TreePtr;
(*------------ Процедура занесения в стек указателя ------*)
Procedure Push_st (var st:stack; p:pointer);
Var
q: stack;
begin new(q); q^.el:=p; q^.next:=st; st:=g; end;
(*----------- Функция извлечения из стека указателя ------*)
Function Pop_st (var st: stack):pointer;
Var
e,p: stack;
begin Pop_st:=st^.el; e:=st; st:=st^.next; dispose(e); end;
Begin
if t = NIL then
begin writeln('Дерево пусто'); exit; end
else begin st:=nil; Push_st(St,t); end;
while st <> nil do { контроль заполнения стека }
begin p:=Pop_st(st);
while p <> nil do
begin { Обработка данных звена }
if p^.right <> nil
then Push_st(st,p^.right);
p:=p^.left;
end; end;
End; { Preorder }
Трассировка нисходящего обхода приведена в табл.6.1:
Таблица 6.1
РЕКУРСИВНЫЙ НИСХОДЯЩИЙ ОБХОД.
Алгоритм существенно упрощается при использовании рекурсии. Так, нисходящий обход можно описать следующим образом:
Алгоритм рекурсивного нисходящего обхода реализован в программном примере 6.5.
{=== Программный пример 6.5. Рекурсивное выполнение нисходящего обхода ===}
Procedure r_Preorder (t: TreePtr);
begin
if t = nil then begin writeln('Дерево пусто'); exit; end;
(*------------------- Обработка данных звена --------------*)
................................
if t^.left <> nil then r_Preorder(t^.left);
if t^.right <> nil then r_Preorder(t^.right);
End; { r_Preorder }
CМЕШАННЫЙ ОБХОД (Inorder, r_Inorder).
Смешанный обход можно описать следующим образом:
В программном примере 6.6. реализован алгоритм смешанного обхода дерева.
{=== Программный пример 6.6. Процедура смешанного обхода ===}
Procedure Inorder (t: TreePtr);
label 1;
type Stack=^Zveno; { тип стека }
Zveno = record
next: Stack;
El: pointer; end;
Var
st: stack;
p: TreePtr;
(*---------- Процедура занесения в стек указателя ---------*)
Procedure Push_st (var st:stack; p:pointer);
Var
q: stack;
begin new(q); q^.el:=p; q^.next:=st; st:=g; end;
(*------------ Функция извлечения из стека указателя ------*)
Function Pop_st (var st: stack):pointer;
Var
e,p: stack;
begin Pop_st:=st^.el; e:=st; st:=st^.next; dispose(e); end;
Begin
if t = NIL then begin writeln('Дерево пусто'); exit; end
else begin p:=t; st:=nil; end;
1: while p^.left <> nil do
begin (* Спуск по левой ветви и заполнение очереди *)
Push_st(st,p); p:=p^.left; end;
if st = NIL { контроль заполнения стека }
then exit;
p:=Pop_st(st);{выборка очередного элемента на обработку}
(*--------------- Обработка данных звена --------------*)
................................
if p^.right <> nil
then begin p:=p^.right; { переход к правой ветви }
goto 1; end;
End; { Inorder }
Трассировка смешанного обхода приведена в табл. 6.2:
Таблица 6.2
Рекурсивный смешанный обход описывается следующим образом:
Текст программы рекурсивной процедуры ( r_Inorder ) демонстрируется в программном примере 6.7.
{=== Программный пример 6.7. Рекурсивное выполнение смешанного обхода ===}
Procedure r_Inorder(t: TreePtr);
begin
if t = nil then
begin writeln('Дерево пусто'); exit; end;
if t^.left <> nil then R_inorder (t^.left);
(*--------------- Обработка данных звена --------------*)
................................
if t^.right <> nil then R_inorder(t^.right);
End;
ВОСХОДЯЩИЙ ОБХОД ( Postorder, r_Postorder ).
Трудность заключается в том, что в отличие от Preorder в этом алгоритме каждая вершина запоминается в стеке дважды: первый раз - когда обходится левое поддерево, и второй раз - когда обходится правое поддерево. Таким образом, в алгоритме необходимо различать два вида стековых записей: 1-й означает, что в данный момент обходится левое поддерево; 2-й - что обходится правое, поэтому в стеке запоминается указатель на узел и признак (код-1 и код-2 соответственно).
Алгоритм восходящего обхода можно представить следующим образом:
Текст программы процедуры восходящего обхода ( Postorder) представлен в программном примере 6.8.
{=== Программный пример 6.8. Восходящий обход ====}
Procedure Postorder (t: TreePtr);
label 2;
Var
p: TreePtr;
top: point; { стековый тип }
Sign: byte; { sign=1 - первый вид стековых записей}
{ sign=2 - второй вид стековых записей}
Begin (*------------- Инициализация ------------------*)
if t = nil then
begin writeln('Дерево пусто'); exit; end
else begin p:=t; top:=nil; end; {инициализация стека}
(*------- Запоминание адресов вдоль левой ветви -------*)
2: while p <> nil do
begin s_Push(top,1,p); { заносится указатель 1-го вида}
p:=p^.left; end;
(*-- Подъем вверх по дереву с обработкой правых ветвей ----*)
while top <> nil do
begin p:=s_Pop(top,sign); if sign = 1 then
begin s_Push(top,0,p); { заносится указатель 2-го вида }
p:=p^.right; goto 2; end
else (*---- Обработка данных звена ---------*)
................................
end; End; { Postorder }
РЕКУРСИВНЫЙ СМЕШАННЫЙ ОБХОДописывается следующим образом:
Текст программы процедуры рекурсивного обхода (r_Postorder) демонстрируется в програмном примере 6.9.
{ ==== Программный пример 6.9. ===== }
(*--------- Рекурсивное выполнение нисходящего обхода -----*)
Procedure r_Postorder (t: TreePtr);
Begin
if t = nil then begin writeln('Дерево пусто'); exit; end;
if t^.left <> nil then r_Postorder (t^.left);
if t^.right <> nil then r_Postorder (t^.right);
(*-------------- Обработка данных звена --------------*)
................................
End; { r_Postorder }
Если в рассмотренных выше процедурах поменять местами поля left и right, то получим процедуры обратного нисходящего, обратного смешанного и обратного восходящего обходов.
ПРОЦЕДУРЫ ОБХОДА ДЕРЕВА, ИСПОЛЬЗУЮЩИЕ СТЕК.
Тип стека при нисходящем обходе.
Stack=^Zveno;
Zveno = record
next: Stack;
El: pointer;
end;
Процедура включения элемента в стек при нисходящем и смешанном обходе ( Push_st ) приведена в программном примере 6.10.
{ === Програмнный пример 6.10 ====}
Procedure Push_st (var st: stack; p: pointer);
Var
q: stack;
begin new(q); q^.el:=p; q^.next:=st; st:=q; end;
Функция извлечения элемента из стека при нисходящем и смешанном обходе ( Pop_st ) приведена в программном примере 6.11.
{ === Програмнный пример 6.11 ====}
Function Pop_st (var st: stack):pointer;
Var
e,p: stack
begin
Pop_st:=st^.el;
e:=st; { запоминаем указатель на текущую вершину }
st:=st^.next;{сдвигаем указатель стека на следующий элемент}
dispose(e); { возврат памяти в кучу }
end;
При восходящем обходе может быть предложен следующий тип стека:
point=^st;
st = record
next: point;
l: integer;
add: pointer;
end;
Процедура включения элемента в стек при восходящем обходе ( S_Push ) приведена в программном примере 6.12.
{ === Програмнный пример 6.12 ====}
Procedure S_Push (var st: point; Har: integer; add: pointer); Var q: point;
begin
new(q); { выделяем место для элемента }
q^.l:=Har; { заносим характеристику }
q^.add:=add; { заносим указатель }
q^.next:=st; { модифицируем стек }
st:=q;
end;
Функция извлечения элемента из стека при восходящем обходе (S_Pop) демонстрируется в программном примере 6.13.
{ === Програмнный пример 6.13 ====}
Function S_Pop (var st: point; var l: integer):pointer;
Var
e,p: point;
begin
l:=st^.l;
S_Pop:=st^.add;
e:=st; { запоминаем указатель на текущую вершину}
st:=st^.next; {сдвигаем указатель стека на след. элемент }
dispose(e); { уничтожаем выбранный элемент }
end;
ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ.
Под прошивкой дерева понимается замена по определенному правилу пустых указателей на сыновей указателями на последующие узлы, соответствующие обходу.
Рассматривая бинарное дерево, легко обнаружить, что в нем имеются много указателей типа NIL. Действительно в дереве с N вершинами имеется ( N+1 ) указателей типа NIL. Это незанятое пространство можно использовать для изменения представления деревьев. Пустые указатели заменяются указателями - "нитями", которые адресуют вершины дерева, и расположенные выше. При этом дерево прошивается с учетом определенного способа обхода. Например, если в поле left некоторой вершины P стоит NIL, то его можно заменить на адрес, указывающий на предшественника P, в соответствии с тем порядком обхода, для которого прошивается дерево. Аналогично, если поле right пусто, то указывается преемник P в соответствии с порядком обхода.
Поскольку после прошивания дерева поля left и right могут характеризовать либо структурные связи, либо "нити", возникает необходимость различать их, для этого вводятся в описание структуры дерева характеристики левого и правого указателей (FALSE и TRUE).
Таким образом, прошитые деревья быстрее обходятся и не требуют для этого дополнительной памяти (стек), однако требуют дополнительной памяти для хранения флагов нитей, а также усложнены операции включения и удаления элементов дерева.
Прошитое бинарное дерево на Паскале можно описать следующим образом:
type TreePtr:=^S_Tree;
S_Tree = record
key: KeyType; { ключ }
left,right: TreePtr; { левый и правый сыновья }
lf,rf: boolean; { характеристики связей }
end;
где lf и rf - указывают, является ли связь указателем на элемент или нитью. Если lf или rf равно FALSE, то связка является нитью.
До создания дерева головная вершина имеет следующий вид: Здесь пунктирная стрелка определяет связь по нити. Дерево подшивается к левой ветви.
Рис. 6.27.
В программном примере 6.14 приведена функция ( Inson ) для определения сына (преемника) данной вершины.
{ === Програмнный пример 6.14 ====}
(*------ Функция, находящая преемника данной вершины X ----*)
(*-------- в соответствии со смешанным обходом ------------*)
Funtion Inson (x: TreePtr):TreePtr;
begin
Inson:=x^.right;
if not (x^.rf) then exit; { Ветвь левая ?}
while Insonon^.lf do { связь не нить }
Inson:=Inson^.left; { перейти по левой ветви }
end; { Inson }
В программном примере 6.15 приведена функция (Int) для определения отца (предка) данной вершины.
{ === Програмнный пример 6.15 ====}
(*---------- Функция, выдающая предшественника узла ------*)
(*------- в соответствии со смеш1анным обходом ------------*)
Function Inp (x:TreePtr):TreePtr;
begin
Inp:=x^.left;
if not (x^.lf) then exit;
while Inp^.rf do Inp:=Inp^.right; { связка не нить }
end;
В программном примере 6.16 приведена функция, реализующая алгоритм включения записи в прошитое дерево ( leftIn ). Этот алгоритм вставляет вершину P в качестве левого поддерева заданной вершины X в случае, если вершина X не имеет левого поддерева. В противном случае новая вершина вставляется между вершиной X и вершиной X^.left. При этой операции поддерживается правильная структура прошивки дерева, соответствующая смешанному обходу.
{ === Програмнный пример 6.16 ====}
(*- Вставка p слева от x или между x и его левой вершиной -*)
Procedure LeftIn (x,p: TreePtr);
Var
q: TreePtr;
begin
(*--------------- Установка указателя ------------------*)
p^.left:=x^.left; p^.lf:=x^.lf; x^.left:=p;
x^.lf:=TRUE; p^.right:=x; p^.rf:=FALSE;
if p^.lf then
(*-------- Переустановка связи с предшественником --------*)
begin q:=TreePtr(Inp(p)); q^.right:=p; q^.rf:=FALSE;
end; end; { LeftIn }
Для примера рассмотрим прошивку дерева приведенного на рис.6.20. при нисходящем обходе.
Машинное представление дерева при нисходящем обходе с прошивкой приведено на рис.6.28.
Рис. 6.28. Машинное связное представление исходного дерева, представленного на рис.6.20 при нисходящем обходе с прошивкой
Трассировка нисходящего обхода с прошивкой приведена в табл.6.3.
Рассмотрим на примере того же дерева прошивку при смешанном обходе. Машинное представление дерева при смешанном обходе с прошивкой приведено на рис.6.28.
| @ указателя | Узел | Обработка узла | Выходная строка |
| PT:=H | H | ||
| LPH | A | A | A |
| LPA | B | B | AB |
| LPB | C | C | ABC |
| -LPC | |||
| -RPC | D | D | ABCD |
| LPD | E | E | ABCDE |
| LPE | F | F | ABCDEF |
| -LPF | |||
| -RPF | G | G | ABCDEFG |
| -LPG | |||
| -RPG | H | Конец алгоритма |
Таблица 6.3
Рис. 6.29. Машинное связное представление дерева при смешанном обходе с прошивкой
Трассировка смешанного обхода с прошивкой приведена в табл.6.4.
| @ указателя | Узел | Обработка узла | Выходная строка |
| P:=PT | H | ||
| LPH | A | ||
| LPA | B | ||
| LPB | C | ||
| -LPC | C | C | C |
| -RPC | B | B | CB |
| -RPB | A | A | CBA |
| RPA | D | ||
| LPD | E | ||
| LPE | F | ||
| -LPF | F | F | CBAF |
| -RPF | E | E | CBAFE |
| -RPE | D | D | CBAFED |
| RPD | G | ||
| -LPG | G | G | CBAFEDG |
| -RPG | H | Конец алгоритма |
Таблица 6.4.
Деревья имеют широкое применение при реализации трансляторов таблиц решений, при работе с арифметическими выражениями, при создании и ведении таблиц символов, где их используют для отображения структуры предложений, в системах связи для экономичного кодирования сообщений и во многих других случаях. Рассмотрим некоторые из них.
Пусть требуется закодировать длинное сообщение в виде строки битов: А В А С С D А кодом, минимизирующим длину закодированного сообщения.
1) назначим коды:
| Символ | Код |
| A | 010 |
| B | 100 |
| C | 000 |
| D | 111 |
А В А С С D А7*3=21 всего 21 бит - неэффективно
| Символ | Код |
| A | 00 |
| B | 01 |
| C | 10 |
| D | 11 |
00 01 00 10 10 11 00
А В А С С D АТогда кодировка требует лишь 14 бит.
А -3 раза, С -2 раза, В -1 раз, D -1 раз то-есть можно:
Если А имеет код 0 т.к часто встречается, то В, С, D - начинаются с 1, если дальше 0,то это С, следующий может быть 0 или 1: 1 - D , 0 - В; то-есть В и D различаются по последнему биту, А -по первому, С - по второму, B и D - по третьему.
| Символ | Код |
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
Таким образом, если известны частоты появления символов в сообщении, то метод реализует оптимальную схему кодирования.
Частота появления группы символов равна сумме частот появления каждого символа.
Сообщение АВАССDА кодируется как 0110010101110 и требует лишь 13 бит.
В очень длинных сообщениях, которые содержат символы, встречающиеся очень редко - экономия существенна.
Рис.6.30 Дерево Хаффмена
Обычно коды создаются на основе частоты во всем множестве сообщений, а не только в одном.
Операция объединения двух символов в один использует структуру бинарного дерева. Каждый узел содержит символ и частоту вхождения. Код любого символа может быть определен просмотром дерева снизу вверх, начиная с листа. Каждый раз при прохождении узла приписываем слева к коду 0, если поднимаемся по левой ветви и 1, если поднимаемся по правой ветви. Как только дерево построено код любого символа алфавита может быть определен просмотром дерева снизу вверх, начиная с места, представляющего этот символ. Начальное значение кода пустая строка. Каждый раз, когда мы поднимаемся по левой ветви, к коду слева приписывается ноль, если справа - 1. Часть info узла дерева содержит частоту появления символа представляемого этим узлом. Дерево Хаффмена строго бинарное. Если в алфавите п символов, то дерево Хаффмена может быть представлено массивом узлов размером 2п-1. Поскольку размер памяти, требуемой под дерево известен, она может быть выделена заранее.
МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ.
Дано выражение а*(-b)+с/d
Операции выполняются над выражениями, представленными в виде бинарных деревьев. Такие выражения можно символьно складывать,
Рис.6.31 Представление выражения в виде дерева
Рис. 6.32 Представление выражения в виде бинарного дерева.
перемножать, вычитать, дифференцировать, интегрировать, сравнивать на эквивалентность и т.д. Т.е. получаются символьные выражения, которые можно закодировать в виде таблиц:
| LPTR | DATA | RPTR |
Для неконцевой вершины поле TYPE задает арифметическую операцию, связанную с этой вершиной. Значения поля TYPE вершин +,-,*, /, (-) и равны 1, 2, 3, 4, 5, 6 соответственно.
Для концевых вершин поле символа в TYPE имеет значение 0, что означает константу или переменную. В этом случае правый указатель вершины задает адрес таблицы символов, который соответствует данной константе или переменной. В дереве указывается тип оператора, а не он сам, что позволяет упростить обработку таких деревьев.
Рис.6.33 Таблица символов
Процедура вычислений:
Создается семимерный массив меток и его элементам задаются требуемые значения.Оператор генерирует метку исходя из значения поля корневой вершины. И передается управление управление оператору, помеченного меткой. Если данная вершина концевая, то в качестве значения выдается значение переменной или константы, обозначенной этой вершиной. Эта операция выполняется путем использования правого указателя данной вершины для ссылки на нужную запись в таблице символов. Для неконцевой вершины инициализируются рекурсивные вычисления ее поддеревьев, характеризующих операнды текущего оператора. Этот процесс продолжается до тех пор, пока не будут достигнуты листья дерева. Для полученных листьев значения выбираются из соответствующих записей таблицы символов.
Ниже приводится программа, вычисляющая арифметическое выражение.
В качестве примера приложения бинарных деревьев сформулируем алгоритм ведения древовидно-структурированной таблицы символов.
Основной критерий, которому должна удовлетворять программа ведения таблицы символов, состоит в максимальной эффективности поиска в этой таблицы. Это требование возникает на этапе компиляции, когда осуществляется много ссылок на записи таблицы символов. Необходимо, чтобы над таблицей символов можно было бы проверить две операции - включение записей в таблицу и поиск их в ней. Причем, каждая из этих операций содержит операцию просмотра таблицы.
Древовидное представление таблицы выбирают по двум причинам:
1. Записи символов по мере их возникновения равномерно распределяются в соответствии с лексикографическим порядком, то при хранении записей в дереве в таком же порядке табличный просмотр становится почти эквивалентен двоичному просмотру.
2. В древовидной структуре легко поддерживать лексикографический порядок, т.к. при включении в нее новой записи необходимо изменить лишь несколько указателей.
Для простоты предположим, что при ведении таблицы символов используется достаточно развитая система записей, допускающая символьные строки переменной длины.
Кроме того, предположим, что подпрограмма ведения таблицы символов используется при создании дерева данного блока программы. Это предположение ведет к тому, что попытка повторного включения записи вызывает ошибку. В глобальном контексте повторные записи допустимы, если они соответствую разным уровням блочной структуры программы.
В некотором смысле таблица символов представляет собой множество деревьев - по одному для каждого уровня блочной структуры программы.
Вершины бинарного дерева таблицы символов имеют формат:
| LPTR | SYMBOLS | INFO | RPTR |
Новая вершина создается путем исполнения оператора P при этом ее адрес запоминается в переменной P.
Еще предлагается, что перед любым исполнением программы ведения таблицы символов на некотором чистом уровне блочной структуры уже имеется соответствующая головная вершина дерева, в поле SYMBOLS в которое занесено значение, лексикографически большее, чем любой допустимый идентификатор. Эта вершина адресуется указателем HEAD[n], где n означает номер уровня блочной структуры. Т.е. предполагается, что при входе в блок осуществляется обращение к основной переменной, управляющей созданием головных вершин деревьев.
Операции включения записи в таблицу и операция поиска в таблице содержат значительное количество одинаковых действий ( например, просмотр ), поэтому рассмотрим только алгоритм TABLE, а различать включение или поиск по переменной FLAG. Если FLAG - истинно - то включение глобальной переменной, если - ложно - поиск. DATA - содержит имя идентификатора и дополнительную информацию для него.
Если включение новой записи было выполнено успешно, то FLAG сохраняет свое первоначальное значение противоположное начальному, что указывает на ошибку, означающую, что искомый идентификатор уже присутствует в таблице данного уровня и выполняемый алгоритм завершается. Если FLAG = ложь, то надо выполнить операцию поиска записи. В этом случае переменная NAME содержит имя идентификатора, который необходимо найти, а значение переменной. При успешном поиске переменная DATA устанавливается на поле INFO соответствующее записи таблицы символов. FLAG сохраняет свое значение и осуществляет возврат к вызванной программе. При неудаче операции поиска, FLAG меняет свое значение и выходит из алгоритма. В этом случае основная программа должна осуществлять поиск записи в таблице, более низких уровней. Деревья с головными вершинами HEAD[n-1], HEAD[n-2] b т.д.
АЛГОТИТМ TABLE.
На вход подается глобальная переменная n, идентифицирующая номер уровня текущего блока и глобальная переменная FLAG, задающая требуемую операцию. Описываемый алгоритм выполняет эту операцию над древовидной структурированной таблицей символов, локальной относительно блока уровня u. Параметры DATA и NAME используются для передачи данных между алгоритмом и от того больше или меньше значение NAME кода исследуемой записи таблицы, осуществляется установка указателя на левый или правый потолок данной вершины и возврат к шагу 2 для дальнейших сравнений. Поскольку дерево упорядочено таким образом, что код каждой вершины левого ( правого ) поддерева лексикографических меньше (больше), чем код корневой вершины, то попытка спуска по пустому дереву означает, что требуемая запись в таблице отсутствует; при этом определяется место, где данная запись расположена.
В этом случае, если требовалось найти запись, то выдается сообщение об ошибке, в противном случае создается новая вершина, в нее заносится нужная информация и она включается в уже существующую древовидную структуру слева или справа от исследуемой вершины.
ОПИСАНИЕ ПРОГРАММЫ:
Последовательность решения задачи:
Процедуры программы:
Процедура Tree - преобразует математическое выражение в бинарное дерево. Процедура работает с помощью рекурсивного нисходящего обхода. Имеет подпроцедуру UnderTree. Подпроцедура UnderTree - специальная процедура. Создает поддеревья исходя из приоритета математической операции. Имеет подпроцедуру Skob. Подпроцедура Skob - учитывает скобки в математическом выражении. Процедура Calc - вычисляет математическое выражение. Процедура использует рекурсивный нисходящий обход. Процедура Symb - определяет в дереве где переменная или константа, и где знак операции. Эта процедура нужна для вычисления математического выражения. Процедура использует рекурсивный нисходящий обход. Процедура OutTree - выводит дерево на экран. Процедура использует рекурсивный нисходящий обход.
{===== Программный пример 6.17 ====== }
{$M 65500,0,100000}
Program MathExpr; { Эта программа вычисляет }
{математические выражения : *, /, +, -, ^. }
Uses CRT;
Type tr=^rec; {Тип дерево}
rec=record
pole:string; {Информационное поле }
sym:boolean; {Флаг символа }
zn:real; {Значение переменной }
rend:boolean; {Вспомогательный флаг}
l,r:tr; {Указатели на потомка}
end;
Var root,el : tr; {вершина и узлы дерева}
st : string; {вспомогательная переменная}
i,j : byte; { -------"-------}
x,y : integer; { координаты для вывода дерева}
g : byte; {вспомогательная переменная}
yn : char; { -------"-------}
code : integer; { для procedure VAL }
{Процедура Tree }
{Преобразование арифметического выражения в бинарное дерево }
{ Процедура использует рекурсивный нисходящий обход }
Procedure Tree(p:tr);
Procedure undertree(c:char); { создает поддеревья}
Procedure Skob; {процедура для учитывания скобок}
begin i:=i+1;
repeat
If p^.pole[i]='(' then Skob; i:=i+1;
until p^.pole[i]=')';
end; {End of Skob}
begin
for i:=1 to Length(p^.pole) do
begin if p^.pole[i]='('
then begin g:=i; Skob;
if (p^.pole[i+1]<>'+') and (p^.pole[i+1]<>'-')
and (p^.pole[i+1]<>'*') and (p^.pole[i+1]<>'/')
and (p^.pole[g-1]<>'*') and (p^.pole[g-1]<>'/')
and (p^.pole[g-1]<>'-') and (p^.pole[g-1]<>'+')
and (p^.pole[i+1]<>'^') and (p^.pole[g-1]<>'^')
then begin delete(p^.pole,i,1);
delete(p^.pole,1,1); i:=0;
end; end;
if p^.pole[i]=c then
begin New(p^.l); p^.l^.l:=nil;
p^.l^.r:=nil;
p^.l^.pole:=copy(p^.pole,1,i-1);
p^.l^.zn:=0; p^.l^.sym:=false;
New(p^.r); p^.r^.l:=nil;
p^.r^.r:=nil;
p^.r^.pole:=copy(p^.pole,i+1,ord(p^.pole[0]));
p^.r^.zn:=0; p^.r^.sym:=false;
i:=ord(p^.pole[0]); p^.pole:=c;
end; end;
end; {end of UnderTree}
begin
if p<>nil then
{Строятся поддеревья в зависимости от приоритета}
{арифметической операции }
begin UnderTree('+'); UnderTree('-');
UnderTree('*'); Undertree('/');
Undertree('^'); Tree(p^.l); Tree(p^.r);
end;
end; {End of Tree}
{Вычисление значения арифметического выражения}
{Процедура использует рекурсивный нисходящий обход}
Procedure Calc(p:tr);
begin
if p<> nil then begin
if p^.l^.sym and p^.r^.sym then begin
case p^.pole[1] of
'+' : begin p^.zn:=p^.l^.zn+p^.r^.zn;
p^.sym:=true; end;
'-' : begin p^.zn:=p^.l^.zn-p^.r^.zn;
p^.sym:=true; end;
'*' : begin p^.zn:=p^.l^.zn*p^.r^.zn;
p^.sym:=true; end;
'/' : begin p^.zn:=p^.l^.zn/p^.r^.zn;
p^.sym:=true; end;
'^' : begin p^.zn:=EXP(p^.r^.zn*LN(p^.l^.zn));
p^.sym:=true; end;
end; {end of case} end;
Calc(p^.l); Calc(p^.r);
end;
end; {end of calc}
{Процедура определяет где в дереве переменная или значение,}
{и где знак операции. Использует рекурсивный нисходящий обход}
Procedure Symb(p:tr);
begin
if p<> nil then begin
if p^.pole[1] in ['a'..'z']
then begin p^.sym:=true; Write(p^.pole,'= ');
Readln(p^.zn); end;
if p^.pole[1] in ['0'..'9']
then begin p^.sym:=true;
VAL(p^.pole,p^.zn,code); end;
Symb(p^.l); Symb(p^.r); end;
end; {End of Symb}
{ Процедура выводит на экран полученное дерево }
{ Процедура использует рекурсивный нисходящий обход}
Procedure OutTree(pr:tr;f:byte);
begin
y:=y+2;
if pr<>nil then begin
If f=1 then begin x:=x-5; end;
if f=2 then begin x:=x+9; end;
GotoXY(X,Y);
{Если f=0, то выводится корневая вершина}
if f=0 then Writeln('[',pr^.pole,']');
{Если f=1, то - левое поддерево}
if f=1 then Writeln('[',pr^.pole,']/');
{Если f=2, то - правое поддерево}
if f=2 then Writeln('\[',pr^.pole,']');
OutTree(pr^.l,1); OutTree(pr^.r,2);
end; y:=y-2;
end; {End of OutTree}
begin {Главная программа}
repeat
Window(1,1,80,25); x:=22; y:=0;
TextBackGround(7); TextColor(Blue); ClrScr;
{Ввод выражения, которое надо посчитать}
Writeln('Введите ваше выражение:');
GotoXY(40,4); Write('Используйте следующие операции:');
GotoXY(50,5); Write(' + , - , * , / , ^ ');
GotoXY(40,7); Write('Программа применяет деревья для');
GotoXY(40,8); Write('вычисления арифметического вы-');
GotoXY(40,9); Write('ражения.');
GotoXY(1,2); Readln(st);
{root Создается корневая вершина}
New(el); el^.l:=nil; el^.r:=nil; El^.pole:=st;
el^.zn:=0; el^.sym:=false; el^.rend:=false; root:=el;
{end of root}
Tree(root); {Создается дерево}
{Ввод значений переменных}
Writeln('Введите значения:'); Symb(root); Window(30,1,80,25);
TextBackGround(Blue); TextColor(White); ClrScr;
WriteLn('Дерево выглядит так:'); {Вывод дерева на экран}
OutTree(root,0);
repeat
if root^.l^.sym and root^.r^.sym
then begin Calc(root); root^.rend:=true; end
else calc(root);
until root^.rend;
Window(1,23,29,25); TextBackGround(Red);
TextColor(Green); ClrScr;
Writeln('Результат =',root^.zn:2:3); {Вывод результата }
Write('Еще?(y/n)'); readln(yn);
until yn='n';
end.
Результат работы программы представлен на рис 6.34.
Рис. 6.34.
Результат выражения = 14.000
ОПРЕДЕЛЕНИЯ.
Одной из наиболее часто встречающихся задач является поиск необходимых данных. Существуют различные методы, отличающиеся друг от друга временем поиска, сложностью алгоритмов, размерами требуемой памяти. Обычно стремятся всячески сократить время, затрачиваемое на поиск необходимого элемента. Одним из самых быстрых методов является поиск по упорядоченному бинарному дереву. При удачной структуре дерева время поиска элементов не превышает в среднем log N. Но при неудачной структуре время поиска может значительно возрасти, достигая N\2. ( N - число элементов дерева).
Одним из методов, улучшающих время поиска в бинарном дереве является создание сбалансированных деревьев обладающих минимальным временем поиска.
Одно из определений сбалансированности было дано Адельсоном-Вельским и Ландисом:
Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.
Поэтому деревья, удовлетворяющие этому условию, часто называют "АВЛ-деревьями" (по фамилиям их изобретателей).
Операции выполняемые над сбалансированным деревом: поиск, вставка, удаление элемента.
Обратимся к задаче поддержания структуры дерева таким образом, чтобы за время, не превышающее (log N), могла быть выполнена каждая из следующих операций:
С тем чтобы предупредить появление несбалансированного дерева, вводится для каждого узла (вершины) дерева показатель сбалансированности, который не может принимать одно из трех значений, левое - (L), правое - (R), сбалансированное - (B), в соответствии со следующими определениями:
левое - узел левоперевешивающий, если самый длинный путь по ее левому поддереву на единицу больше самого длинного пути по ее правому поддереву;
сбалансированное - узел называется сбалансированный, если равны наиболее длинные пути по обеим ее поддеревьям;
правое - узел правоперевешивающий, если самый длинный путь по ее правому поддереву на единицу больше самого длинного пути по ее левому поддереву;
В сбалансированном дереве каждый узел должен находится в одном из этих трех состояний. Если в дереве существует узел, для которого это условие несправедливо, такое дерево называется несбалансированным.
ОПЕРАЦИЯ ВСТАВКИ ВЕРШИНЫ В СБАЛАНСИРОВАННОЕ ДЕРЕВО.
Предполагается, что новая вершина вставляется на уровне листьев, или терминальных вершин (как левое или правое поддерево). При такой вставке показатели сбалансированности могут изменится только у тех вершин, которые лежат на пути между корнем дерева и вновь вставляемым листом.
Алгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева. Определение типа узла имеет вид:
TYPE ref=^node; { указатель }
node=record
key:integer; { ключ узла }
left,right:ref; { указатели на ветви }
bal:-1..+1; { флаг сбалансированности }
end;
Процесс включения узла состоит из последовательности таких трех этапов:
На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому можно ввести в список параметров переменную h, означающую "высота поддерева увеличилась".
Необходимые операции балансировки полностью заключаются в обмене значениями ссылок. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному "повороту" двух или трех узлов.
ПРИНЦИП РАБОТЫ АЛГОРИТМА.
Рассмотрим бинарное дерево представленное на рис. 6.28 (а), которое состоит только из двух узлов. Включение ключа 7 дает вначале несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5.
Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR); результатом является дерево (e). Теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки: двукратному повороту направо и налево (RL). Окончательное дерево показано на рис.6.35 (а-f).
Рис. 6.35 Последовательное включение узлов в сбалансированное дерево.
АЛГОРИТМ Insert_&_Balanse включения узла в сбалансированное дерево.
Дано: сбалансированное бинарное дерево с корнем ROOT.
Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).
Заданы переменные: ключ - х, информация - INF.
Алгоритм вставляет в дерево новый элемент, сохраняя сбалансированность дерева. Если элемент уже присутствует в дереве, то выводится соответствующее сообщение.
Переменная h используется как флаг, указывающий на то, что было произведено включение элемента. P - текущий указатель при перемещении по дереву, p1 и p2 - вспомогательные указатели. Count - счетчик вставленных элементов.
_Начало . Insert_&_Balanse:
1. Поиск места для вставки:
_Если . x < KEY(p)
_то .: _если . p=nil
_то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 3;
_иначе .: p=LPTR(p) и перейти к п. 1;
повторный вызов Insert_&_Balanse;
_Если . x > KEY(p)
_то .: _если . p=nil
_то .: ВСТАВИТЬ_ЭЛЕМЕНТ и перейти к п. 5;
_иначе .: p=RPTR(p) и перейти к п. 1;
повторный вызов Insert_&_Balanse;
2. Совпадение:
Напечатать "Элемент уже вставлен" и _конец ..
3. Изменение показателей сбалансированности:
(производилась вставка в левое поддерево)
_если . BAL(p)=1 _то .:
BAL(p)=0; h=false; { перевеш.-> сбалансир.}
перейти к п. 7
_если . BAL(p)=0 _то .
BAL(p)=-1; { перевеш.-> критическ.}
перейти к п. 7
4. Балансировка при возрастании левого поддерева:
_если . p=ROOT _то . ROOT=LPTR(p);
{ перенос корневой вершины }
p1=LPTR(); { вводим дополнительный указатель }
_если . BAL(p1)=-1
_то .:
{ однокр. LL-поворот }
LPTR(p)=RPTR(p1); RPTR(p1)=p;
BAL(p)=0; p=p1;
перейти к п. 7
_иначе .:
{ двукратн. LR-поворот }
_если . p1=ROOT
_то . ROOT=RPTR(p1); { перенос корневой вершины }
p2:=RPTR(p1); RPTR(p1)=LPTR(p2);
LPTR(p1)=p1; LPTR(p)=RPTR(p2);
RPTR(p2)=p;
(изменение показателей сбалансированности )
_если . BAL(p2)=-1 _то . BAL(p)=1 _иначе . BAL(p)=0;
_если . BAL(p2)=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0;
p=p2;
BAL(p)=0; h=false;
перейти к п. 7;
5. Изменение показателей сбалансированности:
(производилась вставка в правое поддерево)
_если . BAL(p)=-1 _то .:
BAL(p)=0; h=false; { перевеш.-> сбалансир.}
перейти к п. 7
_если . BAL(p)=0 _то
BAL(p)=1; { перевеш.-> критическ.}
перейти к п. 7
6. Балансировка при возрастании правого поддерева:
_если . p=ROOT _то . ROOT=RPTR(p); { перенос корневой вершины }
p1=RPTR(p); { вводим дополнительный указатель }
_если . BAL(p1)=1
_то .:
{ однокр. RR-поворот }
RPTR(p)=LPTR(p1); LPTR(p1)=p;
BAL(p)=0; p=p1;
перейти к п. 7
_иначе .:
{ двукратн. LR-поворот }
_если . p1=ROOT
_то . ROOT=LPTR(p1); { перенос корневой вершины }
p2:=LPTR(p1); LPTR(p1)=RPTR(p2);
RPTR(p1)=p1; RPTR(p)=LPTR(p2);
LPTR(p2)=p;
(изменение показателей сбалансированности )
_если . BAL(p2)=1 _то . BAL(p)=-1 _иначе . BAL(p)=0;
_если . BAL(p2)=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0;
p=p2;
BAL(p)=0; h=false;
7. Выход.
(Т.к. процедура осуществляет рекурсивный вызов самой
себя в п.3, то здесь производится возврат в место
предыдущего вызова. Последний выход осуществляется
в вызывающую программу).
_Конец . Insert_&_Balanse.
8. Алгоритм процедуры ВСТАВИТЬ_ЭЛЕМЕНТ:
_Начало .:
LPTR(p)=nil; RPT(p)=nil; BAL=0; { обнуление указателей }
DATA=INF; KEY=x; { занесение информации }
h=true; { установка флага вставки элемента }
_если . count=0 { это первый элемент ? }
_то . ROOT=p;
count=count+1;
_Конец ..
Описание работы:
ТЕКСТ ПРОЦЕДУРЫ Insert_&_Balanse.
Процедура выполняет действия по вставка элемента в бинарное дерево с последующей балансировкой в соответствии с приведенным выше алгоритмом.
{=====Программный пример 6.18=========}
Procedure Insert_&_Balanse (x:integer; var p,root:ref;
var h:boolean);
{ x=KEY, p=p, root=ROOT, h=h }
var p1,p2:ref; {h=false}
Begin
if p=nil
then Create(x,p,h) {слова нет в дереве,включить его}
else if x=p^.key then
begin gotoXY(35,3); write('Ключ найден!');
readln; exit; end;
if x < p^.key then
begin Insert_&_Balanse(x,p^.left,root,h);
if h then {выросла левая ветвь}
case p^.bal of
1: begin p^.bal:=0; h:=false; end;
0: p^.bal:=-1;
-1: begin {балансировка}
if p=root then root:=p^.left;
p1:=p^.left; {смена указателя на вершину}
if p1^.bal=-1 then
begin {однократный LL-поворот}
p^.left:=p1^.right;
p1^.right:=p;
p^.bal:=0; p:=p1;
end
else begin {2-кратный LR-поворот}
if p1=root then root:=p1^.right; p2:=p1^.right;
p1^.right:=p2^.left; p2^.left:=p1;
p^.left:=p2^.right; p2^.right:=p;
if p2^.bal=-1 then p^.bal:=+1 else p^.bal:=0;
if p2^.bal=+1 then p1^.bal:=-1 else p1^.bal:=0;
p:=p2;
end; p^.bal:=0; h:=false;
end; end;{case}
end { h then}
else if x > p^.key then begin
Insert_&_Balanse(x,p^.right,root,h);
if h then {выросла правая ветвь}
case p^.bal of
-1: begin p^.bal:=0; h:=false; end;
0: p^.bal:=+1;
1: begin {балансировка}
if p=root then root:=p^.right;
p1:=p^.right; {смена указателя на вершину}
if p1^.BAL=+1 then
begin {однократный RR-поворот}
p^.right:=p1^.left; p1^.left:=p; p^.BAL:=0; p:=p1; end
else begin {2-кратный RL-поворот}
if p1=root then root:=p1^.left;
p2:=p1^.left; p1^.left:=p2^.right; p2^.right:=p1;
p^.right:=p2^.left; p2^.left:=p;
if p2^.BAL=+1 then p^.BAL:=-1 else p^.BAL:=0;
if p2^.BAL=-1 then p1^.BAL:=+1 else p1^.BAL:=0;
p:=p2; end;
p^.BAL:=0; h:=false;
end; { begin 3 }
end;{ case }
end; {then }
End {Search};
ТЕКСТ ПРОЦЕДУРЫ ДОБАВЛЕНИЯ ЭЛЕМЕНТА.
Процедура создает новый элемент, заполняет его информационные поля и обнуляет указатели. При создании первого элемента он автоматически становится корнем дерева.
Procedure Create (x:integer; var p:ref; var h:boolean);
{ создание нового элемента }
Begin
NEW(p); h:=true; with p^ do
begin key:=x; left:=nil; right:=nil; BAL:=0; end;
if count=0 then root:=p; count:=count+1; End;
ОПЕРАЦИЯ УДАЛЕНИЯ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.
Удаление элемента из сбалансированного дерева является еще более сложной операцией чем включение, так как может удаляться не только какой-либо из листьев, но и любой узел (в том числе и корень). Поэтому при удалении необходимо правильно изменить структуру связей между элементами, а затем произвести балансировку полученного дерева.
В результате удаления какого-либо узла могут возникнуть ситуации аналогичные тем, что возникают при добавлении элемента:
В общем процесс удаления элемента состоит из следующих этапов:
На каждом шаге должна передаваться информация о том, уменьшилась ли высота поддерева (из которого произведено удаление). Поэтому мы введем в список параметров переменную h, означающую "высота поддерева уменьшилась".
Простыми случаями являются удаление терминальных узлов и узлов с одним потомком. Если же узел, который надо удалить имеет два поддерева, мы будем заменять его самым правым узлом левого поддерева.
Для балансировки дерева после удаления используем две (симметричные) операции балансировки: Balance_R используется, когда уменьшается высота правого поддерева, а Balance_L - левого поддерева. Процедуры балансировки используют те же способы (LL- LR- RL- и RR-повороты), что и в процедуре вставки элемента.
ПРИМЕР УДАЛЕНИЯ РАЗЛИЧНЫХ УЗЛОВ ИЗ СБАЛАНСИРОВАННОГО ДЕРЕВА.
Узел, который необходимо удалить, обозначен двойной рамкой. Если задано сбалансированное дерево (рис.6.35. a), то последовательное удаление узлов с ключами 4,8,6,5,2,1 и 7 дает деревья (рис.6.35 b...h).
Удаление ключа 4 само по себе просто, т.к. он представляет собой терминальный узел. Однако при этом появляется несбалансированность в узле 3. Его балансировка требует однократного левого поворота налево. Балансировка вновь становится необходимой после удаления узла 6. На этот раз правое поддерево корня балансируется однократным поворотом направо.
Удаление узла 2, хотя само по себе просто, так как он имеет только одного потомка, вызывает сложный двукратный поворот направо и налево.
И четвертый случай: двукратный поворот налево и направо вызывается удалением узла 7, который прежде заменяется самым правым элементом левого поддерева, т.е. узлом с ключом 3.
Рис.6.36 а..h Удаление узлов из сбалансированого дерева.
Удаление элемента из сбалансированного дерева удобнее разбить на 4 отдельных процедуры:
АЛГОРИТМ ПРОЦЕДУРЫ Delete.
Дано: сбалансированное бинарное дерево с корнем ROOT. Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).
Задан: ключ - х, информация - INF.
Алгоритм находит удаляемый элемент и вызывает процедуры удаления и последующей балансировки бинарного дерева. Если элемент отсутствует в дереве, выдается соответствующее сообщение.
Переменная h используется как флаг, указывающий на то, что было произведено удаление элемента. P - текущий указатель при перемещении по дереву, q - вспомогательный указатель.
_Начало . Delete
1. Поиск удаляемого элемента
_Если . x < KEY(p)
_то .: p=LPTR(p);
Вызов Delete;
_если . h=true _то . Вызов Balance_L;
перейти к п.5
_Если . x > KEY(p)
_то .: p=RPTR(p);
Вызов Delete;
_если . h=true _то . вызов Balance_R;
перейти к п.5
_Если . p=nil
_то .: напечатать "Ключа в дереве нет!";
_конец .;
2. Удаление элемента : (если все предыдущие
условия не выполнены, то указатель указывает на
элемент, подлежащий удалению).
Удаляется элемент с одним поддеревом.
q=p; { вводим вспомогательный указатель }
_если . RPTR(q)=nil
_то .: p=LPTR(q);
h=true;
перейти к п.4;
_если . LPTR(q)=nil
_то .: p=RPTR(q);
h=true;
перейти к п.4;
3. Удаление элемента с двумя поддеревьями:
q=LPTR(q);
_если . h=true _то .: вызов Balance_L;
перейти к п.4
4. Напечатать "Узел удален из дерева".
5. Выход.
_Конец . Delete;
ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:
АЛГОРИТМ ПРОЦЕДУРЫ Del.
Дано: указатель - r на элемент дерева с двумя поддеревьями.
Алгоритм производит удаление этого элемента, с сохранением связей с нижележащими элементами, и вызов процедуры балансировки.
Используется вспомогательный указатель q, описанный в процедуре Delete.
_Начало . Del.
1. Поиск последнего элемента в правом поддереве
_Если . RPTR(r) <> nil { элемент не найден }
_то .: r=RPTR(r);
вызов процедуры Del;
_если . h=true _то . вызов процедуры Balance_R;
перейти к п.2;
_иначе .: KEY(q)=KEY(r); r=RPTR(r); h=true;
2. Выход.
_Конец . Del;
ОПИСАНИЕ РАБОТЫ:
АЛГОРИТМ ПРОЦЕДУРЫ Balance_L.
Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.
Задан: указатель p на место удаленного элемента.
Алгоритм производит балансировку бинарного дерева и корректировку показателей сбалансированности.
P1 и P2 - вспомогательные указатели, b1 и b2 - вспомогательные показатели сбалансированности.
_Начало . Balance_L:
1. Корректировка показателей сбалансированности:
_Если . BAL(p)=-1
_то .: BAL(p)=0; { перевеш. -> сбалансир. }
_конец
_Если . BAL(p)=0
_то .: BAL(p)=1; h=false; { сбалансир. -> перевеш. }
_конец
p1=RPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. }
2. Однократный RR-поворот :
_Если . b1 >= 0
_то .:
_Если . p=ROOT _то . ROOT=RPTR(p); _ .{ перенос корня }
RPTR(p)=LPTR(p1); LPTR(P1)=p;
{ корректировка показателей сбалансированности }
_если . b1=0
_то .: BAL(p)=1; BAL(p1)=-1; h=false;
_иначе .: BAL(p)=0; BAL(p1)=0;
p=p1;
_конец
2. Двукратный RL-поворот :
_если . b1 < 0
_если . p1=ROOT _то . ROOT=RPTR(p); { перенос корня }
p2=LPTR(p1); b2=BAL(p2);
LPTR(p1)=RPTR(p2); RPTR(p2)=p1;
RPTR(p)=LPTR(p2); LPTR(p2)=p;
{ корректировка показателей сбалансированности }
_если . b2=1 _то . BAL(p)=-1 _иначе . BAL(p)=0;
_если . b2=-1 _то . BAL(p1)=1 _иначе . BAL(p1)=0;
p=p2; BAL(p2)=0;
_конец
_Конец . Balance_L;
ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:
АЛГОРИТМ ПРОЦЕДУРЫ Balance_R.
Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.
Алгоритм, входные данные и вспомогательные переменные аналогичны алгоритму Balance_L, изменены на противоположные только условия выбора и направления указателей.
_Начало . Balance_R:
1. Корректировка показателей сбалансированности:
_Если . BAL(p)=1
_то .: BAL(p)=0; { перевеш. -> сбалансированная. }
_конец
_Если . BAL(p)=0
_то .: BAL(p)=-1; h=false; { сбалансир. -> перевешивающая. }
_конец
p1=LPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. }
2. Однократный LL-поворот :
_если . b1 <= 0
_то .:
_если . p=ROOT _то . ROOT=LPTR(p); { перенос корня }
LPTR(p)=RPTR(p1); RPTR(P1)=p;
{ корректировка показателей сбалансированности }
_если . b1=0
_то .: BAL(p)=-1; BAL(p1)=1; h=false;
_иначе .: BAL(p)=0; BAL(p1)=0;
p=p1;
_конец
3. Двукратный RL-поворот :
_если . b1 > 0
_если . p1=ROOT _то . ROOT=LPTR(p); { перенос корня }
p2=RPTR(p1); b2=BAL(p2);
RPTR(p1)=LPTR(p2); LPTR(p2)=p1;
LPTR(p)=RPTR(p2); RPTR(p2)=p;
{ корректировка показателей сбалансированности }
_если . b2=-1 _то . BAL(p)=1 _иначе . BAL(p)=0;
_если . b2=1 _то . BAL(p1)=-1 _иначе . BAL(p1)=0;
p=p2; BAL(p2)=0;
_конец
_Конец . Balance_R;
Метод работы аналогичен алгоритму Balance_L.
ТЕКСТЫ ПРОЦЕДУР Delete 1, 0 Del 1, 0Balance_L и Balance_R.
Так как процедуры Del, Balance_L и Balance_R используются только процедурой Delete, то их можно выполнить вложенными в Delete.
{=====Программный пример 6.20 ========}
Procedure Delete (x:integer; var p,root:ref; var h:boolean);
var q:ref; {h:false}
procedure Balance_L ( var p:ref; var h:boolean);
{уменьшается высота левого поддерева}
var p1,p2:ref;
b1,b2:-1..+1;
begin { h-true, левая ветвь стала короче }
case p^.BAL of
-1: p^.BAL:=0;
0: begin p^.BAL:=+1; h:=false; end;
1: begin {балансировка}
p1:=p^.right; b1:=p1^.BAL;
if b1 >= 0 then begin { однократный RR-поворот }
if p=root then root:=p^.right; p^.right:=p1^.left;
p1^.left:=p;
if b1 = 0 then begin
p^.BAL:=+1; p1^.BAL:=-1; h:=false; end
else begin p^.BAL:=0; p1^.BAL:=0; end;
p:=p1;
end
else begin { 2-кратный RL-поворот }
if p1=root then root:=p1^.right; p2:=p1^.left;
b2:=p2^.BAL; p1^.left:=p2^.right; p2^.right:=p1;
p^.right:=p2^.left; p2^.left:=p;
if b2=+1 then p^.BAL:=-1 else p^.BAL:=0;
if b2=-1 then p1^.BAL:=+1 else p1^.BAL:=0;
p:=p2; p2^.BAL:=0; end;
end; { begin 3 }
end; { case }
end; {Balance_L}
procedure Balance_R (var p:ref; var h:boolean);
{ уменьшается высота правого поддерева }
var p1,p2:ref;
b1,b2:-1..+1;
begin { h-true, правая ветвь стала короче }
case p^.BAL of
1: p^.BAL:=0;
0: begin p^.BAL:=-1; h:=false; end;
-1: begin { балансировка }
p1:=p^.left; b1:=p1^.BAL;
if b1 <= 0 then begin { однократный LL-поворот }
if p=root then root:=p^.left;
p^.left:=p1^.right; p1^.right:=p;
if b1 = 0
then begin p^.BAL:=-1; p1^.BAL:=+1; h:=false; end
else begin p^.BAL:=0; p1^.BAL:=0; end;
p:=p1;
end
else begin { 2-кратный LR-поворот }
if p1=root then root:=p1^.left;
p2:=p1^.right; b2:=p2^.BAL;
p1^.right:=p2^.left; p2^.left:=p1;
p^.left:=p2^.right; p2^.right:=p;
if b2=-1 then p^.BAL:=+1 else p^.BAL:=0;
if b2=+1 then p1^.BAL:=-1 else p1^.BAL:=0;
p:=p2; p2^.BAL:=0;
end; end; end;
end; {Balance_R}
Procedure Del (var r:ref; var h:boolean);
begin { h-false }
if r^.right <> nil then
begin Del(r^.right,h);
if h then Balance_R(r,h);
end else begin q^.key:=r^.key; r:=r^.left; _ .h:=true; end;
end;{Del}
Begin {Delete}
if p=nil
then begin TextColor(white); GotoXY(а,b+2);
write ('Ключа в дереве нет'); h:=false; end
else if x < p^.key
then begin Delete(x,p^.left,root,h);
if h then Balance_L(p,h); end
else if x > p^.key then
begin Delete(x,p^.right,root,h);
if h then Balance_R(p,h); end
else begin { удаление p^ }
q:=p; if q^.right=nil
then begin p:=q^.left; h:=true; end
else if q^.left=nil then
begin p:=q^.right; h:=true; end
else begin Del(q^.left,h);
if h then Balance_L(p,h);
end;
GotoXY(а,b);
writeln(' Узел с ключом ',x,' удален из дерева.');
end;
End{Delete};
ПОИСК ЭЛЕМЕНТА.
Поиск элемента в сбалансированном дереве уже применялся в операциях вставки и удаления элементов. Поэтому необходимо отдельно рассмотреть эту операцию.
Пусть дано некоторое бинарное дерево, в котором каждый левый элемент меньше вышележащего, а правый - больше.
Для нахождения элемента с заданным ключом начинаем поиск с корневого элемента, сравнивая его ключ с искомым. Если искомый ключ меньше, то продолжаем поиск по левому поддереву (так как его элемент меньше текущего), а если ключ больше - то по правому (его элемент больше). Сравнивая аналогичным образом искомый ключ с ключом текущего элемента мы будем последовательно спускаться по дереву до тех пор, пока ключи искомого и текущего элемента не совпадут - элемент найден. Если мы дошли до уровня листьев (ниже элементов уже нет), а элемент не найден, значит он отсутствует в дереве.
Этот алгоритм пригоден для поиска в любых бинарных деревьях, но при работе со сбалансированными деревьями время поиска элемента минимально.
АЛГОРИТМ Search.
Дано: ключ - X.
Алгоритм производит рекурсивный обход сбалансированного дерева и находит элемент с заданным ключом, либо сообщает об отсутствии такого элемента.
1. Поиск элемента:
_Если . x < key(p)
_то .: _если . p=nil
_то .: напечатать "Элемент отсутствует" и _конец ..
_иначе .: p=LPTR(p) и вызвать процедуру Search;
_Если . x > key(p)
_то .: _если . p=nil
_то .: напечатать "Элемент отсутствует" и _конец ..
_иначе .: p=RPTR(p) и вызвать процедуру Search;
2. Совпадение:
Напечатать "Элемент найден";
Произвести операции обработки элемента и _конец ..
ТЕКСТ ПРОЦЕДУРЫ Search.
{=====Программный пример 6.21 ===========}
Procedure Search (x:integer; var p:ref);
begin
if x > p^.key then
if p=nil then writeln('Элемент на найден')
else Search(x,p^.right);
if x < p^.key then
if p=nil then writeln('Элемент на найден')
else Search(x,p^.left);
writeln('элемент найден');
{ Здесь - процедура обработки элемента }
end;
Так как операция поиска применяется в процедуре вставки элемента в сбалансированное дерево, то нет особого смысла выделять эту операцию в отдельную процедуру. Проще предусмотреть, что при отсутствии элемента производится его включение, а если элемент уже есть - то производятся необходимые действия над элементом.
На первый взгляд работа со сбалансированными бинарными деревьями требует лишних затрат времени на дополнительные операции по поддержанию необходимой структуры дерева и усложнение алгоритмов.
Но на самом деле затраты на балансировку легко компенсируются минимальным временем поиска элементов при вставке, удалении и обработке элементов, по сравнению с другими методами хранения. В то же время четкая структура расположения элементов не усложняет, а наоборот - упрощает алгоритмы работы с такими деревьями.
ОПИСАНИЕ ПРОГРАММЫ РАБОТЫ СО СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ.
1. Процедура NOTE.
В процессе работы пользователя с программой MAVERIC выводит подсказку в нижней части экрана. Подсказка содержит коды клавиш,определяющих режим работы программы.
2. Процедура CREATE.
Создает новый узел дерева,в том числе и корень; записывает ключ дерева и обнуляет указатели узла на его ветви. Включает счетчик узлов и определяет корень дерева,путем установки на него указателя ROOT. Указатель ROOT устанавливается только в случае,если счетчик узлов дерева равен 0.
3. Процедура SEARCH.
Входным элементом для процедуры SEARCH является определяемый пользователем ключ для поиска или создания нового узла. Новый ключ сравнивается с ключом предыдущего узла.Если узла с таким ключом нет в дереве,то вызывается процедура CREATE.
В зависимости от того, больше или меньше ключ нового узла ключа узла предыдущего выбирается вид включения нового узла в дерево - справа или слева. На каждом этапе работы процедуры проверяется флаг "h" определяющий,увеличилась ли высота поддерева; а также проверяется поле "p^.bal" определяющее способ балансировки.
Процедура SEARCH является рекурсивной процедурой,т.е. она вызывает сама себя.При первом проходе процедура SEARCH обращается к корню дерева,затем проходит по всему дереву,последовательно вызывая ветви корня,затем ветви ветвей и так далее.
В случае,если необходима балансировка,процедура SEARCH производит так называемые "повороты" ветвей дерева,путем переопределения указателей.Если балансировка затрагивает корень дерева, процедура переопределяет корень,меняя указатель ROOT,а затем производит балансировку.
4. Процедура DELETE.
Процедура DELETE удаляет ключ из дерева и,если необходимо,производит балансировку.Входным параметром является определяемый пользователем ключ. Процедура DELETE имеет три одпроцедуры: balance_R,balance_L и Del.Подпроцедуры balance_R и balance_L являются симметричными и выполняют балансировку при уменьшении высоты правого или левого поддеревьев соответственно.
Если узла с заданным пользователем ключом нет в дереве,то выводится соответствующее сообщение.Если данный ключ меньше ключа предыдущего узла,то происходит рекурсивный вызов процедуры Delete и обход дерева по левой ветви.Если возникает необходимость балансировки,то вызывается подпроцедура balance_L.Если заданный пользователем ключ больше ключа предыдущего узла,то производится обход дерева по правой ветви и в случае необходимости балансировки вызывается подпроцедура balance_R.
Если подпроцедуры балансировки затрагивают корень дерева,то меняется указатель на корень дерева - ROOT.Эта операция заложена в обоих подпроцедурах balance_R и balance_L.
При обнаружении узла с заданным пользователем ключом подпроцедура Del производит операцию удаления данного узла.
5. Процедура OUTTREE.
Рекурсивная процедура OutTree выводит изображение дерева на монитор. Входными параметрами является указатель на корень дерева ROOT и переменная F определяющая,является ли текущий узел корнем или правой или левой ветвью.
После каждой операции над деревом процедура OutTree выводит изображение дерева заново,предварительно очистив экран.
6. Основная программа.
Программа Maveric работает в текстовом режиме,для чего в начале инициализируется модуль CRT. Основная программа выводит заставку и ожидает нажатия одной из определенных в программе клавиш. При помощи процедуры Note внизу экрана выводится подсказка со списком определенных клавиш и соответствующих им операций.При нажатии клавиши B вызывается процедура Create,при нажатии клавиши S вызывается процедура Search,при нажатии D - процедура Delete.Программа работает в диалоговом режиме.
Режим работы с пользователем прекращается при нажатии клавиши ESC.
{======Программный пример 6.22 ====== }
{$T-}
Program Maveric;
USES CRT;
label L1,L2,L3,L4;
TYPE ref=^node; { указатель на узел }
node=record
key:integer; { ключ узла }
left,right:ref; { указатели на ветви }
bal:-1..+1; { флаг сбалансированности }
end;
VAR
root, { указатель на корень дерева }
p:ref; { новое дерево }
x:integer; { ключ узла }
h:boolean; { true-высота поддерева увеличилась }
n:char; { клавиша подсказки }
Ta,Tb, { координаты начала вывода дерева }
a,b:integer; { координаты вывода подсказки }
count:byte; { счетчик узлов дерева }
Procedure Note; { процедура вывода подсказки }
Begin
TextBackground (white); GotoXY(5,25); textcolor(black);
write('B-новое дерево S-поиск по ключу ');
write (' D-удаление по ключу Esc-выход');
End;
Procedure Create (x:integer; var p:ref; var h:boolean);
{ создание нового дерева }
Begin
NEW(p); h:=true;
with p^ do
begin key:=x;
left:=nil; right:=nil; bal:=0;
end;
if count=0 then root:=p;
count:=count+1;
End;
Procedure Search(x:integer; var p,root:ref; var h:boolean);
var p1,p2:ref; {h=false}
Begin
if p=nil then Create(x,p,h) {слова нет в дереве,включить его}
else if x < p^.key then
begin Search(x,p^.left,root,h);
if h then {выросла левая ветвь}
case p^.bal of
1: begin p^.bal:=0; h:=false; end;
0: p^.bal:=-1;
-1: begin {балансировка}
if p=root then root:=p^.left;
{смена указателя на вершину}
p1:=p^.left;
if p1^.bal=-1 then
begin {однократный LL-поворот}
p^.left:=p1^.right; p1^.right:=p;
p^.bal:=0; p:=p1;
end else
begin {2-х кратный LR-поворот}
if p1=root then root:=p1^.right;
p2:=p1^.right;
p1^.right:=p2^.left; p2^.left:=p1;
p^.left:=p2^.right; p2^.right:=p;
if p2^.bal=-1 then p^.bal:=+1 else p^.bal:=0;
if p2^.bal=+1 then p1^.bal:=-1 else p1^.bal:=0;
p:=p2;
end; p^.bal:=0; h:=false;
end; end;
end else if x > p^.key then
begin Search(x,p^.right,root,h);
if h then {выросла правая ветвь}
case p^.bal of
-1: begin p^.bal:=0; h:=false; end;
0: p^.bal:=+1;
1: begin {балансировка}
if p=root then root:=p^.right;
{смена указателя на вершину}
p1:=p^.right;
if p1^.bal=+1 then
begin {однократный RR-поворот}
p^.right:=p1^.left; p1^.left:=p;
p^.bal:=0; p:=p1; end
else begin {2-х кратный RL-поворот}
if p1=root then root:=p1^.left;
p2:=p1^.left; p1^.left:=p2^.right; p2^.right:=p1;
p^.right:=p2^.left; p2^.left:=p;
if p2^.bal=+1 then p^.bal:=-1 else p^.bal:=0;
if p2^.bal=-1 then p1^.bal:=+1 else p1^.bal:=0;
p:=p2; end;
p^.bal:=0; h:=false;
end; end; end;
End {Search};
Procedure Delete (x:integer; var p,root:ref; var h:boolean);
var q:ref; {h:false}
procedure balance_L ( var p:ref; var h:boolean);
{уменьшается высота левого поддерева}
var p1,p2:ref;
b1,b2:-1..+1;
begin {h-true,левая ветвь стала короче}
case p^.bal of
-1: p^.bal:=0;
0: begin p^.bal:=+1; h:=false; end;
1: begin {балансировка}
p1:=p^.right; b1:=p1^.bal;
if b1 >= 0 then
begin {однократный RR-поворот}
if p=root then root:=p^.left;
p^.right:=p1^.left; p1^.left:=p;
if b1 = 0 then
begin p^.bal:=+1; p1^.bal:=-1; h:=false;
end else
begin p^.bal:=0; p1^.bal:=0; end;
p:=p1;
end else
begin {2-х кратный RL-поворот}
if p1=root then root:=p1^.left;
p2:=p1^.left; b2:=p2^.bal;
p1^.left:=p2^.right; p2^.right:=p1;
p^.right:=p2^.left; p2^.left:=p;
if b2=+1 then p^.bal:=-1 else p^.bal:=0;
if b2=-1 then p1^.bal:=+1 else p1^.bal:=0;
p:=p2; p2^.bal:=0;
end; end; end;
end; {balance_L}
procedure balance_R (var p:ref; var h:boolean);
{уменьшается высота правого поддерева}
var p1,p2:ref;
b1,b2:-1..+1;
begin {h-true,правая ветвь стала короче}
case p^.bal of
1: p^.bal:=0;
0: begin p^.bal:=-1; h:=false; end;
-1: begin {балансировка}
p1:=p^.left; b1:=p1^.bal;
if b1 <= 0 then
begin {однократный LL-поворот}
if p=root then root:=p^.right;
p^.left:=p1^.right; p1^.right:=p;
if b1 = 0 then
begin p^.bal:=-1; p1^.bal:=+1; h:=false;
end else
begin p^.bal:=0; p1^.bal:=0;
end;
p:=p1;
end else begin {2-х кратный LR-поворот}
if p1=root then root:=p1^.right;
p2:=p1^.right; b2:=p2^.bal;
p1^.right:=p2^.left; p2^.left:=p1;
p^.left:=p2^.right; p2^.right:=p;
if b2=-1 then p^.bal:=+1 else p^.bal:=0;
if b2=+1 then p1^.bal:=-1 else p1^.bal:=0;
p:=p2; p2^.bal:=0;
end; end; end;
end; {balance_R}
Procedure Del (var r:ref; var h:boolean);
begin {h-false}
if r^.right <> nil then
begin Del(r^.right,h); if h then balance_R(r,h);
end else
begin q^.key:=r^.key;
r:=r^.left; h:=true; end;
end;{Del}
Begin {Delete}
if p=nil then
begin TextColor(white); GotoXY(a,b+2);
write ('Ключа в дереве нет'); h:=false;
end else if x < p^.key then
begin Delete(x,p^.left,root,h); if h then balance_L(p,h);
end else if x > p^.key then
begin Delete(x,p^.right,root,h); if h then balance_R(p,h);
end else begin {удаление p^} q:=p;
if q^.right=nil then
begin p:=q^.left; h:=true;
end else
if q^.left=nil then
begin p:=q^.right; h:=true;
end else
begin Del(q^.left,h);
if h then balance_L(p,h);
end;
{dispose(q);}
GotoXY(a,b);
writeln('Узел с ключом ',x,' удален из дерева.');
end;
End{Delete};
Procedure OutTree(pr:ref;f:byte);
Begin
Tb:=Tb+2;
If f=1 then Ta:=Ta-2;
if f=2 then Ta:=Ta+8;
if pr<>nil then begin GotoXY(TA,TB);
case f of
0: Writeln('[',pr^.key,']');
1: Writeln('[',pr^.key,']/');
2: Writeln('\[',pr^.key,']');
end;
OutTree(pr^.left,1); OutTree(pr^.right,2);
end;
Tb:=Tb-2; Ta:=Ta-2;
End; {OutTree}
BEGIN {main program}
L4:
count:=0; a:=25; b:=5;
TextBackground(black); ClrScr;
TextBackground (red); gotoxy(a,b);
textcolor(white); writeln(' WELCOME TO THE LAND ');
gotoxy(a,b+1); WRITE(' OF BALANCED TREES ');
while n <> #27 do
begin note; n:=readkey;
case n of
#66: goto L1; {'B'}
#68: goto L3; {'D'}
#83: goto L2; {'S'}
#98: begin {'b'}
L1: clrscr; TextBackground (green); gotoxy(a,b);
writeln ('Введите ключ для нового дерева');
gotoxy(a+32,b); read(x); Create(x,p,h);
end;
#115: begin {'s'}
L2: ClrScr;
TextBackground (blue); gotoxy(a,b);
TextColor(white);
writeln('Введите ключ для поиска и включения');
gotoxy(a+40,b); read(x);
Search(x,p,root,h); Ta:=26; Tb:=10;
OutTree(root,0); end;
#100: begin {'d'}
L3: ClrScr; TextBackground (yellow);
gotoxy(a,b); TextColor(black);
writeln('Введите ключ для удаления узла');
gotoxy(a+32,b); read(x);
Delete(x,p,root,h);
Ta:=26; Tb:=10; OutTree(root,0);
end; end; end;
Dispose(p); ClrScr; TextBackground (red);
GotoXY(a,b); TextColor(white);
writeln('Are you sure? Yes/No');
GotoXY (a+23,b); n:=readkey;
if (n=#78) or (n=#110) then goto L4;
END. {main program}
| Каталог | Индекс раздела |
| Назад | Оглавление | Вперед |