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

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

Двоичное дерево поиска (Binary Search Tree – BST) представляет упорядоченное, иерархическое, ассоциативное множество элементов, между которыми существуют структурные отношения «предки – потомки».

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

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

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

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

· доступ к данным с заданным ключом,

· включение данных с заданным ключом,

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

· обход узлов дерева по схеме, заданной в варианте задания,

· дополнительная операция, заданная в варианте задания.

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

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

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

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

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

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

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

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

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

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

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

3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов для вырожденного и случайного BST -дерева.

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

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

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

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

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

8) сравнительный анализ теоретических и экспериментальных оценок трудоёмкости для операций BST -дерева,

9) сравнительный анализ экспериментальных оценок трудоёмкости для различных операций BST -дерева,

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

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

1.

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

· Схема операции обхода: t → L _t → R _{t .}.

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

2.

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

· Схема операции обхода: Lt → t → Rt.

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

3.

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

· Схема операции обхода: L _t → t → R _{t .}.

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

4.

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

· Схема операции обхода: t → L _t → R _t.

· Дополнительная операция: поиск k –го ключа в дереве (рекурсивная форма алгоритма).

5.

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

· Схема операции обхода: L _t → R _t → t.

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

6.

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

· Схема операции обхода: L _t → t → R _{t .}.

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

7.

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

· Схема операции обхода: Схема операции обхода: t → L _t → R _t .

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

8.

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

· Схема операции обхода: L _t → R _t → t.

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

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

1. Создание коллекции «BST -дерево» выполняется в соответствии с технологией реализации коллекций, изложенной в разделе 1. Для АТД «BST -дерево» разрабатываются формат АТД и шаблонный класс – контейнер. Для элементов дерева и итератора разрабатываются вспомогательные внутренние классы, определённые в классе дерева.

2. Для реализации операций АТД, рекомендуется использовать алгоритмы, приведённые в приложении 3.

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

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

5. Тестирование трудоёмкости операций поиска, вставки и удаления выполняется в соответствии с технологией тестирования, изложенной в разделе 1.4.

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

Контрольные вопросы и упражнения.

1. Перечислите достоинства и недостатки дерева на базе массива.

2. Перечислите достоинства и недостатки дерева на базе связной структуры с адресными указателями.

3. Перечислите основные операции BST -дерева и теоретические оценки их трудоёмкости.

4. Приведите схему структуры дерева на базе связной структуры после серии операций: вставка (10), вставка (6), вставка (23), вставка (15), вставка (4), вставка (9), вставка (7), вставка (13), вставка (14), удаление (23), удаление (9), удаление (10). Дерево первоначально пусто.

5. Приведите псевдокод операции итератора дерева «переход к следующему по значению ключа узлу».

6. Приведите псевдокод итерационного алгоритма обхода BST -дерева по схеме L _t → R_t → t.

7. Для дерева, построенного в упражнении 4, приведите последовательности элементов, полученные в результате обхода по схемам t → L _t → R _{t , ,.} L _t → R _t → t и L _t → t → R _{t .}.

8. Для дерева, построенного в упражнении 4, приведите элемент с порядковым номером 6.

9. Приведите изображение изначально пустого дерева после вызовов алгоритма вставки в корень дерева последовательности ключей 15, 18, 7, 9, 4, 5, 14.

10. Приведите изображение дерева, полученного в результате работы алгоритма объединения исходных деревьев:

5. Лабораторная работа «Коллекция данных - сбалансированное дерево поиска»

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

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