3. Программная реализация дерева поиска

В разделе описания переменных зададим формат элемента дерева:

Type Tree=^T;

T=record;

Inf:integer;

L,R,:Tree;

End;

Для навигации по дереву используем рекурсивную процедуру:

Procedure find_tree(var P:Tree; x:integer);

Begin

If (P<>nil) then

Begin

If P^.inf=x then …{нашли элемент};

If (P^.inf>x) then find_tree(P^.L,x);

If (P^.inf<x) then find_tree(P^.R,x);

End;

End;

4. Сбалансированные деревья.

Дерево является сбалансированным, если для каждого элемента высота левого и правого поддеревьев различаются не более чем на «I».

ПРИМЕР: Дано дерево поиска. Рассчитаем критерий сбалансированности для каждого элемента.

Ни в одном элементе разница в высоте левого и правого поддеревьев не превышает «I». Следовательно, дерево сбалансировано.

Критерий сбалансированности - это разница в высоте левого и правого поддеревьев.

Балансировка дерева поиска

Рассмотрим алгоритм балансировки. Существует теорема:

Все случаи нарушения балансировки при включении сводятся к двум вариантам.

Вариант 1

Рассмотрим рисунок на следующей странице. На данном рисунке «А» и «В» элементы, с которыми производится манипуляции. Произведем балансировку.

до балансировки

после балансировки

Подняв элемент «А» и его левое поддерево мы устранили несбалансированность.

Вариант 2

до балансировки

после балансировки

Обратим внимание, что в обоих случаях все преимущества элементов производились по вертикали, так как по горизонтали дерево не перемещается. Полученные деревья сохранили свойства дерева поиска. После каждого включения/удаления элемента следует рассчитывать критерий сбалансированности для каждого элемента.

ДОСТОИНСТВА:

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

НЕДОСТАТКИ:

после каждого включения/удаления элемента требуется расчет критерия и возможность сбалансирования.

вывод:

Эти деревья выгодно использовать в тех базах данных, где основной и возможно единственной операцией является поиск. Примером такой БД может служить оглавление диска.

ПОСТРОЕНИЕ ДЕРЕВА ПОИСКА ПО ВЕРОЯТНОСТИ ОБРАЩЕНИЯ К ЭЛЕМЕНТАМ.

Пусть даны элементы бинарного дерева и вероятности запроса к ним:

Поместим в корень тот элемент, который нужен чаще всего. Затем, соблюдая правила дерева поиска, добавим к нему остальные элементы так, чтобы элемент с большей вероятностью запроса был бы ближе к корню.

Данное дерево является деревом поиска, но оно не является сбалансированным. Максимальное время поиска будет хуже, чем в сбалансированном дереве. Но среднее время поиска будет лучше, чем в сбалансированном дереве, так как чаще всего требуемые элементы находятся ближе к корню.

Рабочее задание

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

Варианты

№	Вид иерархической структуры	Дополнительные операции
1	дерево поиска	прямой обход, после добавления элементов выполнить балансировку
2	дерево поиска	прямой, обратный, концевой обходы
3	прошитое дерево	прямой обход
4	бинарное дерево	обратный обход, преобразовать в дерево поиска
5	дерево поиска	концевой обход, вычислить критерий сбалансированности
6	дерево поиска	прямой обход, вычислить критерий сбалансированности и выполнить балансировку при необходимости
7	бинарное дерево	с помощью дерева привести выражение к бесскобочной логике: (a*b+c)/(a-(d+a))
8	бинарное дерево	с помощью дерева привести выражение к бесскобочной логике: ((d-c)*b)/a+(a+b)*d
9	бинарное дерево	с помощью дерева привести выражение к бесскобочной логике: ((a/(b+c))*(a-d*c))/b
10	дерево поиска	Построить дерево поиска по вероятности обращения к элементам. Элементы и вероятность запроса к ним задается пользователем
11	дерево поиска	Набрать статистику и перестроить дерево по вероятности обращения к элементам
12	дерево поиска	отсортировать массив с помощью дерева;
13	бинарное дерево	небинарный лес преобразовать в бинарное дерево;
14	дерево поиска	обратный обход, после добавления элементов организовать балансировку
15	дерево поиска	концевой обход, после добавления элементов организовать балансировку
16	бинарное дерево	прямой обход, преобразовать в дерево поиска
17	прошитое дерево	обратный обход
18	бинарное дерево	концевой обход, преобразовать в дерево поиска
19	прошитое дерево	концевой обход
20	дерево поиска	обратный обход, вычислить критерий сбалансированности

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

СЕТЕВЫЕ СТРУКТУРЫ.