Разработать структуру данных (двоичные деревья поиска)

Содержание

• 1. Двоичное дерево
• 2. Представления двоичных деревьев
• 3. Двоичное дерево поиска
• 4. Добавление элемента
• 5. Вывод в виде скобочной последовательности
• 6. Поиск элемента
• 7. Подсчет суммы элементов
• 8. Разработка структуры
• 9. Создание тестовых файлов
• 10. Вывод предметного указателя
• Список литературы
• Приложение 1
• Приложение 2

1. Двоичное дерево

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

Представьте себе

список, в котором за каждым элементом может идти не один следующий, а два.

Рисунок 1

Однако дерево принято рисовать так:

Рисунок 2

Элементы дерева называются вершинами (vertex) или узлами (node), а соединения ребрами (edge) или дугами (arc).

От каждой вершины вниз идет не более двух ребер (поэтому дерево двоичное).

Вершины, с которыми соединена данная, и которые расположены ниже нее, называются детьми данной вершины (также часто говорят «сыновья»). При этом различаются правый и левый сын. Если вершина A является ребенком вершины B, то вершина B называется родителем A. У каждой вершины может быть не более одного родителя.

Вершина, не имеющая родителя, называется корнем дерева. То есть мы изображаем дерево корнем вверх так удобнее.

Вершины, не имеющие детей, называются листьями дерева.

Так на рисунке 5 корень дерева, вершина 3 левый сын вершины 5, вершина 2 — правый сын вершины 1, вершины 2, 6, 8 являются листьями.

Все сказанное выше неформально описывает двоичное дерево. На самом деле двоичное дерево это математический объект и его можно определить строго. Одно из определений рекурсивное звучит так:

Определение.

Каждая вершина имеет не более двух детей и не более одного родителя.

Одна вершина, не имеющая ни детей, ни родителей, является двоичным деревом.

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

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

Вершины 7, 6, 8 образуют левое поддерево вершины 5. Вершина 7 является корнем этого поддерева.

2. Представления двоичных деревьев

Самое простой вариант представления двоичного дерева массив, в котором первый элемент это корень дерева, элемент с номером 2n левый сын элемента с номером n, а элемент с номером 2n+1 правый.

Для дерева на рисунке массив будет выглядеть так.

1 2 3 4 5 6 7 8 9

5 3 7 1 6 8 2

Рисунок 3

Действительно, левый сын вершины 5 (вершина 3) находится на месте с номером 2 (2 * 1), левый сын вершины 3 (1) на месте с номером 4(2 * 2), правый сын вершины 5 (вершина 7) на месте с номером 3 (2 * 1 + 1), а правый сын вершины 1 (2) на месте с номером 9 (2 * 4 + 1).

Два элемента в массиве пусты это места несуществующих вершин правого сына вершины 3 (номер 5 = 2 * 2 + 1) и левого сына вершины 1 (номер 8 = 2 * 4). Это и есть самый большой недостаток такого способа хранения деревьев. Всего вершин в дереве высотой N может быть 2N-1, то есть для такого дерева

Рисунок 4

Понадобится массив размером 26 = 64 элемента (для всего 7 вершин), а для такого же дерева, но из 11 вершин уже 210 = 1024 элемента.

Для экономии памяти можно хранить дерево используя конструкцию аналогичную списку.

Пусть в каждой вершине хранится элемента данных Data и два указателя на сыновей Left и Right.

5 11

nil nil nil nil

Рисунок 5

3. Двоичное дерево поиска

Двоичное дерево «вообще» практически не используется как структура данных. Используется специальный вид двоичных деревьев двоичное дерево поиска.

Определение

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

В частности, дерево, приведенное на рисунке 2, являеся двоичным деревом поиска: для каждой вершины T выполняется:

T.Left.Data < T. Data  T.Right.Data.

Сам термин «двоичное дерево поиска» применяется потому, что такая структура дерева сильно облегчает поиск элемента в нем: как узнать, есть ли в дереве число X? Начнем с корня: если X меньше значения в корне, пойдем налево, если больше направо, если равен мы нашли X, и так в каждой вершине. Если мы хотим перейти к одному из детей, а он не существует, значит элемента X в дереве нет. Поиск в ДДП будет подробно рассмотрен ниже.

4. Добавление элемента

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

Нам понадобится хранить в основной программе только один указатель корень дерева R (root).

Рассмотрим операцию добавления элемента в дерево. Новый элемент нужно добавлять так, чтобы дерево продолжало удовлетворять определению ДДП. Как это сделать?

Начнем с корня. Сравним добавляемый элемент X со значением в текущей вершине. Если X меньше, пойдем налево, если больше или равен направо. Будем двигаться так до тех пор, пока не найдем свободного места в дереве.

Это же можно переформулировать так: если X меньше значения в вершине, добавить X в левое поддерево, если больше в правое. Налицо рекурсия. Нам необходима рекурсивная процедура добавления элемента в дерево с корнем t. Если t = nil, она создает новую вершину и записывает в t указатель на нее, а если нет то вызывает сама себя от нужного поддерева t.

5. Вывод в виде скобочной последовательности

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

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

Рисунок 6

Гораздо проще вывести дерево в виде скобочной последовательности. Определим ее так:

Пустое дерево на экран не выводится

Дерево, состоящее из единственного элемента, выводится в виде значения этого элемента в скобках

Дерево общего вида выводится так: (,)

Так, например, дерево, изображенное на рисунке 2, будет выглядеть так:

(5 (3 (1, (2)),), (7 (6), (8)))

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

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

6. Поиск элемента

Теперь вернемся к операциям над ДДП. Наиболее важной из них является поиск.

В конечном счете нам нужна функция, которая получает на вход дерево T и искомое значение X, и возвращает true или false в зависимости от того, есть в дереве данное значение или нет.

Организация поиска в двоичном дереве похожа на добавление в него.

Определим функцию рекурсивно:

Если X равно значению в текущей вершине, вернуть true

Если X меньше значения в текущей вершине, то искать в левом поддереве и вернуть результат этого поиска.

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

Если дерево T пусто, вернуть false

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

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

Для несбалансированного дерева поиск пойдет медленно, поскольку высота дерева в худшем случае равна общему количеству элементов N (см. рис. 4).