Читайте также:
|
Динамические структуры в виде деревьев широко используются для хранения данных и манипулирования ими. Рассмотрим наиболее распространенные операции, выполняемые с данными, представленными на БД, которые размещаются в динамической памяти.
Создание дерева. Доступ к дереву осуществляется по указателю, объявленному в программе как переменная. Алгоритм включения в дерево отдельных элементов состоит из трех действий:
- поиск места включения;
- получение динамической памяти для элемента и образование связи узла с деревом посредством указателя;
- занесение данных элемента в узел.
Два последних действия не зависят от вида дерева, а поиск места включения элемента в дерево существенно зависит от его вида. После того, как дерево создано, БД поиска легко наращиваются добавлением новых элементов в любой момент времени. Идеально сбалансированные деревья для наращивания с сохранением своих свойств требуют гораздо больших затрат.
Поскольку новые элементы можно включать в дерево поиска в любой момент выполнения программы, то создание дерева сводится к управлению вызовом функции включения элемента.
Поиск элемента в дереве. Перед операцией поиска элемента в дереве могут ставиться различные цели. Во-первых, определить, имеется ли искомый элемент в дереве или нет. Во-вторых, поиск с целью выборки и обработки данных элемента, тогда результат возвращается в виде адреса вершины. В-третьих, поиск с целью удаления элемента, такой поиск обычно бывает частью операции удаления, а не самостоятельной операцией.
Алгоритм поиска зависит от вида дерева. В идеально сбалансированном дереве поиск приходится проводить обходом вершин дерева в некоторой последовательности. Минимальная длина поиска равна 1; максимальная – n (n – количество узлов дерева); средняя – n /2.
Алгоритм поиска в БД поиска достаточно прост. Поиск осуществляется целенаправленным движением по ветвям дерева. Если ключ поиска равен ключу в вершине, значит, ключ найден и его адрес возвращается через параметр-указатель. Если ключ поиска меньше ключа в вершине, то осуществляется движение вниз влево, в противном случае – вниз вправо. Если в очередной вершине дальнейшее движение вниз невозможно (указатель равен nil), то это означает, что искомого ключа в дереве нет.
Максимальная длина поиска равна высоте дерева.
Вставка элемента в дерево. Особенности операций включения зависит от вида дерева. Вставка элемента в БД поиска, как указывалось выше, состоит из трех действий. Необходимо определить, что делать, если в дереве уже есть элемент с включаемым ключом. В одних случаях такой элемент может отвергаться, в других – включаться, например, если дерево используется для сортировки по ключам. Использование такого элемента также возможно для обновления данных в узле дерева.
Дата добавления: 2015-07-16; просмотров: 65 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Сбалансированные деревья поиска | | | Вставка элемента в АВЛ-дерево |