Конец BinSearch

На первый и последний элементы массива, среди которых надо искать элемент key.

Рекурсивная функция двоичного поиска элемента key в массиве Array. init, fin – указатели

Программа 13 двоичного поиска элемента key в массиве Array

char BinSearch(char key, Array; unsigned init, fin)

char mean; 

unsigned index;

if (fin<init) return 0; else {

index=(init+fin)>>1; mean=Array[index];

if (key==mean) return 1; else

if (key < mean) return BinSearch(key, Array, init, --index); else

return BinSearch(key, Array, ++index, fin);

}

Переменная Array должна быть описана как массив того же типа, что и key. Тип char не обязателен, а может быть выбран любым, но тогда необходимо в строке  программы установить тот же тип!

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

3.4. Деревья двоичного поиска

Рассмотрим следующую задачу. В множество S вставляются и из него удаляются элементы. Время от времени может потребоваться узнать, принадлежит ли данный элемент множеству S или, например, каков в данный момент наименьший элемент в S. Cчитается, что элементы добавляются в S из большого универсального множества, линейно упорядоченного отношением £. Эту задачу можно сформулировать в общем виде как выполнение последовательности, состоящей из операций ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЬ и MIN.

Уже было показано, что для выполнения последовательности операций ВСТАВИТЬ, УДАЛИТЬ и ПРИНАДЛЕЖАТЬ хорошей структурой данных может служить таблица расстановки. Но нельзя найти наименьший элемент, не просмотрев всю таблицу. Структурой данных, пригодной для всех четырех операций, является дерево двоичного поиска.

Определение. Деревом двоичного поиска (binary search tree) для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l(v) Î S так, что

1) l (u) <l (v) для каждого узла и из левого поддерева узла v,

2) l (и) >l (и) для каждого узла и из правого поддерева узла v,

3) для каждого элемента a Î S существует в точности один узел v, для которого l(v)=a.

Из условий 1 и 2 вытекает, что метки этого дерева расположены в соответствии с внутренним порядком. Кроме того, условие 3 следует из условий 1 и 2.

Пример 3.2. На рис. 13 изображено возможное двоичное дерево для выделенных слов алгоритмического языка PASCAL begin, else, end, if, then. Здесь линейным порядком является лексикографический порядок. 

Чтобы выяснить, принадлежит ли элемент а множеству S, представленному деревом двоичного поиска, надо сравнить а с меткой корня. Если метка корня равна а, то очевидно, что a Î S. Если а меньше метки корня, то надо перейти к левому поддереву корня (если оно есть). Если а больше метки корня, то надо перейти к правому поддереву корня. Если а присутствует в дереве, его местоположение будет, в конце концов, обнаружено. В противном случае процесс окончится, когда надо будет найти несуществующее левое или правое поддерево.

Алгоритм 14. Просмотр дерева двоичного поиска

Вход. Дерево Т двоичного поиска для множества S и элемент а.

Выход. "Да" (1), если a Î S, и "нет" (0) в противном случае.

Метод. Если дерево Т пусто, выдать "нет." В противном случае пусть r – корень дерева Т. Тогда алгоритм состоит из единственного вызова BinTreeSearch (Arrаy, r) рекурсивной процедуры BinTreeSearch, приведенной ниже.

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

Хотя приведенное в главе 1 определение понятия дерева требует, чтобы дерево содержало хотя бы один узел, а именно корень, во многих алгоритмах далее пустое дерево (дерево без узлов) будет трактоваться как двоичное.

Структура бинарного дерева построена из узлов. Узел дерева содержит поле данных и два поля с указателями. Поля указателей называются, обычно, левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево соответственно. Значение указателя NULL указывает на то, что у узла нет соответствующего сына. Если у узла оба указателя равны NULL, то это – листовой узел. На рис. 14 показаны структура одного узла (а) и способ соединения этих узлов в дерево двоичного поиска (б, в).

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

Очевидно, что алгоритм 14 достаточен для выполнения операции Member (а, S). Более того, его легко модифицировать так, чтобы он выполнял операцию Insert (а, S). Если дерево пусто, строится корень с меткой а. Если дерево непусто, а элемент, который надлежит вставить, не обнаружен в дереве, то процедуре ПОИСК не удается найти сына в строке 3 или 5. Вместо того чтобы выдать "нет" в строке 4 или 6 соответственно, для этого элемента строится новый узел там, где должен был быть отсутствующий сын.

Дата добавления: 2014-01-07