Обработка динамических структур данных

3.1. Деревья

Граф – это один из видов нелинейных структур данных, состоящий из конечного, непустого множества узлов и множества рёбер. Если все рёбра графа представлены в виде упорядоченных пар узлов или вершин, то граф называется ориентированным. Ориентированный граф без цикла называется ориентированным ациклическим графом.

Дерево – ориентированный ациклический граф, удовлетворяющий следующим условиям:

1)      имеется в точности один узел, называемый корнем, в который не входит ни одно ребро;

2)      в каждый узел, кроме корня, входит ровно одно ребро;

3)      из корня к каждому узлу идет путь, который является единственным;

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

3.1.1. Бинарные (двоичные) деревья

Двоичным деревом называется такое упорядоченное дерево, что:

1)      каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын;

2)      каждый узел имеет не более одного левого сына и не более одного правого.

Двоичное дерево обычно представляется в виде двух массивов: левый сын и правый сын.

Обходы деревьев.

Большинство алгоритмов, использующие деревья «проходят» дерево, то есть посещают его узлы в некотором порядке.

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

Произвольное бинарное дерево можно обходить:

1)      прямым (нисходящим) обходом, то есть от корневого узла вниз к листьям;

2)      кольцевым (восходящим) обходом, то есть от листьев вверх к корню.

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

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

Алгоритм 1: нисходящий обход двоичного дерева:

1)      если дерево пусто, то закончить обход дерева;

2)      иначе обработать (прочитать) корень;

3)      обойти левое поддерево. Если пути влево нет, то движение продолжается по ближайшему пути (правому). При этом сразу после рассмотрения очередного узла просматриваются слева направо исходящие из них ветки;

4)      обойти правое поддерево;

5)      закончить обход дерева.

Алгоритм нисходящего обхода дерева двоичного поиска представлен ниже на рисунке 1, а).

Алгоритм 2: восходящий обход двоичного дерева:

1)      если дерево пусто, то закончить обход дерева;

2)      иначе обойти левое поддерево; чтение начинается с левого листа. Каждый узел читается после того, как прочитаны его левые и правые порожденные;

3)      обойти правое поддерево;

4)      обработать корень, закончить обход дерева.

Алгоритм восходящего обхода дерева двоичного поиска представлен ниже на рисунке 1, б).

Алгоритм 3: смешанный обход двоичного дерева:

1)      если дерево пусто, то закончить обход дерева;

2)      иначе обойти левое поддерево. Обработать корень, обойти правое дерево;

3)      закончить обход дерева.

Алгоритм смешанного обхода дерева двоичного поиска представлен ниже на рисунке 1, в).

             а)                                  б)                                 в)

                                           Рисунок 1

3.1.2. Типовые операции над двоичными деревьями:

1)      добавление элемента в дерево;

2)      удаление элемента из дерева;

3)      обход дерева (для печати элементов и т.д.);

4)      поиск в дереве.

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

1. Добавление элемента в дерево

Для включения нового элемента в двоичное дерево поиска вначале нужно определить его точное положение — а именно внешний узел, который должен быть заменен путем отслеживания пути поиска элемента, начиная с корня. Кроме сохранения указателя n на текущий узел мы будем хранить указатель р на предка узла n. Таким образом, когда n достигнет некоторого внешнего узла, р будет указывать на узел, который должен стать предком нового узла. Для осуществления включения узла мы создадим новый узел, содержащий новый элемент, и затем свяжем предок р с этим новым узлом (рисунок 2).

                                                                                    Рисунок 2

2. Удаление элемента в дереве

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

Рисунок 3

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

1)      узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n;

2)      у узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n;

3)      узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.

Очень важно проследить, как будет выглядеть результирующее двоичное дерево поиска в каждом случае. Рассмотрим случай 1. Если подлежащий удалению узел n, является левым потомком, то элементы, относящиеся к правому поддереву n будут меньше, чем у узла р, предка узла n. При удалении узла n его правое поддерево связывается с узлом р и элементы, хранящиеся в новом левом поддереве узла р конечно остаются меньше элемента в узле р. Поскольку никакие другие ссылки не изменяются, то дерево остается двоичным деревом поиска. Аргументы остаются подобными, если узел n является правым потомком, и они тривиальны, если n — корневой узел. Случай 2 объясняется аналогично. В случае 3 элемент v, записанный в узле n, перекрывается следующим большим элементом, хранящимся в узле m (назовем его w), после чего элемент w удаляется из дерева. В получающемся после этого двоичном дереве значения в левом поддереве узла n будут меньше w, поскольку они меньше v. Более того, элементы в правом поддереве узла n больше, чем w, поскольку (1) они больше, чем v, (2) нет ни одного элемента двоичного дерева поиска, лежащего между v и w и (3) из них элемент w был удален.

Заметим, что в случае 3 узел m должен обязательно существовать, поскольку правое поддерево узла n непустое. Более того, рекурсивный вызов для удаления m не может привести к срыву рекурсивного вызова, поскольку если узел m не имел бы левого потомка, то был бы применен случай 1, когда его нужно было бы удалить.

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

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

Рисунок 4

3. Поиск в двоичном дереве

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

Рисунок 5

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

                            Рисунок 6

Для поиска заданного ключа в дереве поиска достаточно пройти по одному пути от корня до (возможно, листовой) вершины (рисунок 7).

Рисунок 7

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

Рисунок 8

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

              3.2. Метод решения

              Игра «20 вопросов» это классическая программа из класса «интеллектуальных» построена для того чтобы отгадывать задуманные пользователем объекты. Эта программа использует двоичное дерево как главную структуру данных. Нелистьевые вершины такого дерева содержат предикаты (вопросы, ответы на которые могут принимать только «да» или «нет») Пользователь должен задумать простой объект и давать ответы на вопросы программы в соответствии со свойствами этого объекта. Пользователь получает вопросы, содержащиеся в вершинах дерева начиная с его корня. Ответ «да» пользователя соответствует пути, проходящему через левую дочь текущей вершины, а ответ «нет»— пути, проходящему через правую дочь текущей вершины. После каждого ответа выбирается соответствующая ветвь и процесс повторяется. Листьевые вершины содержат определение того объекта, которому соответствует последовательность ответов пользователя ведущих от корня дерева к каждому листу. Когда в процессе движения программа доходит до листа она выводит содержащееся там определение объекта «угадывая» тем самым объект задуманный пользователем. Если программа угадала верно, считается, что она выиграла. Если ответ не верен, программа начинает «обучаться», предлагая пользователю ввести вопрос (ответ «да» или «нет») на который зафиксирует различие между объектом, который задумал пользователь, и объектом, который вычислила программа. Вопрос сформулированный пользователем затем помещается в новую вершину дерева, дочерними вершинами которого становятся лист с определением «старого» объекта и лист с определением нового объекта. После этого пользователь может начать новый тур. Конец игры определяется программой по ответу пользователя на специальное приглашение к новому туру.

Рассмотрим пример работы такой программы.

Предположим, что начальное состояние дерева имеет следующий вид:

Имеет две ноги?

Лошадь                                         Кенгуру

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

Загадайте животное.

да-1; нет-0;

Затем программа начинает задавать вопросы, которые на экране монитора имеют следующий вид:

ВОПРОС: Имеет две ноги?

Ответ:1;

Программа повторяет вывод вопросов (содержимого вершин дерева) начиная с его корня дерева и продвигаясь по его потомкам в соответствии с ответам пользователя. Как только программа достигнет некоторый лист, его содержимое интерпретируется как результат «угадывания» задуманного пользователем объекта. Этот результат выводится на экран в форме: