Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Бинарный поиск. Поиск по бинарному дереву.
Бинарный поиск.
Поиск может быть выполнен значительно быстрее, если записи предварительно отсортированы по возрастанию или убыванию ключей. Предположим, что записи отсортированы a1<a2...<aN по возрастанию ключей, тогда сначала вычисляется индекс среднего элемента p=n/2. Если значение не целое, оно может округляться в любую сторону. Затем выполняется сравнение ключа среднего элемента и К, К=ар. Если они равны то поиск завершен успешно и результатом является индекс р некоторого элемента. В противном случае поиск должен быть продолжен в одной из половин таблицы. Если к<ар тогда а1,а2...ар-1 , к>Ар тогда Ар+1, Ар+2....Аn. Затем указанные шаги повторяются до тех пор пока не встретится запись с ключом К или останется 1 непросмотренный элемент в некоторой половине подмассива. Очевидно это этот единственный элемент будет иметь ключ К или же поиск будет завершен неуспешно, эффективность бинарного поиска: каждый просмотр среднего элемента массива или подмассива требует 2 сравнения(1ый - "=", 2ой - "<,>"). Поскольку каждый просмотр среднего элемента уменьшает зону поиска в 2 раза, то один непросмотренный элемент останется после выполнения 2log2n сравнений. Отсюда в худшем случае бинар. поиск требует E=2log2n+1 сравнений. Тогда оценка сложности O(log2n). В сравнении с лин. поиском считается, что бинар. поиск становится более эффективным при n>20.
Основным недостатком бинарного поиска явл. необходимость хранения таблицы в отсортиров. виде. Это практически невозможно при частых вставках и удалениях элементов.
2 реализации бинарного поиска: итерационный и рекурсивный.
Поиск по бинарному дереву .
Использование дерева для хранения записей позволяет сохранить эффективность поиска при достаточно простой реализации вставки и удаления записей. Для выполнения поиска применяют двоичное(бинарное) дерево, вершины которого имеют левого и правого потомка.
Построение дерева производится так: ключ первой записи входной последовательности сопоставляется с корнем дерева. Затем поочередно для записей начиная со второй до последней производится следующие действия: ключ очередной выбранной записи сравнивается с ключом корня. Если он меньше, он сравнивается с ключом левого потомка, если больше то правого и тд. по дереву до достижения листа. Если достигается лист, то образуется новая вершина дерева и ей сопоставляется соответствующая запись. Например пусть вх последовательностью явл.: 8,11,3,9,14,1,10,5,6,12,15,7,13.
Поиск по такому дереву осуществляется аналогично его построению путем просмтора веришн начиная от корня к листьям по тем же самым правилам.
Для описания алгоритма поиска, будем использовать след обозначения:
К-аргумет поиска
а[1...n] - массив ключей, Р - номер текущей вершины
L[p], R[p] - номера левого (правого) потомка текущей вершины Р
top -номер корня TS - результат поискаTS=0 - неуспешный поиск или же TS=p - успешный поиск, где р=1,2,3...N.
Трудоемкость алгоритма определяется высотой дерева 0(n) до 0(log2n). Худший с т зрения вычислительных затрат случай возникает тогда, когда при построении дерева записи считываются строго по возрастанию или убыванию ключей. Тогда дерево вырождается в лин. список длиной n. Однако, если записи выбираются в случайном порядке, то получается полное или почти полное дерево и алгоритм поиска работает подобно бинарному методую В среднем считается что сложность поиска по дереву имеет оценку 0(log2n)