 |
Балансировка дерева поиска
|
|
|
|
Рассмотрим алгоритм балансировки. Существует теорема:
Все случаи нарушения балансировки при включении сводятся к двум вариантам.
Вариант 1
Рассмотрим рисунок на следующей странице. На данном рисунке «А» и «В» элементы, с которыми производится манипуляции. Произведем балансировку.
 |  | ||||||
|
|
Подняв элемент «А» и его левое поддерево мы устранили несбалансированность.
Вариант 2
 | ||||||
|
|
Обратим внимание, что в обоих случаях все преимущества элементов производились по вертикали, так как по горизонтали дерево не перемещается. Полученные деревья сохранили свойства дерева поиска. После каждого включения/удаления элемента следует рассчитывать критерий сбалансированности для каждого элемента.
ДОСТОИНСТВА:
быстрота поиска элементов - максимальное время поиска меньше, чем в каком-нибудь другом.
НЕДОСТАТКИ:
после каждого включения/удаления элемента требуется расчет критерия и возможность сбалансирования.
вывод:
Эти деревья выгодно использовать в тех базах данных, где основной и возможно единственной операцией является поиск. Примером такой БД может служить оглавление диска.
ПОСТРОЕНИЕ ДЕРЕВА ПОИСКА ПО ВЕРОЯТНОСТИ ОБРАЩЕНИЯ К ЭЛЕМЕНТАМ.
Пусть даны элементы бинарного дерева и вероятности запроса к ним:
Поместим в корень тот элемент, который нужен чаще всего. Затем, соблюдая правила дерева поиска, добавим к нему остальные элементы так, чтобы элемент с большей вероятностью запроса был бы ближе к корню.
|
|
|
 |
Данное дерево является деревом поиска, но оно не является сбалансированным. Максимальное время поиска будет хуже, чем в сбалансированном дереве. Но среднее время поиска будет лучше, чем в сбалансированном дереве, так как чаще всего требуемые элементы находятся ближе к корню.
Рабочее задание
Разработать и отладить программу, реализующую обработку иерархической структуры. Обеспечить возможность вставки и удаления элементов, просмотр дерева, используя меню для выбора операции. Вид иерархической структуры и дополнительные операции задаются по вариантам.
Варианты
| № | Вид иерархической структуры | Дополнительные операции |
| дерево поиска | прямой обход, после добавления элементов выполнить балансировку | |
| дерево поиска | прямой, обратный, концевой обходы | |
| прошитое дерево | прямой обход | |
| бинарное дерево | обратный обход, преобразовать в дерево поиска | |
| дерево поиска | концевой обход, вычислить критерий сбалансированности | |
| дерево поиска | прямой обход, вычислить критерий сбалансированности и выполнить балансировку при необходимости | |
| бинарное дерево | с помощью дерева привести выражение к бесскобочной логике: (a*b+c)/(a-(d+a)) | |
| бинарное дерево | с помощью дерева привести выражение к бесскобочной логике: ((d-c)*b)/a+(a+b)*d | |
| бинарное дерево | с помощью дерева привести выражение к бесскобочной логике: ((a/(b+c))*(a-d*c))/b | |
| дерево поиска | Построить дерево поиска по вероятности обращения к элементам. Элементы и вероятность запроса к ним задается пользователем | |
| дерево поиска | Набрать статистику и перестроить дерево по вероятности обращения к элементам | |
| дерево поиска | отсортировать массив с помощью дерева; | |
| бинарное дерево | небинарный лес преобразовать в бинарное дерево; | |
| дерево поиска | обратный обход, после добавления элементов организовать балансировку | |
| дерево поиска | концевой обход, после добавления элементов организовать балансировку | |
| бинарное дерево | прямой обход, преобразовать в дерево поиска | |
| прошитое дерево | обратный обход | |
| бинарное дерево | концевой обход, преобразовать в дерево поиска | |
| прошитое дерево | концевой обход | |
| дерево поиска | обратный обход, вычислить критерий сбалансированности |
|
|
|
Лабораторная работа №5
СЕТЕВЫЕ СТРУКТУРЫ.
Теоретический материал.
На рисунке изображена произвольная сетевая структура. Хорошо заметно, что, в отличие от иерархических структур, в сетевых структурах более свободная дисциплина связей между элементами.
 |
Необходимо при разработке сетевой структуры определить дисциплину связей. Определим ее как
i: j
где i - количество ссылок на данный элемент;
j - количество допустимых ссылок данного элемента.
Рассмотрим формат элемента сетевой структуры:
| inf | S1 | … | Sj |
Иногда используют запись вида
М:3
Это значит, что в данной структуре каждый элемент может ссылаться на 3 других, а количество ссылок на каждый элемент не ограничено. Такое возможно, поскольку количество ссылок на каждый элемент не отражается в формате элемента.
Рабочее задание
Разработать и отладить программу, реализующую сетевую структуру с заданной дисциплиной связей.
Варианты
| № варианта | Вид сети | № варианта | Вид сети |
| 5:2 | 2:5 | ||
| 4:3 | M:3 | ||
| 3:3 | 4:5 | ||
| 1:6 | 4:4 | ||
| 3:5 | 3:2 | ||
| М:4 | M:2 | ||
| 5:4 | 4:2 | ||
| 5:3 | 5:5 | ||
| 2:4 | 6:1 | ||
| 3:4 | 2:3 |
Примечание: М – количество входящих связей неограниченно.
|
|
|
