СибГУТИ Лабораторная работа 1 Вариант 18 Структуры и алгоритмы обработки данных (часть 2) скачать бесплатно

ЛАБОРАТОРНАЯ РАБОТА 1

Тема: Идеально сбалансированное дерево поиска (ИСДП) и случайное дерево поиска (СДП) 

Цель работы: Изучение процесса программного построения ИСДП и СДП.
 

1. Написать подпрограммы для вычисления характеристик двоичного дерева, которые определяют:

o размер дерева;

o высоту дерева;

o среднюю высоту дерева;

o контрольную сумму данных в вершинах дерева;

o Проверить их работу на конкретном примере.
 

2. Запрограммировать обход двоичного дерева слева направо и вывести на экран получившуюся последовательность данных.
 

3. Разработать подпрограмму поиска вершины с заданным ключом в двоичном дереве поиска.
 

4. Разработать подпрограмму построения идеально сбалансированного дерева поиска (ИСДП) для массива случайных чисел, а также логическую функцию для определения является ли данное двоичное дерево деревом поиска. Построить ИСДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенных деревьев вычислить размер, контрольную сумму, высоту и среднюю высоту, используя разработанные функции. Заполнить таблицу (таблица 1) и проанализировать полученные результаты.
 

5. Разработать подпрограмму построения случайного дерева поиска (СДП). Построить СДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо. Для построенного дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и СДП. Заполнить таблицу (таблица 1) и проанализировать полученные результаты.

Таблица 1 - Результаты работы программ

Размер дерева СДП ИСДП

Контр. 

сумма Высота фактическая Теор. оценки для сред. высоты Контр.

сумма Высота фактическая Теор. оценки для сред. высоты

100

200

300

400

500

 

Описание

Структура TNode хранит информацию о вершине дерева: информационное поле, указатель на левую вершину и указатель на правую вершину.

Функция Array1 формирует упорядоченный по возрастанию массив.

Функция Array2 формирует упорядоченный по убыванию массив.

Функция Array3 формирует случайный массив.

Функция NewNode создает новую вершину.

Функция CreateISDP создает ИСДП.

Функция CreateSDP создает СДП.

Функция TreeSize вычисляет размер дерева.

Функция TreeHeight вычисляет высоту дерева.

Функция TreeAverageHeight вычисляет среднюю высоту дерева.

Функция Sum вычисляет контрольную сумму данных в вершинах дерева.

Функция IsSearchTree определяет, является ли дерево деревом поиска.

Функция SearchKey ищет в дереве вершину по ключу и возвращает 1 в случае успеха. 

Функция Print выводит содержимое дерева обходом слева направо.
 

Полученные результаты

ИСДП

СДП. Для упорядоченного по возрастанию массива:

СДП. Для упорядоченного по убыванию массива:

СДП. Для случайного массива:

 

Таблица результатов для упорядоченного по возрастанию или убыванию массива:

Размер дерева СДП ИСДП

Контр. 

сумма Высота фактическая Теор. оценки для сред. высоты Контр.

сумма Высота фактическая Теор. оценки для сред. высоты

100 5050 50.50 50.50 5050 5.80 5.80

200 20100 100.50 100.50 20100 6.76 6.76

300 45150 150.50 150.50 45150 7.33 7.33

400 80200 200.50 200.50 80200 7.75 7.75

500 125250 250.50 250.50 125250 8.00 8.00

Таблица результатов для случайного массива:

Размер дерева СДП

Контр. 

сумма Высота фактическая Теор. оценки для сред. высоты

100 5050 7.88 log100 = 6.64

200 20100 9.05 log200 = 7.64

300 45150 9.61 log300 = 8.23

400 80200 9.69 log400 = 8.64

500 125250 10.61 log500 = 8.97

 

Анализ

Для упорядоченного массива СДП имеет максимально возможную среднюю высоту, т.к. все вершины – только левые или только правые поддеревья.

ИСДП строится только из упорядоченного по возрастанию массива.

Очевидно, что ИСДП гораздо эффективнее при поиске, т.к. средние высоты меньше, чем у СДП, сформированного любым способом.

Построенные деревья являются деревьями поиска.

Сумму элементов для деревьев вычислим как сумму элементов арифметической прогрессии.

Для дерева размера 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