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

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

 

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

 

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. Когда происходит расщепление страницы в В-дереве и на что это влияет?