18,19.Не рекурсивные алгоритмы обхода бинарного дерева.

20.Поиск в упорядоченных таблицах. Последовательный поиск в массиве.

21.Поиск в упорядоченных таблицах. Двоичный поиск в массиве. Фибоначчиев поиск. Интерполяционный поиск.

Очень часто приходится решать следующую задачу: найти элемент с нужным значением ключа. Эту задачу приходится решать с использованием массивов, списков, деревьев. Эта задача решается по-разному в случае неупорядоченных или упорядоченных по возрастанию ключей элементов. В последнем случае можно не просматривать все элементы, а доходить только до элемента с ключом большим, чем требуемый.

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

Двоичный поиск:

Применяется для упорядоченных массивов. При двоичном поиске используется метод деления пополам. Поставим задачу так: найти наименьший индекс (указатель) компоненты списка со значением ключа, равным Х.

Алгоритм:

VAR A: ARRAY[1..N] OF INTEGER;

X: INTEGER;

VAR I: INTEGER;

BEGIN

I := 1; J := N;

REPEAT

K := (I + J) DIV 2;

IF X > A[K] THEN I := K + 1 ELSE J := K - 1

UNTIL (A[K] = X) OR (I > J)

END.

Число просмотров m = log2N.

При N = 100: последовательный поиск выполнится за 50 просмотров (m = 50), двоичный за 6,62 (m = 6,62)

22. Поиск в линейном списке.

Как и в файле, поиск ведется строго последовательно. Он заканчивается либо когда элемент найден, либо когда достигнут конец списка.

Алгоритм

1. B←true; P←BeginList

2. While (P≠nil) and B do

3. If P^.key>=x then B←false

4. Else P←P^.next

5. End while

6. If (B=true) then return nil

7. Else return P

23.Двоичное дерево поиска. Свойства. Основные операции.

Двоичное дерево поиска – это двоичное дерево, с каждым из внутренних узлов которого, связан ключ, удовлетворяющий условиям:

1. Все ключи в левом поддереве меньше родительского узла меньше родительского

2. Все ключи в правом поддереве больше родительского

Для поиска среди N элементов может потребоваться не более log₂N сравнений. Если дерево идеально сбалансировано.

В этом преимущество дерева перед линейным списком, в котором для поиска может потребоваться N сравнений

Основные операции:

1. Включить узел в бинарное дерево поиска

2. Удалить узел

3. Выполнить поиск данных

4. Выполнить обход

5. Определить, пусто ли дерево

6. Создать

7. Уничтожить

Поиск Эл-та в 2-ном дереве:

Tree_Search(T,K).

1.i f (t=nil) or (k=T^.key) then return T

2.i f k<T^.key then return Tree_Search(T^.left,k)

3. else return Tree_Search(T^.right,k)

Iterative_Tree_Search(t,k).

1.while (T<>nil) and (k<>T^.key) do

2.if k<T^.key then TT^.left

3.else TT^.right; returnT.

Min and Max.

Мин. Ключ в дереве поиска можно найти по УК-лю leftот корня, пока зн-е очередного УК-ля не станет = 0.

Tree_Minimum(T).

1.while T^.left<>nil do TT^.left

2.returnT.

Для макс. Нужно заменить в алг-ме Tree_Minimum(T)leftнаright.

Добавление и удаление эл-та.

Эти операции сохр-ют сво-во упорядоченности. Добавление: алг-м вставляет нов. Эл-т в соответствии с бин. поиском.

Tree_Insert(T,z).

1.if T=nil then new(T)

2.T^.keyz T^.leftnil T^.rightnil

3.else if z<T^.key then Tree_Insert(T^.left,z)

4.else Tree_Insert(T^.right)

5.returnT.

Затраты операций пропорциональны высоте дерева. Удаление: возможны 3 случая.

1.удаляемая вершина не имеет сыновей.

2.удаляемая вершина имеет 1-ого сына.

3.вершина имеет 2-х сыновей.

Delete(T,k).

1.if T<> nil then if k<T^.key then Delete(T^.left,k)

2.else if k>T^.key then Delete(T^.right,k)

3.elseесли узел не имеет сыновей:

4.if (T^left=nil) and (T^.right=nil) then q:=T;T:=nil; Dispose(q).

5.elseесли узел имеет сыновей:

6.else if (T^.left=nil) then q:=T; T:=T^.right; Dispose(q).

7.else (if T^.right=nil) then q:=T; T:=T^.left; Dispose(q).

8.else Del(T^.right,T).

Del(T,q),T-ук-ль на корень дерева,q-ук-ль на замен-ю вершину.

1.if T^.left=nil then q^.keyT^.key; q1T TT^.right

2.Dispose(q1); return

3.else Del(T^.left, q).

Представление 2-ых деревьев с помощью ук-лей: узлы дерева опр-ся как переменные с фикс. Структурой, а связи м-ду ними с помощью УК-лей. Т.к. степень дерева=2, то число УК-лей тоже 2. Ссылка на пустое поддерево – nil.

Type pNode=^Node; Node=record

Info:T0; left, right:pNode

End;