Перед выполнением заданий лабораторной работы рекомендуется изучить теоретический материал по теме работы и описание методов обработки данных на псевдокоде, используя конспекты лекционных занятий и литературу из списка.
Задания лабораторных работ выполняются на языке программирования С/С++, среда программирования по выбору студента.
Изучаемые методы построения деревьев рекомендуется программно реализовывать в виде отдельных функций (подпрограмм). Вычисление хактеристики Заполнение массивов данными, вывод их на экран, вычисление вспомогательных величин и пр. необходимо также оформлять в виде отдельных подпрограмм.
При выполнении заданий следует обеспечить вывод на экран данных на всех шагах алгоритма. Программа должна иметь дружественный, интуитивно понятный интерфейс (меню пользователя, вывод подсказок, комментарии при вводе/выводе данных и т.д.).
Тестирование разработанной программы необходимо проводить для различных типов входных данных (случайный массив, упорядоченный массив в прямом и обратном порядке). После тестирования необходимо проанализировать полученные результаты, т.е. проверить соответствие полученных экспериментальным путем величин теоретическим оценкам.
Для зачета по лабораторной работе студенту необходимо представить
Отчет должен включать в себя следующие разделы:
Тема: Идеально сбалансированное дерево поиска (ИСДП) и случайное дерево поиска (СДП)
Цель работы: Изучение процесса программного построения ИСДП и СДП.
Таблица 1 - Результаты работы программ
Размер дерева |
СДП |
ИСДП |
||||
Контр. сумма |
Высота фактическая |
Теор. оценки для сред. высоты |
Контр. сумма |
Высота фактическая |
Теор. оценки для сред. высоты |
|
100 |
|
|
|
|
|
|
200 |
|
|
|
|
|
|
300 |
|
|
|
|
|
|
400 |
|
|
|
|
|
|
500 |
|
|
|
|
|
|
Тема: Сбалансированные по высоте деревья поиска (АВЛ)
Цель работы: Изучение процесса программного построения АВЛ-дерева.
Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.
Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 2 и проанализировать полученные результаты/
Таблица 2 - Результаты работы программы построения АВЛ-дерева для массива целых чисел
Размер дерева |
АВЛ-дерево |
ИСДП |
||||
Контр. сумма |
Высота фактическая |
Теор. оценки для сред. высоты |
Контр. сумма |
Высота фактическая |
Теор. оценки для сред. высоты |
|
100 |
|
|
|
|
|
|
200 |
|
|
|
|
|
|
300 |
|
|
|
|
|
|
400 |
|
|
|
|
|
|
500 |
|
|
|
|
|
|
Тема: Двоичное Б-дерево поиска (ДБД)
Цель работы: Изучение процесса программного построения ДБД.
Разработать подпрограмму построения ДБ-дерева для массива целых чисел.
Построить ДБ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
Для построенного ДБ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту (как для двоичного дерева) и высоту ДБ-дерева как количество уровней, сравнить их с аналогичными характеристиками АВЛ-дерева. ДБ-дерево необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 3 и проанализировать полученные результаты.
Таблица 3 - Результаты работы подпрограммы построения ДБ-дерева
Размер дерева |
АВЛ-дерево |
ДБД |
|||||
Контр. сумма |
Высота фактическая |
Теор. оценки для сред. высоты |
Контр. сумма |
Кол-во уровней |
Теор. оценки для высоты ДБД |
Теор. оценки для сред. высоты двоичного
дерева |
|
100 |
|
|
|
|
|
|
|
200 |
|
|
|
|
|
|
|
300 |
|
|
|
|
|
|
|
400 |
|
|
|
|
|
|
|
500 |
|
|
|
|
|
|
|