Сбалансированные по высоте деревья поиска
Изучение и анализ процесса программного построения дерева поиска. Ознакомление с описанной структурой содержащей данные одного узла дерева для определения дерева в программе. Рассмотрение и характеристика сравнения результатов с теоретическими оценками.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | практическая работа |
| Язык | русский |
| Дата добавления | 20.12.2021 |
| Размер файла | 104,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Тема: «Сбалансированные по высоте деревья поиска (АВЛ)»
Введение
Цель работы: Изучение процесса программного построения АВЛ-дерева.
1. Постановка задачи
1.Разработать подпрограмму построения АВЛ-дерева для массива целых чисел.
2.Построить АВЛ-дерево из 100, 200,…, 500 вершин (данные в вершинах произвольные, но все различные). Распечатать обход дерева слева направо.
3.Для построенного АВЛ-дерева вычислить размер, контрольную сумму, высоту и среднюю высоту, сравнить их с аналогичными характеристиками ИСДП. ИСДП необходимо строить для той же последовательности данных, что и АВЛ-дерево. Заполнить таблицу и проанализировать полученные результаты.
2. Описание используемых алгоритмов
Дерево поиска называется сбалансированным по высоте, или АВЛ - деревом, если для каждой его вершины высоты левого и правого поддеревьев отличаются не более чем на 1.
Заметим, что ИСДП является также и АВЛ - деревом. Обратное утверждение не верно.
АВЛ-дерево никогда не будет в среднем по высоте превышать ИСДП более, чем на 45% независимо от количества вершин.
log(n+1) ? hАВЛ(n) < 1,44 log(n+2) - 0,328 при n.
Рассмотрим, что может произойти при включении новой вершины в сбалансированное по высоте дерево. Пусть r - корень АВЛ-дерева, у которого имеется левое поддерево (ТL) и правое поддерево (TR). Если добавление новой вершины в левое поддерево приведет к увеличению его высоты на 1, то возможны три случая:
1)если hL = hR, то ТL и TR станут разной высоты, но баланс не будет нарушен;
2)если hL < hR, то ТL и TR станут равной высоты, т. е. баланс даже улучшится;
3)если hL > hR, то баланс нарушиться и дерево необходимо перестраивать.
Введём в каждую вершину дополнительный параметр Balance (показатель баланса), принимающий следующие значения:
-1, если левое поддерево на единицу выше правого;
0, если высоты обоих поддеревьев одинаковы;
1, если правое поддерево на единицу выше левого.
Если в какой-либо вершине баланс высот нарушается, то необходимо так перестроить имеющееся дерево, чтобы восстановить баланс в каждой вершине. Для восстановления баланса будем использовать процедуры поворотов АВЛ-дерева.
LL - поворот
LR - поворот
RR - поворот
RL - поворот
Добавление новой вершины в АВЛ-дерево происходит следующим образом. Вначале добавим новую вершину в дерево так же как в случайное дерево поиска (проход по пути поиска до нужного места). Затем, двигаясь назад по пути поиска от новой вершины к корню дерева, будем искать вершину, в которой нарушился баланс (т. е. высоты левого и правого поддеревьев стали отличаться более чем на 1). Если такая вершина найдена, то изменим структуру дерева для восстановления баланса с помощью процедур поворотов.
Для определения дерева в программе описана структура содержащая данные одного узла дерева:
typedef struct TreeNode
{
int Key;
TreeNode * left;
TreeNode * right;
unsigned char height; //Для AVL
int Balance; //Для DBD
int size; //Для идеально сбалансированного
} TreeNode;
Данная структура подходит для реализации всех типов деревьев, с которыми необходимо работать в программах. Для реализации алгоритмов написаны 2 набора функций. программный дерево поиск
3. Результат работы программы
Для решения поставленной задачи разработана программа «L2». Программа последовательно строит ИСДП из 100, 200,…, 500 вершин, затем последовательно строит AVL-дерево из 100, 200,…, 500 вершин. Для деревьев выполняются все необходимые замеры, результаты выводятся в текстовые файлы AVL.txt и ISDP.txt.
На рисунке 1 показан вывод программы на консоль.
Рисунок 1 - Вывод программы на консоль
4. Анализ и сравнение полученных результатов с теоретическими оценками
На основе полученных данных заполним таблицу.
|
Размер дерева |
АВЛ-дерево |
ИСДП |
|||||
|
Контр. сумма |
Высота фактическая |
Теор. оценки для сред. высоты |
Контр. сумма |
Высота фактическая |
Теор. оценки для сред. высоты |
||
|
100 |
1558626 |
8 |
4.86 |
1558626 |
7 |
4.80 |
|
|
200 |
3275687 |
9 |
5.89 |
3275687 |
8 |
5.76 |
|
|
300 |
4797179 |
10 |
6.41 |
4797179 |
9 |
6.33 |
|
|
400 |
6446496 |
10 |
6.82 |
6446496 |
9 |
6.74 |
|
|
500 |
8043283 |
11 |
7.17 |
8043283 |
9 |
7.00 |
Вывод
Мы построили AVL-дерево и ИСДП для наборов данных одного и того же размера. Фактически полученная высота AVL-дерева во всех случаях больше, чем высота ИСДП, но при этом разница в высоте не значительна.
Размещено на Allbest.ru
...Подобные документы
Сбалансированные многоходовые деревья поиска. Исследование структуры B+-дерева, её основные операции. Доказательство их вычислительной сложности. Утверждение о высоте. Поиск, вставка, удаление записи, поиск по диапазону. B+-деревья в системах баз данных.
курсовая работа [705,5 K], добавлен 26.12.2013Рассмотрение нелинейных динамических структур данных в виде бинарного дерева. Построение дерева двоичного поиска. Реализация трех обходов дерева, выведение обходов на экран компьютера. Разработка текста программы. Симметричноправая прошивка дерева.
контрольная работа [81,6 K], добавлен 14.12.2011Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [22,8 K], добавлен 16.09.2013Разработка программы на языке С#, которая будет заниматься построением бинарного дерева для исходных данных и их редактированием, поиском информации о товарах по заданному ключу. Графические схемы алгоритмов поиска и удаления элемента бинарного дерева.
курсовая работа [796,9 K], добавлен 22.02.2016Понятие и базовые свойства ориентированного дерева. Обходы (способы нумерации вершин) в глубину и ширину. Представление бинарных графов с помощью указателей и массива, скобочной записи, списком прямых предков. Сбалансированность дерева двоичного поиска.
презентация [330,6 K], добавлен 19.10.2014Описание процедуры выбора структуры хранения данных. Программная реализация одномерного неоднородного массива. Представление бинарного дерева в виде динамической структуры данных. Изучение способов поиска в упорядоченном дереве. Содержание базы данных.
практическая работа [850,0 K], добавлен 16.04.2015Работа с компонентом TTreeView, служащим для отображения иерархических данных в виде дерева. Обеспечение заполнения дерева, очистка, анализ и редакция элементов. Процедура удаления элемента. Демонстрация работы программы, исходные данные и результаты.
лабораторная работа [788,6 K], добавлен 11.01.2012Структура компилятора PascalABC.NET. Структура дерева и примеры узлов. Упрощенный синтаксис записи модулей. Объявление имен, совпадающих с ключевыми словами. Генерация узла семантического дерева. Сериализация и десериализация узлов семантического дерева.
курсовая работа [1,8 M], добавлен 18.12.2011Организация бинарного дерева. Порядок размещения данных в нелинейных структурах. Организация пользовательского интерфейса. Симметричный обход дерева. Параллельная работа обработчиков исключений. Расширенный графический интерфейс и его возможности.
курсовая работа [426,0 K], добавлен 24.06.2013Организация таблицы идентификаторов, ее содержание и назначение. Метод бинарного дерева и цепочек. Проектирование лексического анализатора и схема распознавателя. Построение дерева вывода, синтаксический анализатор. Анализ результатов работы программы.
курсовая работа [1,0 M], добавлен 25.12.2014Описание структуры бинарного дерева поиска на языке C# среды Visual Studio. Требования к интерфейсу пользователя, структуре данных и программным средствам. Компоненты программных средств, результаты тестирования, диаграммы вариантов использования классов.
курсовая работа [968,2 K], добавлен 26.01.2013Древовидная структура – "Бинарное дерево поиска", его структура и взаимосвязь основных компонентов, исследование в глубину. Описание разработанного программного продукта. Главные функции редактирования исходных данных и принципы работы с файлами.
курсовая работа [1,6 M], добавлен 13.06.2014Основные понятия теории грамматик простого и операторного предшествования, алгоритмы синтаксического разбора предложения для классов КС-грамматик; разработка дерева вывода для грамматики входного языка в форме Бэкуса-Наура с указанием шагов построения.
лабораторная работа [28,0 K], добавлен 24.07.2012Понятие вложенных циклов, одномерных и двумерных массивов в программировании. Матрицы и основные действия с ними. Иерархические записи, понятие дерева. Операции с двоичными деревьями, рекурсия, включение и удаление узла. Алгоритм поиска по дереву.
отчет по практике [507,1 K], добавлен 27.12.2011Составление программы lab3.exe, реализующей удаление элемента из списка перед указанным методом и его сортировку по возрастанию. Описание предикатов, используемых в программе. Проверка на корректный вывод информации. Программа для обхода бинарного дерева.
контрольная работа [559,3 K], добавлен 20.05.2012Пример дерева решений. Анализ древовидной структуры данных. Предикторные (зависимые) переменные как признаки, описывающие свойства анализируемых объектов. Решение задач классификации и численного прогнозирования с помощью деревьев классификации.
презентация [391,1 K], добавлен 09.10.2013Исследование особенностей основных файловых менеджеров, разработанных под операционную систему Windows. Изучение порядка заполнения элементов бинарного дерева. Обзор приложения, реализующего графический интерфейс доступа пользователя к папкам и файлам.
курсовая работа [2,9 M], добавлен 11.07.2012Аналитический обзор системы управления курсами Moodle, программное построение ее модулей. Разработка структурной схемы и базы знаний экспертной системы. Создание дерева вопросов и выбор алгоритма поиска решений. Анализ возможных угроз и защита информации.
дипломная работа [534,7 K], добавлен 14.12.2013Рассмотрение и анализ моделей и алгоритмов семантического поиска в мультиагентной системе поддержки пользователей. Ознакомление с интерфейсом чата с ботом. Изучение и характеристика экспериментальных оценок релевантности и пертинентности запросов.
дипломная работа [3,0 M], добавлен 13.10.2017Структура оптимальных бинарных деревьев поиска. Рекурсивное решение; вычисление математического ожидания стоимости поиска; выбор ключа, который приводит к его минимальному значению. Вычисленные с помощью процедуры Optimal_BST для распределения ключей.
доклад [1,2 M], добавлен 14.11.2011
