Операции над деревьями

Динамические структуры в виде деревьев широко используются для хранения данных и манипулирования ими. Рассмотрим наиболее распространенные операции, выполняемые с данными, представленными на БД, которые размещаются в динамической памяти.

Создание дерева. Доступ к дереву осуществляется по указателю, объявленному в программе как переменная. Алгоритм включения в дерево отдельных элементов состоит из трех действий:

- поиск места включения;

- получение динамической памяти для элемента и образование связи узла с деревом посредством указателя;

- занесение данных элемента в узел.

Два последних действия не зависят от вида дерева, а поиск места включения элемента в дерево существенно зависит от его вида. После того, как дерево создано, БД поиска легко наращиваются добавлением новых элементов в любой момент времени. Идеально сбалансированные деревья для наращивания с сохранением своих свойств требуют гораздо больших затрат.

Поскольку новые элементы можно включать в дерево поиска в любой момент выполнения программы, то создание дерева сводится к управлению вызовом функции включения элемента.

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

Алгоритм поиска зависит от вида дерева. В идеально сбалансированном дереве поиск приходится проводить обходом вершин дерева в некоторой последовательности. Минимальная длина поиска равна 1; максимальная – n (n – количество узлов дерева); средняя – n /2.

Алгоритм поиска в БД поиска достаточно прост. Поиск осуществляется целенаправленным движением по ветвям дерева. Если ключ поиска равен ключу в вершине, значит, ключ найден и его адрес возвращается через параметр-указатель. Если ключ поиска меньше ключа в вершине, то осуществляется движение вниз влево, в противном случае – вниз вправо. Если в очередной вершине дальнейшее движение вниз невозможно (указатель равен nil), то это означает, что искомого ключа в дереве нет.

Максимальная длина поиска равна высоте дерева.

Вставка элемента в дерево. Особенности операций включения зависит от вида дерева. Вставка элемента в БД поиска, как указывалось выше, состоит из трех действий. Необходимо определить, что делать, если в дереве уже есть элемент с включаемым ключом. В одних случаях такой элемент может отвергаться, в других – включаться, например, если дерево используется для сортировки по ключам. Использование такого элемента также возможно для обновления данных в узле дерева.

Не нашли, что искали? Воспользуйтесь поиском: