Идеально сбалансированное дерево поиска (исдп)



Скачать 102.43 Kb.
Дата05.06.2016
Размер102.43 Kb.
ТипЛабораторная работа
Лабораторная работа 1

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

 

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



 

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

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

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

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

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

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



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

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

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

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

 


Размердерева

ИСДП

Контр.

сумма


Высота

Теор. оценка для средней высоты

Средняя

высота


100

 

 

 

 

200

 

 

 

 

300

 

 

 

 

400

 

 

 

 

500

 

 

 

 

 

 

Лабораторная работа 2

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

 

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



 

1.    Разработать подпрограмму построения случайного дерева поиска (СДП).

2.    Построить СДП из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

3.    Для построенного дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и СДП. Заполнить таблицу и проанализировать полученные результаты:

 


Размер дерева

СДП

ИСДП

Контр.

сумма


Высота

Средняя

высота


Контр.

сумма


Высота

Средняя

высота


100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

 

Лабораторная работа 3

Тема: Сбалансированные по высоте деревья поиска (АВЛ)

 

Цель работы: Изучение процесса программного построения АВЛ-дерева.



 

1.    Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.

2.    Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

3.    Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу и проанализировать полученные результаты:

 


Размер дерева

АВЛ-дерево

ИСДП

Контр.

сумма


Теор. оценки для сред. высоты

Средняя

высота


Контр.

сумма


Теор. оценки для сред. высоты

Средняя

высота


100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

 

Лабораторная работа 4

Тема: Двоичное Б-дерево поиска (ДБД)

 

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



 

1.    Разработать подпрограмму построения ДБ-дерева для массива целых чисел

2.    Построить ДБ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.

3.    Для построенного ДБ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту (как для двоичного дерева) и высоту ДБ-дерева как количество уровней, сравнить их с аналогичными характеристиками АВЛ-дерева. ДБ-дерево необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу и проанализировать полученные результаты:

 


Размердерева

АВЛ-дерево

ДБД

Контр.

сумма


Сред.

высота


Контр.

сумма


Кол-во уровней

Теор. оценки для высоты ДБД

Сред.

высота для дв. дерева.



100

 

 

 

 

 

 

200

 

 

 

 

 

 

300

 

 

 

 

 

 

400

 

 

 

 

 

 

500

 

 

 

 

 

 

 

Лабораторная работа 5

Тема: Дерево оптимального поиска (приближенные алгоритмы)

 

Цель работы: Изучение процесса программного построения почти оптимальных деревьев поиска.



1.    Реализовать программно алгоритмы А1 и А2 для построения почти оптимальных деревьев поиска.

2.    Построить почти оптимальные деревья поиска из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные) с помощью алгоритмов А1 и А2, распечатать их обход слева направо.

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

Размердерева

А1

А2

Контр.

сумма


Средне-

взвешенная высота



Контр.

сумма


Средне-

взвешенная высота



100

 

 

 

 

200

 

 

 

 

300

 

 

 

 

400

 

 

 

 

500

 

 

 

 

 
Каталог: tasks
tasks -> Методические указания по выполнению контрольной работы По дисциплине «Математическое моделирование»
tasks -> Введении дается краткое обоснование тем, указывается ее актуальность и теоретическая значимость; отмечается состояние разработки проблемы в литературе, ставится цель и задачи исследования. В основной части
tasks -> Темы эссе по философии
tasks -> С. Г. Кара-Мурза //Социально-гуманитарные знания. 2000. № С. 21-24. Юревич, А. В. Звёздный час гуманитариев: социогуманитарная наука в современной России /А. В. Юревич //Вопросы философии. 2003
tasks -> Профиль: Музыкальное искусство Задания 2015-2016 уч года Этап: I (заочный)
tasks -> Правила работы в группе: Активное участие каждого школьника. Умение договариваться и выслушивать мнение каждого. Основные требования к работе в группе
tasks -> Контрольное задание №2
tasks -> Расчетная работа №1: в практикуме по статистике (авт. Шмойлова Р. А.), вложенном в пункте «Рекомендуемая литература»
tasks -> Вариант Состав группы


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница