Алгоритм поиска по бинарному дереву.

Общая классификация алгоритмов поиска.

Все методы можно разделить на статические и динамические. При статическом поиске массив значений не меняется во время работы алгоритма. Во время динамического поиска массив может перестраиваться или изменять.

Суть этого алгоритма достаточно проста. Представим себе, что у нас есть набор карточек с телефонными номерами и адресами людей. Карточки отсортированы в порядке возрастания телефонных номеров. Необходимо найти адрес человека, если мы знаем, что его номер телефона 222-22-22. Наши действия? Берем карточку из середины пачки, номер карточки 444-44-44. Сравнивая его с искомым номером, мы видим, что наш меньше и, значит, находится точно в первой половине пачки. Смело откладываем вторую часть пачки в сторону, она нам не нужна, массив поиска мы сузили ровно в два раза. Теперь берем карточку из середины оставшейся пачки, на ней номер 123-45-67. Из чего следует, что нужная нам карточка лежит во второй половине оставшейся пачки... Таким образом, при каждом сравнении, мы уменьшаем зону поиска в два раза. Отсюда и название метода - половинного деления или дихотомии.

Скорость сходимости этого алгоритма пропорциональна Log(2)N¹. Это означает, что не более, чем через Log(2)N сравнений, мы либо найдем нужное значение, либо убедимся в его отсутствии.

11.6 Поиск по "дереву Фибоначчи".

Трудноватый для восприятия метод, но эффективность его немного выше, чем у поиска по Бинарному дереву, хотя так же пропорциональна Log(2)N.

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

Почему этот способ считается более эффективным, чем предыдущий?

Дело в том, что метод Фибоначчи включает в себя только такие арифметические операции, как сложение и вычитание, нет необходимости в делении на 2, тем самым экономится процессорное время!

Метод экстраполяций

Массив значений - это словарь, все значения в нем отсортированы по алфавиту. Искомое слово нам известно. Значит искать будем в отсортированном массиве.

Итак, искомое слово начинается на букву T, открываем словарь немного дальше, чем на середине. Нам попалась буква R, ясно, что искать надо во второй части словаря, а на сколько отступить? На половину? "Ну зачем же на половину, это больше, чем надо", скажете вы и будете правы. Ведь нам не просто известно, в какой части массива искомое значение, мы владеем еще и информацией о том, насколько далеко надо шагнуть!

Вот мы и подошли к сути рассматриваемого метода. В отличие от первых двух, он не просто определяет зону нового поиска, но и оценивает величину нового шага.

Алгоритм носит название экстраполяционного метода и имеет скорость сходимости большую, чем первые два метода.

Примечание:

Если при поиске по бинарному дереву за каждый шаг массив поиска уменьшался с N значений до N/2, то при этом методе за каждый шаг зона поиска уменьшается с N значений до корня квадратного из N. Если К лежит между Kn и Km, то следующий шаг делаем от n на величину

(n - m)*(K - Kn)/(Km - Kn)

Скорость экстраполяционнго метода начинает существенно превышать скорость метода половинного деления при больших значениях N.

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

Если массив значений большой и искать нужно часто, необходимо отсортирорать массив и воспользовыаться методом половинного деления или интерполяционным методом. Каким из них именно, выбирать нужно исходя из того, насколько велик массив и какой метод легче реализовать в коде.

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

Итак, имеем массив размерностью N и проводим в нем поиск М раз.

Количество операций, которые выполнит алгоритм прямого перебора, пропорционально M * N. Метод дихотомии совершит 2М * Log(2)N операции, к тому же и время на сортировкку надо прибавить – N * Log(2)N.

Итак, имеем два выражения:

T1 = M*N;

T2 = 2М*Log(2)N + N*Log(2)N

При Т1 = Т2 мы находимся на границе, на которой одинаково оптимальны оба алгоритма. Из этого равенства можно получить области в системе координат "Количество обращений - Размерность массива".