Введение, Определение двоичного дерева поиска - Исследование и программная реализация алгоритмов теории графов
Цель данной работы - реализовать добавление слова в словарь на основе заданного алфавита на языке программирования высокого уровня. Основной задачей является сортировка строк в словарном порядке. В качестве "инструмента" для выполнения данной задачи будет выступать двоичное дерево поиска.
1. Теоретические сведения
Определение двоичного дерева поиска
Для решения задачи сортировки мы будем использовать так называемое двоичное дерево поиска.
Двоичным деревом поиска называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовем их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами. В нашей задаче считается, что одной вершине соответствует только один элемент - слово. Поэтому мы будем использовать понятия ключа вершины и данных вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так же будем понимать под вставкой вершины добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Именно ключ используется во всех операциях сравнения элементов. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение. Двоичное дерево поиска позволяет выполнять следующие основные операции:
- - Поиск вершины по ключу; - Определение вершин с минимальным и максимальным значением ключа; - Переход к предыдущей или последующей вершине, в порядке, определяемом ключами; - Вставка вершины; - Удаление вершины.
Двоичное дерево может быть логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня - первым уровнем, их потомки - вторым, и т. д. Глубина дерева это его максимальный уровень. Понятие глубины также может быть описано в терминах пути, то есть глубина дерева есть длина самого длинного пути от корня до листа, если следовать от родительской вершины до потомка. Каждую вершину дерева можно рассматривать как корень поддерева, которое определяется данной вершиной и всеми потомками этой вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить как о рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его сбалансированностью, то есть с максимальной разницей между глубиной левого и правого поддерева среди всех вершин. Имеется два крайних случая - сбалансированное бинарное дерево (где каждый уровень имеет полный набор вершин) и вырожденное дерево, где на каждый уровень приходится по одной вершине. Вырожденное дерево эквивалентно связанному списку.
Двоичное дерево поиска может быть использовано для реализации таких абстракций, как сортированный список, словарь (набор соответствий "ключ-значение"), очередь с приоритетами и так далее.
При реализации дерева помимо значения ключа (key) и данных также хранятся три указателя: на родителя (net), левого (left) и правого (right) потомков. Если родителя или потомка нет, то указатель хранит нулевое (NULL, NIL) значение.
Похожие статьи
-
Рис. 7 Пример двоичного дерева поиска Двоичное дерево поиска (binary search tree, BST) -- это двоичное дерево, для которого выполняются следующие...
-
Базовый интерфейс двоичного дерева поиска состоит из трех операций: - FIND(K) -- поиск узла, в котором хранится пара (key, value) с key = K. - INSERT(K,...
-
ДВОИЧНЫЙ ПОИСК, АВЛ-Дерево - Структуры и алгоритмы обработки данных
Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берем средний элемент отсортированного массива и сравниваем с ключом X. Возможны...
-
Рис. 9 Пример B+ дерева, связывающего ключи 1-7 с данными d1-d7. Связи (выделены красным) позволяют быстро обходить дерево в порядке возрастания ключей....
-
ИЕРАРХИЧЕСКАЯ МОДЕЛЬ ДАННЫХ ИМД основана на понятии деревьев, состоящих из вершин и ребер. Вершине дерева ставится в соответствие совокупности атрибутов...
-
Теория Графов, 1.1 Историческая справка - Определение кратчайшего пути в графе
Граф дискретный программирование 1.1 Историческая справка ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический...
-
В наше время все большее количество компаний, стремясь к повышению эффективности и прибыльности бизнеса пользуются цифровыми (автоматизированными)...
-
Сравнение алгоритмов поиска оптимальных решений в агентных системах
Аннотация Рассмотрены основные понятия теории агентов: тип агентов, основные задачи агентов, суть поиска решения агентом в пространстве состояния...
-
Заключение - Определение кратчайшего пути в графе
Теория графов находит широкое применение в различных областях науки и техники: Графы и информация Двоичные деревья играют весьма важную роль в теории...
-
Программные модули проекта, Представление графа в памяти ЭВМ - Алгоритмы нескольких махов
Все программы были реализованы на языке С++ на персональной ЭВМ с операционной системой Windows. Каждая программа представляет собой консольное...
-
Модернизация обобщенного алгоритма кластеризации состоит в использовании вместо обычных бинарных деревьев сбалансированных бинарных деревьев(B+ tree)....
-
Введение - Визуализация графа цитирования
В данной работе рассматриваются методы автоматической и полуавтоматической визуализации графов цитирования на плоскости. Визуализация графов на плоскости...
-
2.2 Нахождение кратчайших путей в графе - Определение кратчайшего пути в графе
Начальные понятия Будем рассматривать ориентированные графы G = < V , E> , дугам которых приписаны веса. Это означает, что каждой дуге < U ,...
-
Заключение - Разработка программы для реализации редактора временных графов синхронизации
Результатом выполнения задания является реализованный редактор временных графов синхронизации (класс временных сетей Петри), соответствующий задачам,...
-
В работе возникает необходимость выбора предметной области, в которой будет тестироваться каскадный классификатор. Главными вопросами на данном этапе...
-
Перед написанием основных алгоритмов были разработаны модули-классы, отвечающие за геометрические примитивы. Так как визуализация производится в...
-
Кластеризация (или кластерный анализ) -- это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться...
-
Понятие Data Mining Средства Data Mining включают в себя очень широкий класс различных технологий и инструментов. Средства Data Mining на рынке...
-
Алгоритмы распознавания интервальных и единичных интервальных графов [2,5-7] основываются на специальном упорядочивании вершин графа и проверке...
-
1.2 Основные термины и теоремы теории графов - Определение кратчайшего пути в графе
1. Граф - Пара объектов G = ( X, Г ),где Х - конечное множество, а Г - конечное подмножество прямого произведения Х*Х. При этом Х называется множеством...
-
Реализация визуализации анимации алгоритма - Визуализация графа цитирования
При работе алгоритма расположения вершин графа необходимо анимировать изменения графа в режиме реального времени. Для этого используется специальная...
-
Для запуска кластеризации пользователю нужно ввести 4 параметра: А) Название ODBC драйвера с созданным подключением. Как создать Такое подключение,...
-
Модель данных - Модели серверов баз данных
Модель данных - это множество правил, посредством которых производится создание структуры данных в базе данных, производятся операции над данными, а...
-
Основные термины теории баз данных - БД (База данных) - совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы...
-
Построение дерева - Деревья решений
Пусть нам задано некоторое множество T, содержащее объекты, каждый из которых характеризуется m атрибутами, причем один из них указывает на...
-
Визуализация кластерной структуры - Визуализация графа цитирования
Следующей задачей, после расстановки вершин на плоскости, должна быть решена задача визуализации кластерной структуры. В данном разделе мы рассмотрим...
-
Введение - Один алгоритм сжатия изображения
Сжатие цифровых изображений -- одна из задач цифровой обработки изображений, наряду с сегментацией, морфологической обработкой, распознаванием образов и...
-
Основные определения, термины и понятия - Визуализация графа цитирования
1. Граф - совокупность множества вершин и наборов пар вершин, называемых ребрами. 2. Ориентированный граф - граф в котором пары вершин в ребрах...
-
Деревья решений - это способ представления иерархической, последовательной структуры организованной по определенным правилам, где каждому объекту...
-
Выбор средств реализации информационной системы Названные в параграфе 1.4. настоящей работы задачи могут быть решены тремя типами средств автоматизации:...
-
Итерационные алгоритмы разрезания графа на куски
Лекция Итерационные алгоритмы разрезания графа на куски Суть Итерационных Алгоритмов Разрезания Графов заключается в выборе первого случайного разрезания...
-
Силовые алгоритмы для иерархически-кластеризованных графов - Визуализация графа цитирования
На данный момент мы рассмотрели алгоритм для отрисовки некластеризованных графов и их улучшения. Теперь необходимо изучить подходы, которые используются...
-
Введение - Система циклового программного управления
Система циклового программного управления исполнительными механизмами (ИМ) технологического оборудования в машиностроении является одной из типовых,...
-
Улучшения классических силовых алгоритмов - Визуализация графа цитирования
Первым улучшением является добавление псевдо-гравитационной силы [11]. Эта сила притягивает все вершины к центру рабочей области. Обычно она линейна...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ - Структуры и алгоритмы обработки данных
В ходе выполнения курсовой работы, помимо основных алгоритмов, потребовалось реализовать также несколько вспомогательных, необходимых для корректной...
-
Для того, чтобы использовать симметричные алгоритмы шифрования, необходимо безопасно обменяться ключами. Протокол Диффи - Хеллмана позволяет двум и более...
-
Введение - Алгоритмы нескольких махов
Теория графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике и социологии, а также в генетике,...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Физическая модель данных При разработке структуры базы данных важным процессом является нормализация. Нормализация - это удаление избыточных данных из...
Введение, Определение двоичного дерева поиска - Исследование и программная реализация алгоритмов теории графов