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

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

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

Для двоичных деревьев алгоритм поиска имеет простую рекурсивную структуру (рис. 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;

7.4.3 Стратегия распределения памяти

Одним из типов поиска являются задачи по распределению памяти (наиболее характерны они при создании ОС), однако во многих прикладных алгоритмах эти задачи возникают при создании прикладных программ, работающих с большим объемом данных. Если до начала обработки полный объем данных, которые подлежат обработке, неизвестен, то используется общий подход для распределения областей этой памяти согласно заданным требованиям.

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

Первое возможное размещение. Последовательно просматриваются области памяти, пока не найдется первая, достаточная для размещения. Вся область организована в список и упорядочена по адресам (рис. 7.3).

Рис. 7.3 — Схема распределения памяти

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

Данный способ самый простой, однако поскольку занятие области памяти осуществляется после нахождения первой области, достаточной для размещения данных, память становится фрагментной.

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

Сопрягаемые области памяти. Областями памяти являются N цепочек размером 2^N каждая. Если область размером 2^K отсутствует, а имеется свободная область размером 2^K+1, то она разбивается на две сопрягаемые области размером 2^K. После того как области освободятся, они рассматриваются как области размером 2^K, которые можно объединить в область размером 2^K+1.