28. Алгоритмы поиска. Основные понятия и определения. Задача поиска. Бинарный поиск элемента упорядоченного массива и связного упорядоченного списка.
См. 27 вопрос по основным понятиям.
Для упорядоченной таблицы можно предложить более эффективный алгоритм поиска, известный под названием метод бинарного или двоичного поиска (binary search). Искомый ключ сравнивается с ключом среднего элемента в таблице. Результат сравнения позволяет определить, в какой половине таблицы следует продолжить поиск: если ключи совпали, то алгоритм заканчивается успешно, если искомый ключ больше ключа среднего элемента, то для дальнейшего поиска выбирают правую половину, если меньше – левую. Затем к выбранной половине таблицы рекурсивно применяется тот же метод.
Можно представить процедуру бинарного поиска в виде бинарного дерева: поиск осуществляет последовательное сравнение ключей с элементами, индексы которых представлены в узлах бинарного дерева. Последовательность индексов зависит только от размера N. Неудачный поиск приведет в один из внешних (квадратных) узлов.
Для таблиц, размер которых на 1 меньше степени двойки, дерево имеет вид:
Для таблиц произвольной длины последовательность не столь симметрична, что видно на примере дерева:
Алгоритм бинарного поиска относится к рекурсивным алгоритмам типа «разделяй и властвуй». Для рекурсивного описания алгоритма левую и правую границы поиска (l и r соответственно) следует рассматривать как примеры процедуры. Для выполнения поиска необходимо при вызове процедуры задать значения ее формальных параметров l как 1 и r как N, а закончить рекурсию при условии, что левый индекс стал больше правого (l>r). Рекурсивная функция бинарного поиска RBinSearch представлена в следующем примере:
Function RBinSearch (x: Tkey; var T: table; l,r: Index): index;
Var i: index;
Begin
If l>r then RBinSearch:=N+1
Else
Begin
i:=(l+r) div 2;
if T[i].key=x then RBinSearch:=i
else if T[i].key<x then
RBinSearch:= RBinSearch(x,T,i+1,r)
Else RBinSearch:= RBinSearch(x,T,l,i-1);
End;
End;
Устранение концевой рекурсии в процедуре бинарного поиска выполняется так: в нерекурсивной функции BinSearch нужная половина таблицы выбирается за счет изменения левого или правого индексов, и итерации продолжаются до тех пор, пока либо не будет найден элемент, либо левый индекс не станет больше правого.
Function RBinSearch (x: Tkey; var T: table;): index;
Var i,r,l: index;
Begin
L:=1; r:=N;
While (l<=r) and (x<>T[i].key) do
Begin
i:=(l+r) div 2;
if x>T[i].key then l:=i+1;
else r:=i-1;
end;
if x=T[i].key then BinSearch:=i;
else BinSearch:=N+1;
end;
Обе функции возвращают номер искомого ключа или N+1, если ключ не найден.
29. Деревья. Основные понятия и определения. Области применения деревьев. Обход дерева.
Дерево(tree) – совокупность элементов, называемых узлами, и отношений, образующих иерархическую структуру узлов. Дерево может быть либо в нем имеется один специально обозначенный узел, называемый корнем дерева, а остальные узлы содержатся в непересекающихся множествах Т1, Т2,..Tm, каждое из которых в свою очередь является деревом. Деревья Т1, Т2,.. Tm называют поддеревьями данного корня.