Варианты задания

1.

 Алгоритмы операций АТД реализуются в рекурсивной форме,

 Схема операции обхода: t -> L_t -> R_t,

 Дополнительная операция: поиск для заданного ключа предыдущего по значению ключа в дереве (нерекурсивная форма).

2.

 Алгоритмы операций АТД реализуются в нерекурсивной форме,

 Схема операции обхода: L_t -> t -> R_t,

 Дополнительная операция: определение длины внешнего пути дерева (рекурсивная форма).

3.

 Алгоритмы операций АТД реализуются в рекурсивной форме,

 Схема операции обхода: L_t -> t -> R_t,

 Дополнительная операция: вставка элемента в корень дерева (нерекурсивная форма).

4.

 Алгоритмы операций АТД реализуются в нерекурсивной форме,

 Схема операции обхода: t -> L_t -> R_t,

 Дополнительная операция: поиск n -го по значению ключа в дереве (рекурсивная форма).

5.

 Алгоритмы операций АТД реализуются в рекурсивной форме,

 Схема операции обхода: L_t -> R_t -> t,

 Дополнительная операция: определение длины внутреннего пути дерева (нерекурсивная форма).

6.

 Алгоритмы операций АТД реализуются в нерекурсивной форме,

 Схема операции обхода: L_t -> t -> R_t,

 Дополнительная операция: удаление узла дерева на основе метода объединения двух поддеревьев удаляемого узла (рекурсивная форма).

7.

 Алгоритмы операций АТД реализуются в рекурсивной форме,

 Схема операции обхода: L_t -> t -> R_t,

 Дополнительная операция: определение критерия сбалансированности для узлов дерева (нерекурсивная форма).

8.

 Алгоритмы операций АТД реализуются в нерекурсивной форме,

 Схема операции обхода: L_t -> R_t -> t,

 Дополнительная операция: объединение двух поддеревьев (рекурсивная форма).

Методические указания по выполнению задания

1. Для АТД "BST - дерево" разрабатываются формат АТД и шаблонный класс - контейнер.

2. Для тестирования разработанного класса - контейнера разрабатываются две программы: программа тестирования операций через меню и программа тестирования трудоёмкости операций поиска, вставки и удаления.

3. Тестирование операций через меню выполняется для BST - дерева небольшого размера (до 20 элементов). Размер BST - дерева и тип данных, хранящихся в нём, задаётся с клавиатуры перед началом тестирования. После выполнения операций необходимо вывести на экран содержимое BST - дерева с помощью операции вывода структуры дерева.

4. Перед тестированием эффективности операций задаются тип данных, хранящихся в дереве, и размер дерева. Размер дерева варьируется в пределах от 10 до 100 000 элементов. После тестирования на экран выводятся размер дерева и средняя трудоёмкость операций поиска, вставки и удаления (среднее число пройденных узлов дерева).

Задание к лабораторной работе

Цели работы: Изучение и исследование методов балансировки двоичных деревьев поиска на примере АТД "Сбалансированное двоичное дерево поиска". Освоение методики модификации коллекций с помощью механизма наследования классов.

Задание к лабораторной работе:

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

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

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

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

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

 доступ к значению элемента с заданным ключом,

 включение нового элемента с заданным ключом,

 удаление элемента с заданным ключом,

 итератор для доступа к элементам дерева с операциями:

 1) установка на корень дерева,

 2) проверка конца дерева,

 3) доступ к данным текущего элемента дерева,

 4) переход к следующему по значению ключа элементу дерева,

 5) переход к предыдущему по значению ключа элементу дерева,

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

 вывод структуры дерева на экран,

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

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

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

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

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

 1) титульный лист,

 2) цель лабораторной работы,

 3) общее задание (пункты 1 - 5) и вариант задания,

 4) формат АТД,

 5) определение шаблонного класса для коллекции "Сбалансированное двоичное дерево поиска", предназначенное для клиентской программы,

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

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

 8) сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов АТД,

 9) выводы,

 10) список использованной литературы,

 11) приложение с текстами программ:

 полное определение класса и текстов методов класса,

 текст программы тестирования трудоёмкости операций АТД.