В заключение данной темы рассмотрим один частный случай ДД – так называемое идеально сбалансированное дерево (ИСД). Как будет отмечено в дальнейшем, эффективное использование деревьев на практике часто требует управления ростом дерева для устранения крайних случаев, когда дерево вырождается в линейный список и тем самым теряет всю свою привлекательность (с вычислительной точки зрения, разумеется).
В этом смысле ИСД полностью оправдывает свое название, поскольку вершины в нем распределяются наиболее равномерно и тем самым ИСД имеет минимально возможную высоту. Более точно, ДД называется идеально сбалансированным, если для каждой вершины число вершин в левом и правом ее поддеревьях отличаются не более чем на единицу. Обратим внимание, что данное условие должно выполняться для всех вершин дерева!
| 
| 
| |||||||||||||||||||||
| Это дерево - ИСД | Это – не ИСД (нарушение условия для корня!) | Это тоже не ИСД (совсем плохо, почти список!) |
ИСД легко строится, если заранее известно количество вершин N в этом дереве. В этом случае ИСД можно построить с помощью следующего рекурсивного алгоритма:
· взять первую по порядку вершину в качестве корневой
· найти количество вершин в левых и правых поддеревьях:
Nl = N div 2;
Nr = N – Nl – 1;
· построить левое поддерево с Nl вершинами точно таким же образом (пока не получим Nl = 0)
· построить правое поддерево с Nr вершинами точно таким же образом (пока не получим Nr = 0)
Естественно, что реализация рекурсивного алгоритма наиболее просто выполняется в виде рекурсивной подпрограммы. При этом между этой процедурой и процедурами обхода есть одно принципиальное различие: процедуры обхода лишь используют существующую структуру дерева, не изменяя ее, и поэтому их формальные параметры являются лишь входными, тогда как процедура построения ИСД должна СОЗДАВАТЬ вершины и каждый раз возвращать в вызвавшую ее подпрограмму адрес очередной созданной вершины. Поэтому формальный параметр ссылочного типа должен быть объявлен как параметр-переменная. Кроме того, второй формальный параметр-значение принимает число вершин в текущем строящемся поддереве.
|
|
procedure AddNodes (var pСurrent: Tp; aN: integer);
var pTemp: Tp;
Nl, Nr: integer;
Begin
if aN = 0 then { вершин для размещения нет }
pCurrent:= nil { формируем пустую ссылку }
Else
Begin
Nl:= aN div 2; {сколько вершин будет слева?}
Nr:= aN - Nl - 1; {сколько вершин будет справа?}
New (pTemp); {создаем корень поддерева}
AddNodes (pTemp^.left, Nl); {уходим на создание левого поддерева}
AddNodes (pTemp^.right, Nr);{уходим на создание правого поддерева}
pCurrent:= pTemp; {возвращаем адрес созданного корня}
End
end;
Запуск процесса построения как обычно выполняется из главной программы с помощью вызова AddNodes(pRoot, N). В этом вызове фактический параметр N обязательно должен иметь конкретное значение, например – заданное пользователем количество вершин в строящемся ИСД. Однако, первый фактический параметр pRoot, являясь выходным, получит свое значение лишь после отработки всех рекурсивных вызовов, при возврате в главную программу.
Для понимания работы приведенной процедуры целесообразно вручную расписать шаги ее работы для простейшего дерева из трех вершин. Пусть элементами дерева являются символы A, B, C. В результате работы мы должны получить: pRoot -> A, A.left -> B, A.right -> C, B.left -> nil, B.right -> nil, C.left -> nil, C.right -> nil.
|
|
Тогда схема построения ИСД будет:
· Главная программа: вызов AddNodes (pRoot, 3)
· П/п 1: Nl = 1, Nr = 1, создание вершины A, вызов AddNodes (A.left, 1)
· П/п 1-2: сохранение в стеке значений Nl = 1, Nr = 1, адреса A
· П/п 1-2: Nl = 0, Nr = 0, создание вершины B, вызов
AddNodes (B.left, 0)
· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса B
· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр B.left = nil
· П/п 1-2: вызов AddNodes (B.right, 0)
· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса B
· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр B.right = nil
· П/п 1-2: pCurrent = адрес B, возврат к 1
· П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A.left=адрес B
· П/п 1: вызов AddNodes (A.right, 1)
· П/п 1-2: сохранение в стеке значений Nl = 1, Nr = 1, адреса A
· П/п 1-2: Nl = 0, Nr = 0, создание вершины C, вызов
AddNodes (C.left, 0)
· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C
· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр C.left = nil
· П/п 1-2: вызов AddNodes (C.right, 0)
· П/п 1-2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C
· П/п 1-2-3: aN = 0, pCurrent = nil, возврат к 1-2
· П/п 1-2: восстановление Nl = 0, Nr = 0, вых. параметр C.right = nil
· П/п 1-2: pCurrent = адрес C, возврат к 1
· П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A.right=адрес C
· П/п 1: pCurrent = адрес A, возврат в главную программу
· Главная программа: установка выходного параметра pRoot = адрес A
Практические здания
Задание 1. Построение и обход идеально сбалансированных двоичных деревьев. Реализовать программу, выполняющую следующий набор операций:
|
|
· построение идеально сбалансированного двоичного дерева с заданным числом вершин
· построчный вывод дерева на основе процедуры обхода в прямом порядке
· построчный вывод дерева на основе процедуры обхода в симметричном порядке
· построчный вывод дерева на основе процедуры обхода в обратно-симметричном порядке
Рекомендации:
· для простоты построения дерева можно информационную часть формировать как случайное целое число в интервале от 0 до 99
· глобальные переменные: указатель на корень дерева и число вершин
· алгоритмы построения ИСД и его обхода оформляются как подпрограммы, вызываемые из главной программы
· все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины
· Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна:
Ø проверить пустоту очередного поддерева
Ø вывести в цикле необходимое число пробелов в соответствии с уровнем вершины
Ø вывести информационную часть текущей вершины
Ø вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1
Ø вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1
Сравнение рассмотренных правил вывода двоичного дерева приводится в следующей таблице
| Исходное дерево | Вывод в прямом порядке | Вывод в симметричном порядке | Вывод в обратно-симметричном порядке | ||||||||||||||||
  10
15 9
13 22 5 17 |
Главная программа реализует следующий набор действий:
· запрос числа вершин в дереве
· запуск рекурсивной подпрограммы построения идеально сбалансированного дерева со следующими фактическими параметрами: указатель на корень дерева (при построении дерева этот параметр является выходным!) и заданное число вершин
· последовательный вызов подпрограмм обхода дерева со следующими фактическими входными параметрами: указатель на корень дерева, ноль в качестве уровня корневой вершины дерева.
Задание 2. Добавить в программу нерекурсивный вариант процедуры обхода дерева в симметричном порядке.
Замена рекурсии циклом основана на использовании вспомогательного стека для хранения последовательности пройденных вершин от корня до текущей вершины и уровня этих вершин в дереве (напомним, что уровень используется только для задания правильного числа отступов при построчном выводе дерева). Исходя из этого, создаваемая подпрограмма должна объявить необходимые локальные типы данных для динамической реализации вспомогательного стека. Каждый элемент стека должен хранить: указатель на пройденную вершину дерева, уровень вершины, указатель на следующий элемент стека. Для реализации стека, как обычно, требуются две ссылочные переменные: указатель на вершину стека и вспомогательный указатель, используемый при добавлении или удалении элементов в стек.
Кодовая часть подпрограммы должна начинаться с инициализации необходимых переменных: текущая вершина дерева – его корень, вспомогательный стек - пустой, начальный уровень равен (-1). После этого запускается основной цикл обработки дерева, включающий выполнение следующих действий:
· циклическое сохранение очередной вершины в стеке (пока не будет достигнута пустая вершина) следующим образом:
Ø увеличение уровня вершины на 1
Ø создание нового элемента стека, заполнение всех его полей и добавление его в стек
Ø переход к левому потомку текущей вершины
· проверка пустоты стека: если стек пуст, то основной цикл следует завершить, а иначе – перейти к обработке вершины
Ø извлечь из стека адрес текущей обрабатываемой вершины и ее уровень
Ø вывести вершину с необходимым числом пробелов
Ø удалить элемент из стека с освобождением памяти
Ø перейти к правому потомку текущей вершины
Для проверки правильности работы подпрограммы сравнить ее результаты с рекурсивным аналогом.
Задание 3. Обработка произвольных двоичных деревьев
Реализовать программу, выполняющую следующий набор операций с двоичными деревьями:
· поиск вершины с заданным значением информационной части
· добавление левого или правого потомка для заданной вершины
· построчный вывод дерева с помощью основных правил обхода
· уничтожение всего дерева
Рекомендации:
· объявить необходимые глобальные переменные: указатель на корень дерева, указатель на родительскую вершину, признак успешности поиска
· объявить и реализовать рекурсивную подпрограмму поиска. В качестве основы можно взять любой из известных вариантов обхода дерева. Основное отличие рекурсивного поиска от рекурсивного обхода состоит в необходимости прекращения обхода дерева в случае совпадения информационной части текущей вершины с заданным значением. Один из способов прекращения обхода основан на использовании булевского признака, который перед запуском обхода устанавливается в false и переключается в true при обнаружении искомой вершины. Для каждой текущей вершины подпрограмма поиска должна выполнять следующие основные действия:
Ø проверить необходимость продолжения поиска
Ø проверить текущую ссылочную переменную на nil
Ø сравнить информационную часть текущей вершины с заданным значением
Ø если эти величины совпадают, то установить признак окончания поиска и установить адрес родительской переменной в адрес текущей вершины
Ø в противном случае продолжить поиск сначала в левом поддереве текущей вершины, вызвав рекурсивно саму себя с адресом левого потомка, а потом – в правом поддереве, вызвав саму себя с адресом правого потомка
Результат поиска можно проверить с помощью глобального признака. В случае успешного поиска становится известен адрес найденной вершины, который можно использовать в дальнейшем для добавления к этой вершине одного из потомков.
· Объявить и реализовать подпрограмму добавления новой вершины в дерево как потомка заданной вершины.
Подпрограмма должна:
Ø проверить пустоту дерева: если указатель корня имеет значение nil, то надо создать корень дерева
o выделить память
o запросить значение информационной части корня
o сформировать пустые ссылочные поля на потомков
Ø если дерево не пустое, то организовать поиск родительской вершины:
o запросить искомое значение информационной части родительской вершины
o установить признак поиска и вызвать подпрограмму поиска
o если поиск удачен, то проверить число потомков у найденной родительской вершины
o если вершина-родитель имеет двух потомков, то добавление невозможно
o если родительская вершина имеет только одного потомка, то сообщить о возможности добавления одного из потомков, выделить память для новой вершины и заполнить все три ее поля, настроить соответствующее ссылочное поле у родительской вершины
o если родительская вершина не имеет ни одного потомка. то запросить тип добавляемой вершины (левый или правый потомок) и выполнить само добавление
· Объявить и реализовать рекурсивную подпрограмму для построчного вывода дерева в обратно-симметричном порядке. Эту подпрограмму без каких-либо изменений можно взять из предыдущей работы.
· Объявить и реализовать подпрограмму для уничтожения всего дерева с освобождением памяти. Основой подпрограммы является рекурсивный обход дерева, причем – по правилу обратного обхода: сначала посещается и удаляется левый потомок текущей вершины, потом посещается и удаляется правый потомок, и лишь затем удаляется сама текущая вершина. Такой обход позволяет не разрывать связи между родительской вершиной и потомками до тех пор, пока не будут удалены оба потомка. Подпрограмма удаления имеет один формальный параметр – адрес текущей вершины. Подпрограмма должна проверить указатель на текущую вершину, и если он не равен nil, то:
Ø вызвать рекурсивно саму себя с адресом левого поддерева
Ø вызвать рекурсивно саму себя с адресом правого поддерева
Ø вывести для контроля сообщение об удаляемой вершине
Ø освободить память с помощью процедуры Dispose и текущего указателя
Главная программа должна:
· создать пустое дерево
· организовать цикл для добавления вершины с вызовом соответствующей подпрограммы и последующим построчным выводом дерева
· предоставить возможность в любой момент вызвать подпрограмму удаления дерева с фактическим параметром, равным адресу корня дерева, что запускает механизм рекурсивного удаления всех вершин, включая и корневую; поскольку после удаления корневой вершины соответствующий указатель становится неопределенным, можно инициировать его пустым значением, что позволит повторно создать дерево с новой корневой вершиной
5.5. Контрольные вопросы по теме
1. В чем состоит основное отличие древовидных структур от списковых?
2. Как рекурсивно определяется дерево?
3. Какие типы вершин существуют в деревьях?
4. Какие можно выделить типы деревьев?
5. Какие деревья называются двоичными?
6. Какие деревья называются упорядоченными?
7. Какие основные понятия связываются с деревьями?
8. Какие основные операции характерны при использовании деревьев?
9. Какую структуру имеют вершины двоичного дерева?
10. Почему для деревьев существует несколько правил обхода вершин?
11. Какие правила обхода вершин дерева являются основными?
12. Как выполняется обход дерева в прямом направлении?
13. Как выполняется обход дерева в симметричном направлении?
14. Как выполняется обход дерева в обратном направлении?
15. Как выполняется обход дерева в обратно-симметричном направлении?
16. Почему рекурсивная реализация правил обхода является наиболее удобной?
17. Что происходит при рекурсивном выполнении обхода дерева?
18. Как программно реализуется обход дерева в прямом направлении?
19. Как программно реализуется обход дерева в симметричном направлении?
20. Как программно реализуется обход дерева в обратном направлении?
21. Какой формальный параметр необходим для рекурсивной реализации правил обхода и как он используется?
22. В чем состоит суть нерекурсивной реализации процедур обхода?
23. Какая вспомогательная структура данных необходима для нерекурсивной реализации обхода дерева и как она используется?
24. Опишите схему процедуры для нерекурсивного обхода дерева.
25. Как выполняется поиск в дереве вершины с заданным ключом?
26. Как правильно выполнить уничтожение всей древовидной структуры?
27. Какое дерево называется идеально сбалансированным?
28. В чем заключается значимость идеально сбалансированных деревьев с точки зрения организации поиска?
29. Опишите алгоритм построения идеально сбалансированного дерева.
30. В чем состоит принципиальное отличие алгоритмов обхода деревьев от алгоритма построения идеально сбалансированного дерева?
31. Почему ссылочный параметр в рекурсивной процедуре построения идеально сбалансированного дерева должен быть параметром-переменной?
32. Какие формальные параметры должна иметь рекурсивная подпрограмма построения идеально сбалансированного дерева и для чего они используются?
33. Приведите программную реализацию процедуры построения идеально сбалансированного дерева.