Новосибирский государственный технический университет
Кафедра вычислительной техники
 |
Лабораторная работа №2
по дисциплине
«Структуры и алгоритмы обработки данных»
«Нелинейные коллекции данных - деревья»
Группа:
Вариант: 6
Студенты:
Преподаватель:
Новосибирск 2003
Задание.
Спроектировать, реализовать и провести тестовые испытания АТД для нелинейной коллекции - "Дерево двоичного поиска”. Спроектировать, реализовать и провести тестовые испытания АТД для нелинейной коллекции - "Сбалансированное дерево поиска".
АТД "2-3 дерево" реализовать, как самостоятельный класс. Получить оценки эффективности операций Find, Insert, Delete относительно количества узлов в дереве, выраженные в средней на операцию глубине пути в дереве. Получить сравнительную оценку эффективности двоичного дерева поиска и сбалансированного дерева поиска.Вариант: АТД "Нерекурсивное 2-3 дерево".
Формат АТД «Дерево».
АТД Tree
Данные:
Структура данных: связное дерево с указателями на сыновей и родителя
Счетчик узлов: количество узлов, включённых в данный момент в дерево
Область значений ключей в дереве: любые неравные значения
Операции:
Конструктор:
Начальные значения: нет (по умолчанию)
Процесс: установление начального количества узлов в дереве в ноль.
Insert:
Вход: значение ключа и данные для вставки
Предусловие: значение данных ≠nil-значению, значение ключа уникально
Процесс: добавление значения ключа и данных в дерево,
увеличение количества узлов на 1, если выполнено предусловие; иначе данные и значение ключа в дерево не добавляются
Выход: логическое true – если вставка произведена,
false – в противном случае
Постусловие: если произведена вставка, количество узлов увеличивается на 1
Delete:
Вход: значение ключа
Предусловие: значение ключа принадлежит множеству ключей,
включённых в дерево.
Процесс: удаление узла дерева по заданному ключу, уменьшение количества узлов на 1, если выполнено предусловие;
иначе удаление не производится
Выход: логическое true – если удаление произведено,
false – в противном случае
Постусловие: если произведено удаление, количество
узлов в дереве уменьшается на 1
Size:
Вход: нет
Предусловие: нет
Процесс: нет
Выход: количество узлов в дереве
Постусловие: нет
Empty:
Вход: нет
Предусловие: нет
Процесс: определение пустоты дерева
Выход: логическое true, если в дереве нет ни одного ключа с данными,
логическое false – в противном случае
Постусловие: нет
Clear:
Вход: нет
Предусловие: нет
Процесс: удаление всех узлов в дереве, установление количества узлов =0
Выход: нет
Постусловие: количество узлов в дереве =0
Find:
Вход: значение ключа для поиска
Предусловие: значение ключа принадлежит множеству ключей,
включённых в дерево.
Процесс: поиск узла в дереве, значение ключа
которого совпадает с заданным
Выход: логическое true, если узел найден
логическое false – в противном случае
Постусловие: нет
Конец АТД Tree
Результаты работы тестовой программы.
Выводы.
Экспериментальные оценки эффективности основных операций как в двоичном несбалансированном, так и в сбалансированном деревьях совпали с теоретическими. Полученные экспериментально эффективности показывают в общем случае логарифмические зависимости для вставки, удаления и поиска. Худший случай загрузки ключей в несбалансированное дерево вырождает его в линейную СД.
Реализация методов на языке С++.
