Структуры и алгоритмы обработки данных

12. Как выполняется обход дерева в прямом направлении?

13. Как выполняется обход дерева в симметричном направлении?

14. Как выполняется обход дерева в обратном направлении?

15. Как выполняется обход дерева в обратно-симметричном направлении?

16. Почему рекурсивная реализация правил обхода является наиболее удобной?

17. Что происходит при рекурсивном выполнении обхода дерева?

18. Как программно реализуется обход дерева в прямом направлении?

19. Как программно реализуется обход дерева в симметричном направлении?

20. Как программно реализуется обход дерева в обратном направлении?

21. Какой формальный параметр необходим для рекурсивной реализации правил обхода и как он используется?

22. В чем состоит суть нерекурсивной реализации процедур обхода?

23. Какая вспомогательная структура данных необходима для нерекурсивной реализации обхода дерева и как она используется?

24. Опишите схему процедуры для нерекурсивного обхода дерева.

25. Как выполняется поиск в дереве вершины с заданным ключом?

26. Как правильно выполнить уничтожение всей древовидной структуры?

27. Какое дерево называется идеально сбалансированным?

28. В чем заключается значимость идеально сбалансированных деревьев с точки зрения организации поиска?

29. Опишите алгоритм построения идеально сбалансированного дерева.

30. В чем состоит принципиальное отличие алгоритмов обхода деревьев от алгоритма построения идеально сбалансированного дерева?

31. Почему ссылочный параметр в рекурсивной процедуре построения идеально сбалансированного дерева должен быть параметром-переменной?

32. Какие формальные параметры должна иметь рекурсивная подпрограмма построения идеально сбалансированного дерева и для чего они используются?

33. Приведите программную реализацию процедуры построения идеально сбалансированного дерева.

Тема 6. Реализация поисковых деревьев

6.1 Двоичные деревья поиска

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

Пример дерева поиска с целыми ключами представлен на следующем рисунке.

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

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

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

Например, если идеально сбалансированное ДП имеет 1000 вершин, то даже в наихудшем случае потребуется не более 10 сравнений (2 в степени 10 есть 1024), а если число вершин 1 миллион, то потребуется не более 20 сравнений.

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

Интересно заметить, что обход ДП в симметричном порядке позволяет получить исходный набор данных в соответствии с заданным упорядочиванием, а обход в обратно-симметричном порядке - в обратном порядке.

Алгоритм поиска в ДП очень прост:

Начиная с корневой вершины для каждого текущего поддерева надо выполнить следующие шаги:

· сравнить ключ вершины с заданным значением x

· если заданное значение меньше ключа вершины, перейти к левому потомку, иначе перейти к правому поддереву.

Поиск прекращается при выполнении одного из двух условий:

· либо если найден искомый элемент

· либо если надо продолжать поиск в пустом поддереве, что является признаком отсутствия искомого элемента

Интересно, что поиск очень легко можно реализовать простым циклом, без использования рекурсии:

pCurrent := pRoot; {начинаем поиск с корня дерева}

Stop := false;

While (pCurrent <> nil) and (not Stop) do

if x < pCurrent ^.inf then pCurrent := pCurrent^.left else

if x > pCurrent ^.inf then pCurrent := pCurrent^.right else Stop := true;

6.2 Добавление вершины в дерево поиска

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

· найдена вершина с заданным значением ключа, и в этом случае просто увеличивается счетчик

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

Само добавление включает следующие шаги:

· выделение памяти для новой вершины

· формирование информационной составляющей

· формирование двух пустых ссылочных полей на будущих потомков

· формирование в родительской вершине левого или правого ссылочного поля - адреса новой вершины

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

Procedure AddNode ( var pCurrent : Tp);

begin

if pCurrent = nil then {место найдено, создать новую вершину}

begin

New ( pCurrent ); {параметр pCurrent определяет адрес новой вершины}

pCurrent^.inf := "необходимое значение";

pCurrent^.left := nil; pCurrent^.right := nil;

"установка значения поля счетчика в 1 ";

end

else {просто продолжаем поиск в левом или правом поддереве}

if x < pCurrent^.inf then AddNode (pCurrent^.left)

else if x > pCurrent^.inf then AddNode (pCurrent^.right)

else "увеличить счетчик"

end;

Запуск процедуры выполняется в главной программе вызовом AddNode(pRoot). Если дерево пустое, т.е. pRoot = nil, то первый вызов процедуры создаст корневую вершину дерева, к которой потом можно аналогичными вызовами добавить любое число вершин.

Рассмотрим нерекурсивный вариант процедуры добавления вершины в ДП. Необходимо объявить две ссылочные переменные для отслеживания адреса текущей вершины и адреса ее родителя:

pCurrent, pParent : Tp;

Удобно отдельно рассмотреть случай пустого дерева и дерева хотя бы с одной корневой вершиной:

if pRoot = nil then

begin

New (pRoot); pRoot^.left := nil; pRoot^.right := nil;

"заполнение остальных полей";

end

else

begin

pCurrent := pRoot; {начинаем поиск с корня дерева}

while (pCurrent <> nil ) do

begin

pParent := pCurrent; {запоминаем адрес родительской вершины}

if ( x < pCurrent^.inf) then pCurrent := pCurrent^.left

else if ( x > pCurrent^.inf) then pCurrent := pCurrent^.right

else begin {вершина найдена, добавлять не надо, закончить цикл}

pCurrent := nil;

"увеличить счетчик";

end;

end;

if ( x < pParent^.inf) then

begin {добавляем новую вершину слева от родителя}

New (pCurrent);

"заполнить поля новой вершины";

pParent^.left := pCurrent;

end

else

if ( x > pParent^.inf) then

begin {добавляем новую вершину справа от родителя}

New (pCurrent);

"заполнить поля новой вершины";

pParent^.right := pCurrent;

end

end;

6.3 Удаление вершины из дерева поиска

Теперь рассмотрим удаление вершины из ДП. По сравнению с добавлением удаление реализуется более сложным алгоритмом, поскольку добавляемая вершина всегда является терминальной, а удаляться может ЛЮБАЯ, в том числе и нетерминальная. При этом может возникать несколько различных ситуаций.

Рассмотрим фрагмент ДП с целыми ключами.

Ситуация 1. Удаляемая вершина не имеет ни одного потомка, т.е. является терминальной. Удаление реализуется очень легко обнулением соответствующего указателя у родителя. Например, для удаления вершины с ключом 23 достаточно установить 25.left = nil.

Ситуация 2. Удаляемая вершина имеет только одного потомка. В этом случае удаляемая вершина вместе со своим потомком и родителем образуют фрагмент линейного списка. Удаление реализуется простым изменением указателя у родительского элемента. Например, для удаления вершины с ключом 20 достаточно установить 30.left = 20.right = 25

Ситуация 3. Пусть удаляемая вершина имеет двух потомков. Этот случай наиболее сложен, поскольку нельзя просто в родительской вершине изменить соответствующее ссылочное поле на адрес одного из потомков удаляемой вершины. Это может нарушить структуру дерева поиска. Например, замена вершины 30 на одного из ее непосредственных потомков 20 или 40 сразу нарушает структуру дерева поиска.

Существует специальное правило для определения вершины, которая должна заменить удаляемую. Это правило состоит из двух взаимоисключающих действий:

· либо войти в левое поддерево удаляемой вершины и в этом поддереве спустится как можно глубже, придерживаясь только правых потомков; это позволяет найти в дереве ближайшую меньшую вершину (например, для вершины 30 это будет вершина 25)

· либо войти в правое поддерево удаляемой вершины и спустится в нем как можно глубже придерживаясь только левых потомков; это позволяет найти ближайшую бОльшую вершину (например, для той же вершины 30 это будет вершина 33).

Перейдем к программной реализации процедуры удаления. Поскольку при удалении могут изменяться связи между внутренними вершинами дерева, удобно (но, конечно же, не обязательно) использовать рекурсивную реализацию. Основная процедура DeleteNode рекурсивно вызывает сама себя для поиска удаляемой вершины. После нахождения удаляемой вершины процедура DeleteNode определяет число ее потомков. Если потомков не более одного, выполняется само удаление. Если потомков два, то вызывается вспомогательная рекурсивная процедура Changer для поиска вершины-заменителя.

Procedure DeleteNode ( var pCurrent : Tp);

Var pTemp : Tp;

Procedure Changer ( var p : Tp);

begin

{реализация рассматривается ниже}

end;

begin

if pCurrent = nil then "удаляемой вершины нет, ничего не делаем"

else

if x < pCcurrent^.inf then DeleteNode ( pCcurrent^.left)

else

if x > pCurrent^.inf then DeleteNode ( pCurrent^.right)

else {удаляемая вершина найдена}

begin

pTemp := pCurrent;

if pTemp^.right = nil then pCurrent := pTemp^.left

else

if pTemp^.left = nil then pCurrent := pTemp^.right

else {два потомка, ищем заменитель}

Changer ( pCurrent^.left); { а можно и pCurrent^.right }

Dispose ( pTemp);

end;

end;

Схема процедуры Changer:

begin

if p^.right <> nil then Changer ( p^.right)

else {правое поддерево пустое, заменитель найден, делаем обмен}

begin

pTemp^.inf := p^.inf; {заменяем информац. часть удаляемой вершины}

pTemp := p; {pTemp теперь определяет вершину-заменитель}

p := p^.left; {выходной параметр адресует левого потомка заменителя}

end;

end;

Дополнительный комментарий к процедурам. Подпрограмма Changer в качестве входного значения получает адрес левого (или правого) потомка удаляемой вершины и рекурсивно находит вершину-заменитель. После этого информационная часть удаляемой вершины заменяется содержимым вершины-заменителя, т.е. фактического удаления вершины не происходит. Это позволяет сохранить неизменными обе связи этой вершины с ее потомками. Удаление реализуется относительно вершины-заменителя, для чего ссылка pTemp после обмена устанавливается в адрес этой вершины. Кроме того, в самом конце процедуры Changer устанавливается новое значение выходного параметра p: оно равно адресу левого потомка вершины-заменителя. Это необходимо для правильного изменения адресной части вершины-родителя для вершины-заменителя. Само изменение происходит при отработке механизма возвратов из рекурсивных вызовов процедуры Changer. Когда все эти возвраты отработают, происходит возврат в основную процедуру DeleteNode, которая освобождает память, занимаемую вершиной-заменителем. Отметим, что приведенная выше реализация процедуры Changer ориентирована на поиск в левом поддереве удаляемой вершины и требует симметричного изменения для поиска заменителя в правом поддереве.

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

6.4 Практические задания

Задание 1. Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска:

поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа

добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений

построчный вывод дерева в наглядном виде с помощью обратно-симметричного обхода

вывод всех вершин в одну строку по порядку следования ключей с указанием для каждой вершины значения ее счетчика появлений

удаление вершины с заданным значением ключа

Рекомендации:

Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением. При совпадении ключей поиска заканчивается с выводом значения счетчика числа появлений данного ключа. При несовпадении поиск продолжается в левом или правом поддереве текущей вершины

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

Объявить и реализовать не-рекурсивный вариант подпрограммы добавления новой вершины в дерево. Необходимы две ссылочные переменные - адрес текущей вершины и адрес ее родителя. Сначала в цикле ищется подходящее место за счет сравнения ключей и перехода влево или вправо. Поиск заканчивается либо по пустому значению текущего адреса, либо в случае совпадения ключей (здесь просто увеличивается счетчик числа появлений). После окончания поиска либо создается корневая вершина, либо добавляется новая вершина как левый или правый потомок родительской вершины.

Объявить и реализовать рекурсивную подпрограмму для построчного вывода дерева в обратно-симметричном порядке. Эту подпрограмму без каких-либо изменений можно взять из предыдущей работы.

Объявить и реализовать рекурсивную подпрограмму для вывода всех вершин в одну строку в соответствии с возрастанием их ключей. Основа - обход в симметричном порядке. Дополнительно рядом со значением ключа в скобках должно выводится значение счетчика повторений данного ключа. Например:

5(1) 11(2) 19(5) 33(1) 34(4) . . . . .

· Объявить и реализовать подпрограмму удаления вершины: запрашивается ключ вершины, организуется ее поиск, при отсутствии вершины выводится сообщение, при нахождении вершины проверяется число ее потомков и при необходимости выполняется поиск вершины-заменителя

Главная программа должна предоставлять следующие возможности:

· создание дерева с заданным числом вершин со случайными ключами

· добавление в дерево одной вершины с заданным пользователем значением ключа

· поиск в дереве вершины с заданным ключом

· построчный вывод дерева в наглядном виде

· вывод всех вершин в порядке возрастания их ключей

· удаление вершины с заданным ключом

Задание 2. Построение таблицы символических имен с помощью дерева поиска. Постановка задачи формулируется следующим образом.

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

Необходимо реализовать программу, выполняющую следующие действия:

· запрос имени исходного файла с текстом анализируемой программы

· чтение очередной строки и выделение из нее всех символических имен (будем считать, что имя - любая непрерывная последовательность букв и цифр, начинающаяся с буквы и не превышающая по длине 255 символов)

· запоминание очередного имени в дереве поиска вместе с номером строки исходного текста, где это имя найдено; поскольку одно и то же имя в тексте может встречаться многократно в разных строках, приходится с каждым именем-вершиной связывать вспомогательный линейный список номеров строк

· вывод построенной таблицы имен по алфавиту с помощью процедуры обхода дерева в симметричном порядке

· построчный вывод построенного дерева в наглядном представлении с помощью процедуры обхода дерева в обратно-симметричном порядке

Для упрощения программной реализации будем считать, что обрабатываемая программа удовлетворяет следующим непринципиальным условиям:

· в именах используются только строчные (малые) буквы

· отсутствуют комментарии

· отсутствуют текстовые константы, задаваемые с помощью кавычек `'

Например, пусть исходная программа имеет следующий вид:

program test;

var x, y : integer;

str : string;

begin

x := 1;

y := x + 2;

write(x, y);

end.

Тогда для нее должна быть построена следующая таблица имен и дерево поиска:



Рекомендации:

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

2. Объявить необходимые глобальные переменные, такие как номер обрабатываемой строки исходного текста и ее длина, номер обрабатываемого символа в строке (счетчик символов), сама текущая строка, текущее формируемое имя, имя исходного файла, файловая переменная, указатель на корень дерева

3. Объявить и реализовать рекурсивную подпрограмму добавления вершины в дерево поиска. За основу можно взять рассмотренную в предыдущей работе процедуру добавления, внеся в нее следующие небольшие дополнения:

при вставке новой вершины создать первый (пока единственный!) узел вспомогательного линейного списка, заполнить его поля и поля созданной вершины дерева необходимыми значениями

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

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

5. Объявить и реализовать рекурсивную подпрограмму для построчного вывода дерева в обратно-симметричном порядке. Эту подпрограмму без каких-либо изменений можно взять из предыдущей работы.

6. Реализовать главную программу, выполняющую основную работу по выделению имен из строк обрабатываемого текста. Формируемое имя объявляется как String, но обрабатывается как массив символов. Основной механизм формирования имени - посимвольная обработка текущей строки. Как только в строке после не-буквенных символов распознается буква, начинается выделение всех последующих буквенно-цифровых символов и формирование очередного имени. Обрабатываемая строка (тип String) рассматривается как массив символов. Удобно перед обработкой строки добавить в ее конце символ пробела. Номер текущего обрабатываемого символа задается переменной-счетчиком. Для отслеживания символов в формируемом имени также необходима переменная-счетчик.

Алгоритм работы главной программы:

· инициализация обработки исходного файла (запрос имени файла, открытие для чтения)

· цикл обработки строк исходного файла:

ь чтение очередной строки и определение ее длины

ь добавление в конец строки дополнительного символа пробела

ь инициализация счетчика символов

ь организация циклической обработки символов строки по следующему алгоритму:

a. если очередной символ есть буква, то:

Ш запомнить символ как первую букву имени

Ш организовать цикл просмотра следующих символов в строке, пока они являются буквами или цифрами, с добавлением этих символов к формируемому имени

Ш после окончания цикла установить длину сформированного имени (можно использовать нулевой элемент массива символов)

Ш вызвать подпрограмму для поиска сформированного имени в дереве

b. увеличить значение счетчика символов для перехода к анализу следующего символа

· вывод построенной таблицы в алфавитном порядке

· построчный вывод дерева поиска

Контрольные вопросы по теме

1. Какое дерево называется деревом поиска?

2. В чем состоит практическая важность использования деревьев поиска?

3. Какие преимущества имеет использование деревьев поиска для хранения упорядоченных данных по сравнению с массивами и списками?

4. Почему наивысшая эффективность поиска достигается у идеально сбалансированных деревьев?

5. Как находится максимально возможное число шагов при поиске в идеально сбалансированном дереве?

6. Приведите алгоритм поиска в дереве поиска.

7. Как программно реализуется поиск в дереве поиска?

8. Как выполняется добавление новой вершины в дерево поиска?

9. В чем смысл рекурсивной реализации алгоритма добавления вершины в дерево поиска?

10. Какой формальный параметр имеет рекурсивная процедура добавления вершины в дерево поиска и как он используется?

11. Приведите программную реализацию рекурсивной процедуры добавления вершины в дерево поиска.

12. Какие ссылочные переменные необходимы для нерекурсивной реализации процедуры добавления вершины в дерево поиска?

13. Как программно реализуется добавление нерекурсивная процедура добавления вершины в дерево поиска?

14. Какие ситуации могут возникать при удалении вершины из дерева поиска?

15. Что необходимо выполнить при удалении из дерева поиска вершины, имеющей двух потомков?

16. Какие правила существуют для определения вершины-заменителя при удалении из дерева поиска?

17. Опишите алгоритм удаления вершины из дерева поиска.

18. Приведите программную реализацию алгоритма удаления вершины из дерева поиска.

Тема 7. Дополнительные вопросы обработки деревьев. Графы

7.1 Проблемы использования деревьев поиска

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

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

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

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

Дерево поиска называется АВЛ-сбалансированным, если для каждой вершины справедливо требование: высоты левого и правого поддеревьев отличаются не больше чем на единицу.

Очевидно, что любое идеально сбалансированное дерево является также и АВЛ-сбалансированным, но не наоборот.

Для реализации алгоритмов АВЛ-балансировки в каждой вершине дерева удобно хранить так называемый коэффициент балансировки (КБ) как разность высот правого и левого поддеревьев. Для АВЛ-деревьев у всех вершин значение КБ равно -1, 0 или +1.



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

Type Tp = ^TNode;

TNode = record

Inf : <описание>;

Left, right : Tp;

Balance : shortInt;

end;

Алгоритм АВЛ-балансировки при добавлении вершины.

· выполняется поиск в дереве места для новой добавочной вершины, при этом для каждой вершины высчитывается коэффициент балансировки

· если необходимо, то выполняется добавление самой вершины с заполнением всех полей, в том числе и КБ =0 (т.к. потомков у вновь созданной вершины пока нет)

· изменяется на 1 коэффициент балансировки у родителя добавленной вершины: КБ = КБ + 1 если добавлен правый потомок, иначе КБ = КБ - 1

· проверяем новое значение КБ у родительской вершины: если он имеет допустимое значение, то переходим еще на уровень выше для изменения и анализа КБ у деда новой вершины и т.д - до корневой вершины (иногда условие балансировки может нарушиться только для корневой вершины, поэтому приходится проверять все вершины на пути от вновь добавленной до корневой)

· если у какой либо вершины нарушается условие балансировки, запускается специальный алгоритм перестановки вершин, который восстанавливает АВЛ-балансировку дерева и в то же время сохраняет упорядоченную структуру дерева поиска

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

Данная ситуация является более простой и определяется следующими условиями:

· вершина с нарушенным условием балансировки деформирована влево, КБ(30) = -2

· ее левый потомок также перевешивает в левую сторону, КБ(15) = -1

Для исправления этой ситуации выполняется однократный поворот вправо:

· вершина 15 заменяет вершину 30

· левое поддерево вершины 15 не изменяется (15 - 10 - 5)

· правое поддерево вершины 15 образуется корневой вершиной 30

· у вершины 30 правое поддерево не изменяется (30 - 40)

· левое поддерево вершины 30 образуется бывшим правым потомком вершины 15, т.е. 20

Аналогично выполняется однократный поворот влево, если вершина с нарушенным условием балансировки перевешивает вправо (КБ = 2), а ее правый потомок тоже перевешивает вправо (КБ = 1).

Более сложные случаи возникают при несогласованном перевешивании корневой вершины и ее потомков (коэффициенты балансировки имеют разные знаки). Например, рассмотрим случай, когда корневая вершина поддерева с нарушенным условием перевешивает влево (КБ = -2), но ее левый потомок перевешивает вправо (КБ = 1).

Двукратный поворот включает в себя:

· вершина 30 заменяется вершиной 20, т.е. правым потомком левого потомка

· левый потомок вершины 20 (вершина 17) становится правым потомком вершины 15

· левое поддерево с корнем 15 без изменений остается левым поддеревом вершины 20

· правое поддерево вершины 20 начинается с вершины 30

· правое поддерево вершины 30 не меняется (30 - 40 - 50)

· левое поддерево вершины 30 образуется правым поддеревом вершины 20 (25-23)

Удаление вершин из АВЛ-дерева выполняется аналогично:

· ищется удаляемая вершина

· если требуется - определяется вершина-заменитель и выполняется обмен

· после удаления вершины пересчитываются КБ и при необходимости производится балансировка точно по таким же правилам

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

Практика использования АВЛ-деревьев показала, что балансировка требуется примерно в половине случаев вставки и удаления вершин.

Общий вывод: учитывая достаточно высокую трудоемкость выполнения балансировки, АВЛ-деревья следует использовать тогда, когда вставка и удаление выполняются значительно реже, чем поиск.

7.2 Двоичные деревья с дополнительными указателями

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

В таком дереве каждая вершина имеет дополнительное поле - указатель на своего родителя. Описание соответствующей структуры данных:

Type Tp = ^TNode;

TNode = record

Inf : <описание>;

Left, right, parent : Tp;

end;

Преимуществом такого дерева является простота реализации прохода по дереву как вниз, так и вверх, что напоминает двунаправленный список.

Недостатками являются:

· Увеличение затрат памяти на поддержку в каждой вершине дополнительного указателя (4 байта на вершину), т.е. в каждой вершине 12 байт занимает служебная информация, что при большом числе вершин (сотни тысяч) может стать весьма ощутимым

· Увеличивается число операций при добавлении и удалении вершин за счет поддержки дополнительных ссылочных полей

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

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

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

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

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

Type Tp = ^ TNode;

TNode = record

Inf : <описание>;

NextParent, NextChild : Tp;

end;

В списках потомков ссылочное поле NextParent в простейшем случае просто не используется (устанавливается в nil). Как вариант, можно в этом поле хранить указатель на одноименную вершину в родительском списке.

Схематично рассмотрим реализацию основных операций с подобным списковым представлением недвоичных деревьев.

1. Вывод списка родителей с соответствующими списками потомков реализуется двойным циклом: внешний цикл идет по списку родителей, а внутренний позволяет для каждого родителя вывести список его потомков

PCurrentParent := pRoot;

While pCurrentParent <> nil do

begin

"обработка вершины pCurrentParent^";

pCurrentChild := pCurrentParent^.NextChild;

while pCurrentChild <> nil do

begin

"обработка вершины pCurrentChild^";

pCurrentChild := pCurrentChild^.NextChild;

end;

pCurrentParent := pCurrentParent^.NextParent;

end;

2. Добавление вершины X как потомка вершины Y:

· "поиск вершины Y обходом всех вершин";

· if "вершина Y найдена в списке родителей" then "добавляем X в список потомков вершины Y";

· if "вершина Y найдена в списке потомков" then

ь "добавляем Y в список родителей";

ь "создаем у вершины Y список потомков с вершиной X";

3. Удаление вершины X, если она не корневая для всего дерева:

· "поиск вершины X обходом всех вершин";

· if "вершина X найдена в списке родителей" then

ь "просмотром всех списков найти родителя вершины X";

ь "удалить X из списка потомков";

ь "к родителю X добавить список всех потомков X";

· if "вершина X есть только в списке потомков" then

ь "удалить X из списка потомков";

ь if "список потомков пуст, то удалить родителя из списка родителей";

7.4 Представление графов

Граф - это множество однотипных объектов (вершин), некоторые из которых связаны друг с другом какими-либо связями (ребрами). Одна связь всегда соединяет только две вершины (иногда - вершину саму с собой). Основные разновидности графов:

· неориентированные (обычные), в которых важен только сам факт связи двух вершин

· ориентированные (орграфы), для которых важным является еще и направление связи вершин

· взвешенные, в которых важной информацией является еще и степень (величина, вес) связи вершин

Примеры графов разных типов:

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

Для рассмотренных выше примеров матрицы смежности будут следующими:



Недостатки данного способа:

· заранее надо знать хотя бы ориентировочное число вершин в графе

· для графов с большим числом вершин матрица становится слишком большой (например 1000*1000 = 1 миллион чисел)

· при малом числе связующих ребер матрица заполнена в основном нулями

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

Описание подобной сложной списковой структуры выполняется обычным образом.

Операции добавления и удаления по сравнению с деревьями имеют следующие варианты:

· добавление новой связи (ребра) между заданной парой существующих вершин

· добавление новой вершины вместе со всеми необходимыми связями

· удаление связи (ребра) между двумя вершинами

· удаление вершины вместе со всеми ее связями

Добавление нового ребра включает в себя (на примере обычного графа):

· получение имен связываемых вершин

· поиск в основном списке первой связываемой вершины

· поиск в списке смежных ей вершин второй связываемой вершины и либо вывод сообщения об ошибке, либо добавление в этот список нового элемента с именем второй вершины

· поиск в основном списке второй связываемой вершины

· поиск в списке смежных ей вершин первой связываемой вершины и либо вывод сообщения об ошибке, либо добавление в этот список нового элемента с именем первой вершины

Добавление новой вершины включает в себя:

· запрос имени новой вершины вместе с именами всех связываемых с ней вершин

· поиск в основном списке имени новой вершины и в случае отсутствия ее -добавление в основной список

· формирование списка вершин, смежных вновь добавленной

· поиск в основном списке всех смежных вершин и добавление в их вспомогательные списки нового элемента с именем новой вершины

Удаление ребра производится следующим образом:

· запрос имен двух вершин, между которыми разрывается связь

· поиск в основном списке каждой из этих вершин

· поиск в каждом из двух вспомогательных списков имени соседней вершины и удаление соответствующего элемента

Удаление вершины производится следующим образом:

· запрос имени удаляемой вершины

· поиск ее в основном списке

· просмотр вспомогательного списка удаляемой вершины, для каждого элемента которого:

o поиск смежной вершины в основном списке и удаление из ее вспомогательного списка элемента, соответствующего удаляемой вершине

o удаление самого элемента из вспомогательного списка

· удаление вершины из основного списка

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

Поиск в глубину использует две структуры - стек для запоминания еще не обработанных вершин и список для запоминания уже обработанных. Поиск выполняется следующим образом:

· задать стартовую вершину (аналог корневой вершины при обходе дерева)

· обработать стартовую вершину и включить ее во вспомогательный список обработанных вершин

· включить в стек все вершины, смежные со стартовой

· организовать цикл по условию опустошения стека и внутри цикла выполнить:

o извлечь из стека очередную вершину

o проверить по вспомогательному списку обработанность этой вершины

o если вершина уже обработана, то извлечь из стека следующую вершину

o если вершина еще не обработана, то обработать ее и поместить в список обработанных вершин

o просмотреть весь список смежных с нею вершин и поместить в стек все еще не обработанные вершины

Например, для рассмотренного выше обычного графа получим:

· пусть стартовая вершина - B

· включаем B в список обработанных вершин: список = (В)

· помещаем в стек смежные с В вершины, т.е. A и E: стек = (А, Е)

· извлекаем из стека вершину E: стек = (А)

· т.к. E нет в списке обработанных вершин, то обрабатываем ее и помещаем в список: список = (В, Е)

· смежные с E вершины - это A и B, но B уже обработана, поэтому помещаем в стек только вершину А: стек = (А, А)

· извлекаем из стека вершину А: стек = (А)

· т.к. А нет в списке обработанных вершин, то помещаем ее туда: список = (В, Е, А)

· смежные с А вершины - это B, C, D, E, из которых B и E уже обработаны, поэтому помещаем в стек C и D: стек = (A, C, D)

· извлекаем из стека вершину D: стек = (A, C)

· т.к. D не обработана, то помещаем ее в список: список = (B, E, A, D)

· смежные с D вершины - это А и С, из которых А уже обработана, поэтому помещаем в стек вершину С: стек = (А, С, С)

· извлекаем из стека вершину С: стек = (А, С)

· т.к. С не обработана, помещаем ее в список: список = (B, E, A, D, C)

· смежные с С вершины - это A и D, но они обе уже обработаны, поэтому в стек ничего не заносим

· извлекаем из стека С, но она уже обработана

· извлекаем из стека А, но она тоже уже обработана

· т.к. стек стал пустым, то завершаем обход с результатом (B, E, A, D, C)

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

· задать стартовую вершину (аналог корневой вершины при обходе дерева)

· обработать стартовую вершину и включить ее во вспомогательный список обработанных вершин

· включить в очередь все вершины, смежные со стартовой

· организовать цикл по условию опустошения очереди и внутри цикла выполнить:

o извлечь из очереди очередную вершину

o проверить по вспомогательному списку обработанность этой вершины

o если вершина уже обработана, то извлечь из очереди следующую вершину

o если вершина еще не обработана, то обработать ее и поместить в список обработанных вершин

o просмотреть весь список смежных с нею вершин и поместить в очередь все еще не обработанные вершины

Тот же что и раньше пример даст следующий результат:

· пусть стартовая вершина - B

· включаем B в список обработанных вершин: список = (В)

· помещаем в очередь смежные с В вершины, т.е. A и E: очередь = (А, Е)

· извлекаем из очереди вершину А: очередь = (Е)

· т.к. она не обработана, добавляем ее в список: список = (В, А)

· смежные с А вершины - это B, C, D и E, помещаем в очередь вершины C, D и E: очередь = (E, C, D, E)

· извлекаем из очереди вершину Е: очередь = (C, D, E)

· т.к. Е не обработана, помещаем ее в список: список = (B, A, E), т.е. в первую очередь обработаны обе смежные с В вершины

· смежные с Е вершины - это А и В, но обе они уже обработаны, поэтому очередь новыми вершинами не пополняется

· извлекаем из очереди вершину С: очередь = (D, E)

· т.к. С не обработана, то помещаем ее в список: список = (B, A, E, С)

· смежные с С вершины - это А и D, помещаем в очередь только D: очередь = (D, E, D)

· извлекаем из очереди вершину D: очередь = (E, D)

· т.к. D не обработана, помещаем ее в список: список = (B, A, E, С, D)

· смежные с D вершины - это А и С, но обе они обработаны, поэтому очередь не пополняется

· извлекаем из очереди вершину Е, но она уже обработана: очередь = (D)

· извлекаем из очереди вершину D, но она уже обработана и т.к. очередь становится пустой, то поиск заканчивается с результатом (B, A, E, С, D), что отличается от поиска в глубину.

В заключение отметим несколько наиболее часто встречающихся задач на графах:

· найти путь наименьшей (наибольшей) длины между двумя заданными вершинами

· выделить из графа дерево, имеющее наименьший суммарный вес ребер (кратчайшее покрывающее дерево)

· присвоить каждой вершине графа цвет таким образом, чтобы не было ни одной пары смежных вершин, имеющих одинаковый цвет, и при этом число используемых цветов было бы минимальным (задача раскраски графа)

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

7.5 Практические задания

Задание 1. Реализовать основные операции с недвоичными деревьями, представленными с помощью списка родителей и потомков. Будем считать, что начальное дерево содержит единственную корневую вершину. Необходимо реализовать следующие операции:

· добавление новой вершины как потомка заданной вершины

· удаление заданной вершины

· вывод всех вершин с указанием родительских связей

· поиск заданной вершины

Требования к подпрограммам и главной программе - стандартные.

Задание 2. Реализовать основные операции с простыми графами с использованием матричного и спискового представлений:

· формирование матрицы смежности

· преобразование матрицы смежности в список смежности

· формирование списка смежности

· преобразование списка смежности в матрицу смежности

· добавление нового ребра

· удаление заданного ребра

· добавление новой вершины

· удаление заданной вершины

· обход графа в глубину

· обход графа в ширину

Требования к подпрограммам и главной программе - стандартные.

Контрольные вопросы по теме

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. Какие шаги включает в себя алгоритм поиска в ширину?

Раздел 2. Алгоритмы сортировки и поиска

Тема 1. Классификация методов. Простейшие методы сортировки

1.1 Задача оценки и выбора алгоритмов

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

· точность решения задачи

· затраты машинного времени

· затраты оперативной памяти

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

· минимально возможное число повторов элементарных операций в наилучшем случае

· среднее число повторов

· максимальное число повторов для наихудшего случая

Например, в задаче поиска в неупорядоченном массиве или списке из n элементов базовой операцией является сравнение заданного значения с ключом элемента массива. Тогда минимальное число сравнений равно 1 (совпадение произошло на первом элементе массива), максимальное равно n (просмотрен весь массив), а среднее - около n/2.

В отличие от этого, двоичный поиск в упорядоченном массиве или в "хорошем" двоичном дереве поиска дает другие оценки: минимум - 1, максимум - log 2 n, среднее - 0,5* (log 2 n).

Получение подобных оценок часто является сложной математической задачей. Наиболее полный анализ методов получения этих оценок для всех основных алгоритмов приводится в фундаментальной многотомной работе Дональда Кнута [1, 2].

В идеале каждый алгоритм должен оцениваться по всем 3 параметрам: наилучшему, наихудшему и среднему числу базовых операций. К сожалению, получение средних оценок часто бывает невозможно, и поэтому на практике больше всего используются оценки для наихудшего случая. При этом для сравнения алгоритмов важен не точный вид функциональной зависимости трудоемкости от объема входных данных, а скорее характер или поведение этой зависимости. Эта информация помогает ответить на следующий важнейший вопрос: если рост трудоемкости с увеличением объема данных неизбежен, то насколько быстро происходит этот рост?

Для оценивания трудоемкости алгоритмов была введена специальная система обозначений - так называемая О-нотация. Эта нотация позволяет учитывать в функции f (n) лишь наиболее значимые элементы, отбрасывая второстепенные.

Например, в функции f (n) = 2n2 + n - 5 при достаточно больших n компонента n2 будет значительно превосходить остальные слагаемые, и поэтому характерное поведение этой функции определяется именно этой компонентой. Остальные компоненты можно отбросить и условно записать, что данная функция имеет оценку поведения (в смысле скорости роста ее значений) вида О(n2).