Балансировка дерева поиска
⇐ ПредыдущаяСтр 2 из 2
Рассмотрим алгоритм балансировки. Существует теорема: Все случаи нарушения балансировки при включении сводятся к двум вариантам.
Вариант 1 Рассмотрим рисунок на следующей странице. На данном рисунке «А» и «В» элементы, с которыми производится манипуляции. Произведем балансировку.
Подняв элемент «А» и его левое поддерево мы устранили несбалансированность.
Вариант 2
Обратим внимание, что в обоих случаях все преимущества элементов производились по вертикали, так как по горизонтали дерево не перемещается. Полученные деревья сохранили свойства дерева поиска. После каждого включения/удаления элемента следует рассчитывать критерий сбалансированности для каждого элемента. ДОСТОИНСТВА: быстрота поиска элементов - максимальное время поиска меньше, чем в каком-нибудь другом. НЕДОСТАТКИ: после каждого включения/удаления элемента требуется расчет критерия и возможность сбалансирования. вывод: Эти деревья выгодно использовать в тех базах данных, где основной и возможно единственной операцией является поиск. Примером такой БД может служить оглавление диска.
ПОСТРОЕНИЕ ДЕРЕВА ПОИСКА ПО ВЕРОЯТНОСТИ ОБРАЩЕНИЯ К ЭЛЕМЕНТАМ. Пусть даны элементы бинарного дерева и вероятности запроса к ним:
Поместим в корень тот элемент, который нужен чаще всего. Затем, соблюдая правила дерева поиска, добавим к нему остальные элементы так, чтобы элемент с большей вероятностью запроса был бы ближе к корню.
Данное дерево является деревом поиска, но оно не является сбалансированным. Максимальное время поиска будет хуже, чем в сбалансированном дереве. Но среднее время поиска будет лучше, чем в сбалансированном дереве, так как чаще всего требуемые элементы находятся ближе к корню.
Рабочее задание Разработать и отладить программу, реализующую обработку иерархической структуры. Обеспечить возможность вставки и удаления элементов, просмотр дерева, используя меню для выбора операции. Вид иерархической структуры и дополнительные операции задаются по вариантам. Варианты
Лабораторная работа №5 СЕТЕВЫЕ СТРУКТУРЫ.
Теоретический материал. На рисунке изображена произвольная сетевая структура. Хорошо заметно, что, в отличие от иерархических структур, в сетевых структурах более свободная дисциплина связей между элементами.
Необходимо при разработке сетевой структуры определить дисциплину связей. Определим ее как i: j где i - количество ссылок на данный элемент; j - количество допустимых ссылок данного элемента.
Рассмотрим формат элемента сетевой структуры:
Иногда используют запись вида М:3 Это значит, что в данной структуре каждый элемент может ссылаться на 3 других, а количество ссылок на каждый элемент не ограничено. Такое возможно, поскольку количество ссылок на каждый элемент не отражается в формате элемента.
Рабочее задание Разработать и отладить программу, реализующую сетевую структуру с заданной дисциплиной связей. Варианты
Примечание: М – количество входящих связей неограниченно.
Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|