Цель работы: изучение организации древовидных структур данных,как динамических списковых структур,и алгоритмов построения, поиска и исключения элементов для бинарных деревьев различной структуры и сильноветвящихся В-деревьев.
Домашнее задание:
1. Изучить организацию двоичного дерева, как динамической структуры данных.
2. Освоить алгоритмы поиска и включения в идеально сбалансированное двоичное дерево и стандартные алгоритмы обхода таких деревьев.
3. Изучить организацию и алгоритмы поиска и включения элемента в сбалансированное АVL-дерево;стандартные повороты для балансировки АVL-деревьев, алгоритм исключения элемента из АVL-дерева.
4. Изучить организацию недвоичного сильноветвящегося В-дерева и алгоритмы построения с поиском и включением элемента; реорганизацию В-дерева при расщеплении страниц: алгоритм исключения элемента из В-дерева.
Порядок выполнения работы
1. Открыть проект Delphi - Struct.
2. На главной форме (Main Form) установить компонент, управляющий всем проектом – главное меню, и назвать первый пункт «Лаб. раб. №1». Организовать вертикальную составляющую к этому пункту «Задача 1».
3. Добавить к проекту модуль с формой TreeStruct, которая должна появляться на экране при выборе пункта меню «Задача 1». Убедитесь в том, что ваша управляющая конструкция в проекте работает.
4. Установить на форму модуля TreeStruct компоненты, обеспечивающие ввод исходных данных, управляющую командную кнопку, и компоненты для вывода результатов на экране – для реализации программного приложения в соответствии с вариантом задания таблицы 1.1. Для отображения организованной вами древовидной структуры используйте визуальный компонент библиотеки VCL - TreeView,расположенный на странице Win32 указанной библиотеки.
5. В обработчике события onClick командной кнопки на языке Object Pascal написать фрагмент программы для ввода исходных данных, обработки их по алгоритму, соответствующему варианту вашего задания (таблица 1.1) и вывода результатов в соответствующий объект (TreeView) на форму модуля TreeStruct. Отладить программу и продемонстрировать результаты преподавателю.
6. Составить отчет, в котором должно быть:
a. а) текст задания;
b. б)распечатка текста модуля TreeView;
c. в)отображение формы с результатами работы модуля;
d. г)блок-схема алгоритма работы модуля.
7. Защитить работу преподавателю.
Таблица 6.1
| № вар. | Текст задания |
| 1. | а)Организовать и отладить программу для построения и печати идеально сбалансированного двоичного дерева (Function Tree, Function PrintTree). б)Запрограммировать и отладить алгоритм обхода построенного бинарного дерева слева направо (в качестве примера построить и обойти дерево, отображающее заданное арифметическое выражение с бинарными операциями). |
| 2. | а)Организовать программно двоичное дерево с помощью процедуры поиска и включения ключа (Search). б)Написать и отладить программу для поэлементного вывода значений узлов построенного дерева обходом дерева слева направо(Inorder). Замечание: при правильной организации бинарного дерева с целочисленными ключами в результате отображения ключей при обходе в порядке Inorder, должна получиться отсортированная в порядке возрастания последовательность ключей. |
| 3. | а)Написать и отладить программу, которая позволит построить идеально сбалансированное двоичное дерево (с целочисленными ключами). б)Организовать процедуру удаления элемента из организованного двоичного дерева(Procedure Delete). |
| 4. | Организовать и отладить программу для построения и отображения сбалансированного AVL-дерева(высоты в поддеревьях отличаются не более, чем на 1) с помощью алгоритма поиска и включения элемента; учесть необходимость балансировки AVL-дерева с использованием LL, RR, LR, RL-поворотов. |
| 5. | Программно организовать построение дерева Фибоначчи(Ф-дерево), как пример AVL-дерева. Замечание: дерево Фибоначчи определяется следующим образом: 1) пустое дерево есть Ф-дерево высотой 0; 2)единственная вершина есть дерево высотой 1; 3)если Th-1 и Th-2 -Ф-деревья с высотами (h-1) и (h-2), то Th =(Th-1,x,Th-2) также Ф-дерево высотой h; 4)других деревьев Фибоначчи не существует. |
| 6. | Программно построить недвоичное сильноветвящееся В-дерево с помощью алгоритма поиска и включения элемента на страницу(Procedure SearchB). В программе учесть, что при переполнении страницы происходит расщепление страницы и,соответственно реорганизация структуры В-дерева. |
| 7. | Написать и отладить программу исключения элемента из недвоичного сильноветвящегося В-дерева(Procedure UnderFlow). В программе учесть возможность реорганизации структуры В-дерева в результате исключения элемента со страницы. |
Контрольные вопросы
1. Определение дерева, как динамической структуры данных.
2. Бинарное дерево, описание структуры узла в таком дереве.
3. Правило идеально сбалансированного двоичного дерева.
4. Три стандартных обхода деревьев(примеры).
5. Правило сбалансированности для AVL-дерева.
6. Стандартные повороты, используемые для балансировки AVL-дерева.
7. Что такое сильноветвящееся дерево и каково правило его роста?
8. Что такое порядок В-дерева?
9. Когда происходит расщепление страницы в В-дереве и на что это влияет?
Лабораторная работа № 7
(4 часа)
