СибГУТИ Лабораторная работа 3 Вариант 18 Структуры и алгоритмы обработки данных (часть 2) скачать бесплатно
ЛАБОРАТОРНАЯ РАБОТА 3
Тема: Двоичное Б-дерево поиска (ДБД)
Цель работы: Изучение процесса программного построения ДБД.
Разработать подпрограмму построения ДБ-дерева для массива целых чисел.
Построить ДБ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
Для построенного ДБ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту (как для двоичного дерева) и высоту ДБ-дерева как количество уровней, сравнить их с аналогичными характеристиками АВЛ-дерева. ДБ-дерево необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 3 и проанализировать полученные результаты.
Таблица 3 - Результаты работы подпрограммы построения ДБ-дерева
Размердерева АВЛ-дерево ДБД
Контр.
сумма Высота фактическая Теор. оценки для сред. высоты Контр.
сумма Кол-во уровней Теор. оценки для высоты ДБД Теор. оценки для сред. высоты двоичного дерева
100
200
300
400
500
Описание
Структура TNode хранит информацию о вершине дерева: информационное поле, указатель на левую вершину, указатель на правую вершину и баланс.
Функция Array1 формирует упорядоченный по возрастанию массив.
Функция Array2 формирует упорядоченный по убыванию массив.
Функция Array3 формирует случайный массив.
Функция NewNode создает новую вершину.
Функция AddNode добавляет вершину в двоичное Б-дерево.
Функция CreateTree создает двоичное Б-дерево.
Функция TreeSize вычисляет размер дерева.
Функция TreeHeight вычисляет высоту дерева.
Функция TreeAverageHeight вычисляет среднюю высоту дерева.
Функция Sum вычисляет контрольную сумму данных в вершинах дерева.
Функция Print выводит содержимое дерева обходом слева направо.
Функция TreeLevels вычисляет количество уровней дерева.
Полученные результаты
Для упорядоченного по возрастанию массива:
Для упорядоченного по убыванию массива:
Для случайного массива:
Таблица результатов:
Размер
дерева АВЛ-дерево ДБД
Контр.
сумма Высота фактич. Теор. оценки для сред. высоты Контр.
сумма Кол-во уровней Высота фактич. Теор. оценки для сред. высоты двоичного дерева
100 5050 5.89 Меньше 9.28 5050 5 6.03 6.66
200 20100 6.86 Меньше 10.70 20100 6 7.06 7.65
300 45150 7.43 Меньше 11.53 45150 7 7.51 8.23
400 80200 7.87 Меньше 12,13 80200 7 8.12 8.65
500 125250 8.25 Меньше 12,59 125250 7 8.42 8.97
Анализ
Высота двоичного Б-дерева h = log(n + 1).
Средние высоты соответствуют теоретическим оценкам.
Средняя высота ДБД-дерева оказалась немного больше, чем средняя высота АВЛ-дерева. Это соответствует теоретическим сведениям.
Сумму элементов для деревьев вычислим как сумму элементов арифметической прогрессии.
Для дерева размера 100 сумма элементов равна (1 + 100) / 2 * 100 = 5050
Для дерева размера 200 сумма элементов равна (1 + 200) / 2 * 200 = 20100
Для дерева размера 300 сумма элементов равна (1 + 300) / 2 * 300 = 45150
Для дерева размера 400 сумма элементов равна (1 + 400) / 2 * 400 = 80200
Для дерева размера 500 сумма элементов равна (1 + 500) / 2 * 500 = 125250
