Задание к лабораторной работе. 1. Спроектировать, реализовать и провести тестовые испытания АТД «Сбалансированное

1. Спроектировать, реализовать и провести тестовые испытания АТД «Сбалансированное двоичное дерево поиска» для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.

АТД «Сбалансированное двоичное дерево поиска» представляет собой модифицированную версию АТД «BST -дерево» с трудоёмкостью операций O(log ₂ n).

Интерфейс АТД «Сбалансированное двоичное дерево поиска» включает следующие операции:

· опрос размера дерева,

· очистка дерева,

· проверка дерева на пустоту,

· поиск объекта с заданным ключом,

· включение нового объекта с заданным ключом,

· удаление объекта с заданным ключом,

· итератор для доступа к объектам в дереве дерева с операциями:

- установка на первый объект в дереве (объект с минимальным ключом),

- установка на последний объект в дереве (объект с максимальным ключом),

- проверка окончания просмотра,

- доступ по чтению и записи к данным текущего объекта в дереве,

- переход к следующему по значению ключа объекту в дереве,

- переход к предыдущему по значению ключа объекту в дереве,

Для тестирования коллекции интерфейс АТД «Сбалансированное двоичное дерево поиска» включает дополнительные операции:

· вывод структуры дерева на экран (см. приложение 3),

· опрос числа просмотренных операцией узлов дерева.

2. Выполнить отладку и тестирование всех операций АТД «Сбалансированное двоичное дерево поиска» с помощью меню операций.

3. Выполнить сравнительное тестирование средней трудоёмкости операций для коллекций «BST -дерево» и «Сбалансированное двоичное дерево поиска» для среднего и худшего случаев.

4. Провести сравнительный анализ экспериментальных показателей трудоёмкости операций.

5. Составить отчёт по лабораторной работе. Отчёт должен содержать следующие пункты:

1) пункты 1 – 5 (см. раздел 2.2),

6) описание методики тестирования трудоёмкости операций,

7) таблицы и графики с полученными оценками трудоёмкости операций для худшего и среднего случаев функционирования АТД. Должны быть приведены графики трудоёмкости для операций поиска, вставки и удаления (графики обоих коллекций совмещены в одной системе координат),

8) пункты 8 – 11 (см. раздел 2.2),

5.2.1. Варианты заданий:

1. АТД «АВЛ-дерево», как модификация АТД «BST -дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.

2. АТД «АВЛ-дерево», как модификация АТД «BST -дерево». Алгоритмы операций АТД реализуются в итерационной форме.

3. АТД «RB-дерево», как модификация АТД «BST -дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.

4., АТД «RB-дерево», как модификация АТД «BST -дерево». Алгоритмы операций АТД реализуются в итерационной форме.

5. АТД «2-3-дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.

6. АТД «2-3-дерево». Алгоритмы операций АТД реализуются в итерационной форме.

7. АТД «Рандомизированное дерево», как модификация АТД «BST -дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.

8. АТД «Рандомизированное дерево», как модификация АТД «BST -дерево». Алгоритмы операций АТД реализуются в итерационной форме.

---

Дата добавления: 2015-11-04