Введение, Определение двоичного дерева поиска - Исследование и программная реализация алгоритмов теории графов

Цель данной работы - реализовать добавление слова в словарь на основе заданного алфавита на языке программирования высокого уровня. Основной задачей является сортировка строк в словарном порядке. В качестве "инструмента" для выполнения данной задачи будет выступать двоичное дерево поиска.

1. Теоретические сведения

Определение двоичного дерева поиска

Для решения задачи сортировки мы будем использовать так называемое двоичное дерево поиска.

Двоичным деревом поиска называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовем их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами. В нашей задаче считается, что одной вершине соответствует только один элемент - слово. Поэтому мы будем использовать понятия ключа вершины и данных вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так же будем понимать под вставкой вершины добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Именно ключ используется во всех операциях сравнения элементов. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение. Двоичное дерево поиска позволяет выполнять следующие основные операции:

    - Поиск вершины по ключу; - Определение вершин с минимальным и максимальным значением ключа; - Переход к предыдущей или последующей вершине, в порядке, определяемом ключами; - Вставка вершины; - Удаление вершины.

Двоичное дерево может быть логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня - первым уровнем, их потомки - вторым, и т. д. Глубина дерева это его максимальный уровень. Понятие глубины также может быть описано в терминах пути, то есть глубина дерева есть длина самого длинного пути от корня до листа, если следовать от родительской вершины до потомка. Каждую вершину дерева можно рассматривать как корень поддерева, которое определяется данной вершиной и всеми потомками этой вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить как о рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его сбалансированностью, то есть с максимальной разницей между глубиной левого и правого поддерева среди всех вершин. Имеется два крайних случая - сбалансированное бинарное дерево (где каждый уровень имеет полный набор вершин) и вырожденное дерево, где на каждый уровень приходится по одной вершине. Вырожденное дерево эквивалентно связанному списку.

Двоичное дерево поиска может быть использовано для реализации таких абстракций, как сортированный список, словарь (набор соответствий "ключ-значение"), очередь с приоритетами и так далее.

При реализации дерева помимо значения ключа (key) и данных также хранятся три указателя: на родителя (net), левого (left) и правого (right) потомков. Если родителя или потомка нет, то указатель хранит нулевое (NULL, NIL) значение.

Похожие статьи




Введение, Определение двоичного дерева поиска - Исследование и программная реализация алгоритмов теории графов

Предыдущая | Следующая