Программа 20: Бинарный поиск (в таблице символов, основанной на массиве)

 

Эта реализация функции поиска (search) использует процедуру рекурсивного би­нарного поиска. Для выяснения, присутствует ли заданный ключ v в отсортирован­ном массиве, функция сначала сравнивает v с элементом, находящимся в средней позиции. Если v меньше, он должен быть в первой половине массива, а если боль­ше — то во второй.

Массив должен быть отсортированным. Эта функция может рассматриваться в ка­честве замены функции search из программы 18, которая обеспечивает динами­ческую сортировку во время вставки. Можно было бы также добавить конструктор таблицы символов, который получал бы массив в качестве аргумента, а затем стро­ил бы таблицу символов на основе элементов входного массива и сортировал бы ее для целей поиска с применением одной из стандартных процедур сортировки.

 

private:

Item searchR(int 1, int r, Key v)

(if (1 > r) return nullltem;

int m = (l+r)/2;

if (v == st[m].key()) return st[m];

if (1 == r) return nullltem;

if (v < st[m].key())

return searchR(l, m-1, v);

else return searchR (m+l, r, v);

}

public:

Item search (Key V)

{ return searchR(0, N- l, v);

 

Последовательность сравнений, выполняемых ал­горитмом бинарного поиска, предопределена: конк­ретная последовательность используется в зависимо­сти от значения искомого ключа и значения N. Сравнения могут быть описаны в виде структуры би­нарного дерева, подобной приведенной на рис. 31.

 

 

Рисунок.31. Последовательность сравнений при бинарном поиске

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

В бинарном поиске ис­пользуется один путь в дереве, тогда как при сорти­ровке слиянием — все пути. Это дерево является статическим и неявным.

На верхней диаграмме показан поиск в файле, состоящем из 15 элементов, проиндексированных от 0 до 14. Мы просматриваем средний элемент (индекс 7), затем (рекурсивно) просматриваем левое поддерево, если искомый элемент меньше него, и правое — если он больше. Каждый поиск соответ­ствует пути, проходящему по дереву сверху вниз; на­пример, поиск элемента, который располагается между элементами 10 и 11, потребовал бы просмот­ра элементов 7, 11, 9, 10. Для файлов с размерами, которые не являются на 1 меньше степени числа 2, последовательность не столь симметрична, что не­сложно заметить на нижней диаграмме, нарисован­ной для 12 элементов.

Одно из возможных усовершенствований бинарного поиска — более точное пред­положение о размещении ключа поиска в текущем интервале (вместо слепого срав­нения его со средним элементом на каждом шаге). Эта тактика имитирует способ по­иска имени в телефонном справочнике или слова в словаре: если искомая запись начинается с буквы, находящейся в начале алфавита, поиск выполняется вблизи на­чала книги, но если она начинается с буквы, находящейся в конце алфавита, поиск выполняется в конце книги. Для реализации данного метода, называемого интерпо­ляционным поиском (interpolation search), программу 20 потребуется изменить следую­щим образом: оператор

заменяется на оператор

Для обоснования изменения отметим, что выражение равнозначно вы­ражению : мы вычисляем середину интервала, добавляя клевой граничной точке половину размера интервала. Использование интерполяционного поиска сво­дится к замене в этой формуле коэффициента — ожидаемой позицией ключа — а именно (v ~ ) / (k_r — k_l), где и означают значения a[l].key() и а[r].кеу() соот­ветственно. При этом предполагается, что значения ключей являются числовыми и равномерно распределенными.

Можно показать, что при интерполяционном поиске в файлах с произвольными ключами для каждого поиска (попадания или промаха) используется менее lglgN сравнений. Доказательство этого утверждения выходит далеко за рамки этой книги. Эта функция растет очень медленно и на практике ее можно считать постоянной: если N равно 1 миллиарду, то lglgN < 5. Таким образом, любой элемент можно найти, выпол­нив только несколько обращений (в среднем) — это существенное достижение по срав­нению с бинарным поиском. Для ключей, которые распределены не вполне произволь­но, производительность интерполяционного поиска еще выше. Действительно, граничным случаем является метод поиска с использованием индексирования по клю­чам.

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

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

Бинарные деревья поиска

 

Для решения проблемы излишне высоких затрат на вставку в качестве основы для реализации таблицы символов используется явная древовидная структура[3].

Лежащая в основе структура данных позволяет разрабатывать алгоритмы с высокой средней производительностью выполнения операций search, insert, selectиsort в табли­цах символов. Этот метод используется во множестве приложений и в компьютерных науках считается одним из наиболее фундаментальных.

Определяющее свойство дерева (tree) заключается в том, что каждый узел указывается только одним другим узлом, называемым родительским (parent). Определя­ющее свойство бинарного дерева — наличие у каждого узла левой и правой связей. Связи могут указывать на другие двоичные деревья или на внешние (external) узлы, которые не имеют связей. Узлы с двумя связями называются также внутренними (internal) узлами. Для выполнения поиска каждый внутренний узел имеет также элемент со значением клю­ча, а связи с внешними узлами называются нулевыми (null) связями. Значения ключей во внутренних узлах сравниваются в ключом поиска и управляют протеканием поиска.

Лемма 17: Дерево бинарного поиска (BST) — это бинарное дерево, с каждым из внутренних узлов которого связан ключ, причем ключ в любом узле больше (или равен) ключам и во всех узлах левого поддерева этого узла и меньше (или равен) ключам во всех узлах правого поддерева этого узла.

 

В программе 21 BST-деревья используются для реализации операций search, insert, constructиcount. В первой части реализации узлы в BST-дереве определяются как содержащие элемент (с ключом), левую и правую связи. Кроме того, для обеспе­чения энергичной реализации операции count программа поддерживает поле, содер­жащее количество узлов в дереве. Левая связь указывает на BST-дерево с элемента­ми с меньшими (или равными) ключами, а правая — на BST-дерево с элементами с большими (или равными) ключами.

Программа 21: Таблица символов на базе дерева бинарного поиска.

В этой реализации функции search и insert используют приватные рекурсивные функции searchR и insertR, которые непосредственно отражают рекурсивное опре­деление BST-дерева. Обратите внимание на использование аргумента ссылки в функции insertR. Ссылка head указывает на корень дерева.

 

template Cclass Item, class Key> class ST {

private:

struct node

{ Item item; node *1, *r; node(Item x)

{ item = x; 1 = 0; r = 0; }

};

typedef node *link;

link head;

Item nullltem;

Item searchR (link h, Key v)

{ if (h == 0} return nullltem;

Key t = h->itern.key();

if (v == t) return h->item;

if (v < t) return searchR(h->l, v);

else return searchR(h-> r, v);

}

void insertR (links h, Item x)

{ if (h = 0)

{ h = new node(x);

return; }

if (x.key() < h->item.key()) insertR(h->l, x); else insertR(h->r, x);

}

public:

ST(int maxN)

{ head = 0; }

Item search(Key v)

{ return searchR(head, v);}

void insert(Item x)

{ insertR(head, x); }

};

 

При наличии этой структуры рекурсивный алго­ритм поиска ключа в BST-дереве становится очевид­ным: если дерево пусто, имеет место промах при поиске; если ключ поиска равен ключу в корне, имеет место попадание при поиске. В противном случае выполняется поиск (рекурсивно) в соответ­ствующем поддереве. Функция searchR в программе 21 непосредственно реализует этот алгоритм. Мы вызываем рекурсивную подпрограмму, которая при­нимает дерево в качестве первого аргумента и ключ в качестве второго, начиная с корня дерева и иско­мого ключа. На каждом шаге гарантируется, что никакие части дерева, кроме текущего поддерева, не могут содержать элементы с искомым ключом.

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

На диаграмме в верхней части рис. 32 проиллю­стрирован процесс поиска для примера дерева. Начи­ная с верхней части, процедура поиска в каждом узле приводит к рекурсивному вызову для одного из до­черних узлов этого узла; таким образом, поиск опре­деляет путь по дереву. В случае попадания при поис­ке путь завершается в узле, содержащем ключ, а в случае промаха путь завершается во внешнем узле, как показано на средней диаграмме на рис. 32

В программе 21 используется 0 связей для пред­ставления внешних узлов и приватные данные — член head, который является ссылкой на корень дере­ва. Для конструирования пустого BST-дерева значе­ние head устанавливается равным 0. Можно было бы также использовать фиктивный узел в корне и еще один для представления всех внешних узлов в различ­ных комбинациях, подобных рассмотренным для связных списков.

 

Рисунок.32. Поиск и вставка в дерево бинарного поиска.

В процессе успешного поиска H в этом примере дерева (вверху) мы перемещаемся вправо от корня (поскольку Н больше чем А), затем влево в правом поддереве (поскольку Н меньше чем S) и т.д., продолжая перемещаться вниз по дереву, пока не встретится Н. В процессе неуспешного поиска М в этом примере дерева (в центре) мы перемещаемся вправо от корня (поскольку М больше чем А), затем влево в правом поддереве корня (поскольку М меньше чем S) и т.д., продолжая перемещаться вниз по дереву, пока не встретится внешняя связь слева от N в нижней части диаграммы. Для вставки М после обнаружения промаха при поиске достаточно просто заменить связь, которая прерывает поиск, связью с М (внизу).

Функция поиска в программе столь же проста, как и обычный бинарный поиск; существенная особенность BST-деревьев заключается в том, что операцию insert легко реализовать в виде операции search. Рекурсивная функ­ция insertR для вставки нового элемента в BST-дерево следует логике, аналогичной ис­пользованной при разработке функции searchR, и использует ссылочный аргумент h для построения дерева: если дерево пусто, h устанавливается рав­ным ссылке на новый узел, содержащий элемент; если ключ поиска меньше ключа в корне, элемент вставляется в левое поддерево, в противном случае элемент вставляется в правое поддерево. То есть, аргумент ссылки изменяется только в пос­леднем рекурсивном вызове, когда вставляется новый элемент.

 

Рисунок.33. Создание дерева бинарного поиска

Эта последовательность отражает результат вставки ключей ASER CHIN в первоначально пустое BST-depeeo. Каждая вставка следует за промахом при поиске в нижней части дерева.

На рис. 33 показан пример создания BST-дерева путем вставки последовательности ключей в первоначально пустое дерево. Новые узлы присоединяются к нулевым свя­зям в нижней части дерева, а в остальном структура дерева никак не изменяется. Поскольку каждый узел имеет две свя­зи, дерево растет скорее в ширину, нежели в высоту.

При использовании BST-деревьев реализация функции sort требует незначительного объема дополнительной рабо­ты. Построение BST-дерева сводится к сортировке элемен­тов, поскольку при соответствующем рассмотрении BST-дерево представляет отсортированный файл. На приведенных выше рисунках ключи отображаются на странице слева на­право (если не обращать внимания на их расположение по высоте и связи). Программа работает только со связями, но простой поперечный обход, по определению, обеспечивает выполнение этой задачи, что демонстрируется рекурсивной реализацией функции showR в программе 22. Для отобра­жения элементов в BST-дереве в порядке их ключей мы ото­бражаем элементы в левом поддереве в порядке их ключей (рекурсивно), затем корень, и далее элементы в правом под­дереве в порядке их ключей (рекурсивно).