Инфиксный (симметричный) обход дерева

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм обхода дерева

1. Если дерево пусто, остановиться.

1. Иначе

   1. Рекурсивно обойти правое поддерево Т.

   2. Применить функцию f к корневому узлу.

   3. Рекурсивно обойти левое поддерево Т.

В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции ИНФИКСНЫЙ_ОБХОД будут выведены все пары в порядке возрастания ключей. Если же использовать ПРЕФИКСНЫЙ_ОБХОД, то пары будут выведены в порядке, соответствующем описанию дерева.

Поиск элемента в дереве

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

4. совпадению,

5. близости снизу

6. близости сверху.

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

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

Поиск элемента двоичного дерева

Рассмотрим алгоритм поиска по совпадению.

Поиск элемента (ИСКАТЬ)

Дано: дерево Т и ключ K.

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

Алгоритм поиска элемента двоичного дерева по ключу

1. Если дерево пусто, сообщить, что узел не найден, и остановиться.

2. Иначе сравнить K со значением ключа корневого узла X.

   1. Если K=X, выдать ссылку на этот узел и остановиться

      1. Иначе, если K>X, рекурсивно искать ключ K в правом поддереве Т.

      2. Иначе (если K<X) рекурсивно искать ключ K в левом поддереве Т.

Поиск элемента в дерева

Благодаря структуре этого дерева и постоянно поддерживаемому балансу, поиск осуществляется за логарифмическое время от количества элементов. Сам алгоритм описывается следующим образом. Пусть ищется значение X в заданном В-дереве.

Алгоритм поиска элемента В дерева

1. Начинаем от корня

2. Если X –один из ключей текущего узла, то СТОП, ключ найден.

Иначе находим пару соседних ключей Y, Z, таких что X лежит в интервале от Y до Z.

3. Переходим к потомку между Y и Z.

4. Возврат к шагу 2.

5. Если дошли до листа и Х нет среди ключей, то СТОП, ключ и элемент не найден.

Порядок выполнения лабораторной работы Подготовка к работе

Подготовка предполагает выполнение следующих этапов.

1. Знакомство со всеми разделами руководства.

2. Разработка алгоритма и программы построения двоичного дерева поиска.

3. Разработка алгоритма и программы построения В+ дерева.

Последовательность выполнения лабораторной работы

1. Разработать алгоритм и программу построения двоичного дерева поиска:

1. Получить у преподавателя задание на величину диапазона значений ключей и размер их массива n.

2. Сформировать массив ключей, значения которых задаются с помощью датчика случайных чисел.

3. По заданию преподавателя упорядочить значения ключей по возрастанию (убыванию).

4. Приняв за корень элемент с ключом из середины массива (ключ с номером n / 2), построить двоичное дерево поиска. Информационные поля узлов дерева можно оставить пустыми.

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

2. Разработать алгоритм и программу построения В+ дерева:

1. Получить у преподавателя задание на количество ярусов, величину диапазона значений ключей и размер их массива n на каждом ярусе.

2. Сформировать массив ключей, значения которых задаются с помощью датчика случайных чисел.

3. По заданию преподавателя упорядочить значения ключей по возрастанию (убыванию).

4. Приняв за корень элемент с ключом из середины массива (ключ с номером n / 2), построить В+ дерево. Информационные поля узлов дерева можно оставить пустыми.

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

3. Разработать алгоритм и программу поиска заданного преподавателем типа (по совпадению, интервалу или близости) на двоичном и В+ дереве.

4. Оценить сложность разработанных алгоритмов.