Особенности структуры и функционирования двоичного дерева поиска с «барьером»
3
Рис. 1
.
Схема хранения двоичного дерева поиска
При рассмотрении алгоритма поиска в обычном двоичном дереве
поиска условий окончания поиска будет два [5]:
1) найден требуемый элемент;
2) пройден путь от вершины дерева до листа, но требуемый эле-
мент не найден.
В последнем случае алгоритм вернет NULL как указатель на пу-
стой элемент, что и будет соответствовать отсутствию искомого эле-
мента в имеющемся дереве [6]:
Tree *FindElement(Tree *top, int n)
{
if (top == NULL)
return NULL;
if (top->data == n)
return top;
else
{
if (n < top->data)
top = FindElement(top->leftChild, n);
if (n > top->data)
top = FindElement(top->rightChild, n);
}
}
Возможна ситуация, когда при отсутствии заданного элемента в
дереве необходимо вернуть на пустой элемент не указатель, а уста-
новленное значение, не зависящее от того, какой элемент требова-
лось найти. При решении данной задачи рационально воспользовать-
ся двоичным деревом поиска с «барьером».
Топологически дерево поиска с «барьером» представляет собой
двоичное дерево, листья которого ссылаются не на пустой, а на заранее
установленный элемент, в основе которого лежит та же структура, что и
в основе любого из узлов рассматриваемого дерева (рис. 2,
а
). Значения
поля-ключа и информационного поля такого элемента установлены за-
