Деревья, как динамические структуры данных

Цель работы: изучение организации древовидных структур данных,как динамических списковых структур,и алгоритмов построения, поиска и исключения элементов для бинарных деревьев различной структуры и сильноветвящихся В-деревьев.

Домашнее задание:

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)если T_h_-1 и T_h_-2 -Ф-деревья с высотами (h-1) и (h-2), то T_h =(T_h_-1,x,T_h_-2) также Ф-дерево высотой h; 4)других деревьев Фибоначчи не существует.
6.	Программно построить недвоичное сильноветвящееся В-дерево с помощью алгоритма поиска и включения элемента на страницу(Procedure SearchB). В программе учесть, что при переполнении страницы происходит расщепление страницы и,соответственно реорганизация структуры В-дерева.
7.	Написать и отладить программу исключения элемента из недвоичного сильноветвящегося В-дерева(Procedure UnderFlow). В программе учесть возможность реорганизации структуры В-дерева в результате исключения элемента со страницы.