Н.С. Гриценко, Ю.С. Белов
6
else
{
if (n < top->data)
top = FindElement(top->leftChild, n,
stop);
if (n > top->data)
top = FindElement(top->rightChild, n,
stop);
}
}
Это связано с тем, что «барьер» должен указываться при созда-
нии дерева, т. е. если дерево существует, то оно считается пустым
при наличии всего лишь одного элемента — «барьера». В связи с
этим при написании алгоритма условия окончания поиска будут сле-
дующие:
1) найден требуемый элемент;
2) достигнут элемент, являющийся «барьером» данного дерева.
Двоичное дерево поиска с «барьером» структурно объединило в
себе двоичное дерево поиска и поиск с «барьером» в массиве. Алго-
ритм поиска с «барьером» в массиве заключается в том, что в конец
массива к
n
элементам добавляется (
n
+ 1)-й элемент — «барьер» и
поиск продолжается до тех пор, пока не найден требуемый элемент
либо не достигнут «барьер». Результаты поиска с «барьером» в неот-
сортированном массиве и поиска с «барьером» в двоичном дереве
поиска одинаковы: либо элемент найден, либо достигнут «барьер»,
однако построение дерева в данном случае оправдано выигрышем во
времени поиска, что особенно заметно при большом числе элемен-
тов. Недостаток заключается лишь в том, что алгоритм построения
двоичного дерева поиска с «барьером» более трудоемкий, чем алго-
ритм построения неотсортированного массива с «барьером». Необ-
ходимо при добавлении узла в дерево учитывать его местоположение
в зависимости от значения ключа, т. е. выполнять операции сравне-
ния со значениями ключей текущего узла и ключей его поддеревьев,
тогда как при построении массива элементы добавляются последова-
тельно, независимо от значений их ключей.
Исследовав структуру двоичного дерева поиска с «барьером», мож-
но сделать вывод, что по построению оно разительно отличается от ши-
роко известных видов деревьев. Особенности его построения вполне
оправданны и уместны. Основную часть логики функционирования и
программного описания данного дерева составляет обычное двоичное
дерево поиска, что позволяет легче понять алгоритм его работы.
ЛИТЕРАТУРА
Вирт Н.
Алгоритмы и структуры данных.
Москва, ДМК Пресс, 2010, 272 с.
Axo А., Хопкрофт Д., Ульман Д.
Структуры данных и алгоритмы.
Москва, Издательский дом «Вильямс», 2003, 384 с.
