Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Рассмотрим пример, представленный на рис. 5.7. Допустим нам необходимо найти элемент с ключом 52. Первым сравниваемым элементом будет 49. Так как 49<52, то ищем следующую середину среди элементов, расположенных выше 49. Это число 86. 86>52, поэтому теперь ищем 52 среди элементов, расположенных ниже 86, но выше 49. На следующем шаге обнаруживаем, что очередное значение середины равно 52. Мы нашли элемент в массиве с заданным ключом.

Программы на псевдокоде и Паскале:

Low = 1
hi = n
while (low <= hi) do
mid = (low + hi) div 2
if key = k(mid) then
search = mid
return
endif
if key < k(mid) then
hi = mid — 1
else low = mid + 1
endif
endwhile
search = 0
return
low := 1;
hi := n;
while (low <= hi) do
begin
mid := (low + hi) div 2;
if key = k[mid] then
begin
search := mid;
exit;
end;
if key < k[mid]
then hi := mid — 1
else low := mid + 1;
end;
search := 0;
exit

При key = 101 запись будет найдена за три сравнения (в последовательном поиске понадобилось бы семь сравнений).
Если С — количество сравнений, а n — число элементов в таблице, то
С = log2n.
Например, n = 1024.
При последовательном поиске С = 512, а при бинарном
С = 10.
Можно совместить бинарный и индексно-последовательный поиск (при больших объемах данных), учитывая, что последний также используется при отсортированном массиве.

5.7. Поиск по бинарному дереву

Назначение его в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список, как правое на рис. 5.8.

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. придется перебирать N/2 элементов.
Наибольшего эффекта использования дерева достигается в том случае, когда дерево сбалансировано.В этом случае для поиска придотся перебрать не больше log2N элементов.
Строго сбалансированное дерево — это дерево, в котором каждый узел имеет левое и правое поддеревья, отличающиеся по уровню не более, чем на единицу.
Поиск элемента в бинарном дереве называется бинарным поиском по дереву.
Такое дерево называют деревом бинарного поиска.
Суть поиска заключается в следующем. Анализируем вершину очередного поддерева. Если ключ меньше информационного поля вершины, то анализируем левое поддерево, больше — правое.
Пусть задан аргумент key
p = tree
whlie p <> nil do
if key = k(p) then
search = p
return
endif
if key < k(p) then
p = left(p)
else
p = right(p)
endif
endwhile
search = nil
return
p := tree;
whlie p <> nil do
begin
if key = p^.k then
begin
search := p;
exit;
end;
if key < p^.k then
p := p^.left
else
p := p^.right;
end;
search := nil;

5.8  Поиск со вставкой (с включением)

Для вставки элемента в дерево, сначало нужно осуществить поиск в дереве по заданному ключу. Если такой ключ имеется, то программа завершается, если нет, то происходит вставка.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники