Деревья поиска

Если данные организованы как структура дерева, алгоритм поиска сводится к алгоритму, просматривающему все узлы дерева. Для ведения поиска существуют два основных алгоритма поиска: поиск в глубину и поиск в ширину.

Поиск в глубину. При поиске в глубину каждая ветвь дерева просматривается слева направо.

Для двоичных деревьев алгоритм поиска имеет простую рекурсивную структуру (рис. 7.1):

Рис. 7.1 — Схема поиска по двоичному дереву

DEPTHFIRST: procedure(TREE);

declare 1 TREE,

2 KEY,

2 ARGUMENT, /* данные */

2 RightSon, /* ноль, если нет сына*/

2 LeftSon; /* ноль, если нет сына */

if TREE = null then return;

if текущий узел не KEY then do;

call DEPTHFIRST(LtftSon);

call DEPTHFIRST(RightSon);

end;

end DEPTHFIRST;

Заметим, что если дерево упорядочено таким образом, что LeftSon имеет ключ, величина которого меньше, чем значение корневого узла, а величина ключа для RightSon больше, чем значение корневого узла, то такой алгоритм аналогичен алгоритму двоичного поиска.

Поиск в ширину. Это алгоритм поиска, при котором просматривается каждый уровень в направлении сверху вниз (рис. 7.2).

Рис. 7.2 — Поиск в ширину

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

BREADTHFIRST: procedure(solution);

declare 1 TREE,

2 ARGUMENT, /* данные */

2 SONS(N); /* произвольные деревья */

declare (solution, NextStep) set of TREE;

/* переход вниз для каждого уровня */

do while (solution ¹ 0);

NextStep = {TREE.SONS(I) для всех I и TREE

в solution};

call BREADTHFIRST(NextStep);

end;

end BREADTHFIRST;

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

Поиск с возвратом. Для многих алгоритмов часто требуется перебор возможных вариантов решения задачи. Один из таких способов перебора называется поиском с возвратом.

Алгоритм:

Вызвать первую часть;

do while (не окончится);

вызвать следующую часть;

do while (нет возможности продолжить);

Вернуться на предыдущий уровень;

Проверить возможность альтернативного решения

для этого уровня;

end;

end;

Алгоритм поиска в глубину является примером поиска с возвратом:

Начать с корневого узла;

do while (существуют не просмотренные узлы);

Перейти к узлу «левый сын», если возможно;

Иначе перейти к узлу «правый брат»;

do while (нет узлов «левый сын» и «правый брат);

Перейти к узлу «отец»;

Перейти к узлу «правый брат», если можно;

end;

end;