СибГУТИ Лабораторная работа 2 Вариант 18 Структуры и алгоритмы обработки данных (часть 2) скачать бесплатно
ЛАБОРАТОРНАЯ РАБОТА 2
Тема: Сбалансированные по высоте деревья поиска (АВЛ)
Цель работы: Изучение процесса программного построения АВЛ-дерева.
Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.
Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу 2 и проанализировать полученные результаты/
Таблица 2 - Результаты работы программы построения АВЛ-дерева для массива целых чисел
Размер дерева АВЛ-дерево ИСДП
Контр.
сумма Высота фактическая Теор. оценки для сред. высоты Контр.
сумма Высота фактическая Теор. оценки для сред. высоты
100
200
300
400
500
Описание
Структура TNode хранит информацию о вершине дерева: информационное поле, указатель на левую вершину, указатель на правую вершину и баланс.
Функция Array1 формирует упорядоченный по возрастанию массив.
Функция Array2 формирует упорядоченный по убыванию массив.
Функция Array3 формирует случайный массив.
Функция NewNode создает новую вершину.
Функция AddNode добавляет вершину в АВЛ-дерево.
Функция CreateTree создает АВЛ-дерево.
Функция TreeSize вычисляет размер дерева.
Функция TreeHeight вычисляет высоту дерева.
Функция TreeAverageHeight вычисляет среднюю высоту дерева.
Функция Sum вычисляет контрольную сумму данных в вершинах дерева.
Функция Print выводит содержимое дерева обходом слева направо.
Полученные результаты
Для упорядоченного по возрастанию массива:
Для упорядоченного по убыванию массива:
Для случайного массива:
Таблица результатов:
Размер дерева АВЛ-дерево ИСДП
Контр.
сумма Высота фактическая Теор. оценки для сред. высоты Контр.
сумма Высота фактическая Теор. оценки для сред. высоты
100 5050 5.89 Меньше 9.28 5050 5.80 5.80
200 20100 6.86 Меньше 10.70 20100 6.76 6.76
300 45150 7.43 Меньше 11.53 45150 7.33 7.33
400 80200 7.87 Меньше 12,13 80200 7.75 7.75
500 125250 8.25 Меньше 12,59 125250 8.00 8.00
Анализ
Адельсон - Вельский и Ландис доказали теорему, гарантирующую, что АВЛ-дерево никогда не будет в среднем по высоте превышать ИСДП более, чем на 45% независимо от количества вершин: log(n+1) hАВЛ(n) < 1,44 log(n+2) - 0,328 при n .
Средние высоты соответствуют теоретическим оценкам.
Средняя высота АВЛ-дерева оказалась немного больше, чем средняя высота ИСДП. Это соответствует теоретическим сведениям.
Сумму элементов для деревьев вычислим как сумму элементов арифметической прогрессии.
Для дерева размера 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
