Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 13
Текст из файла (страница 13)
Верно и обратное — любое бинарное дерево соответствует некоторому методу поиска в упорядоченной таблице; достаточно просто пометить узлы в симметричном порядке слева направо. Если аргумент поиска алгоритма В равен К»е, алгоритм выполняе~ сравнения К > Ке, К < Кш, К = Кш. На рис. 5 это соответствует пути от корня дерева к вершине Я~у. Точно так поведение алгоритма В при поиске других ключей соответствует некоторому пути из корня дерева. Метод построения бинарных деревьев, соответствующих алгоритму В, позволяет легко доказать с помощью индукции по Х следующую теорему.
Теорема В Дня 2» 1 < Я < 2» успешный поиск по алгоритму В требует 1шш 1 гпах я) сравнений; неудачный поиск при 2» ' < Х < 2» - 1 требует )с - 1 либо )с сравнений. 1 Дальнейший анализ бинарного поиска. (Читателям, для которых математика не представляет интереса, рекомендуем пропустить материал до формулы (4).) Представление в виде дерева показывает нам также простой путь вычисления сред'- него числа сравнений.
Пусть См — среднее число сравнений при успешном поиске; предположим также, что все Л' ключей равновероятны в качестве аргумента поиска. Среднее число сравнений при неудачном поиске — С(„все Х + 1 интервалов внутри н вне граничных значений также равновероятны. Тогда по определению длин внутреннего и внешнего путей длина внутреннего пути дерева ~ю =1+ Х длина внешнего пути дерева У+1 Из 2.3.4.5-(3) видно, что длина внешнего пути всегда на 2Л' больше длины внутрен- него пути.
Отсюда следует несколько неожиданное соотношение между См и С~: 1~ Ся = ~1+ — ~С' -1. Л./ (Л + 1)(рйЛ) +2) 20вл)+~. (3) (См. 5,3.1-(34).) Из формул (2) и (3) мы можем вычислить точные средние значеяия количества сравнений, полагая, что все аргументы поиска равновероятны. Ю = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 С, =1 1,' 1уз 2 2~ 2~ 2~ 25 21 2~ 3 3~ 3Д зз 314 3Д В общем случае при Й = (18 Л') мы имеем следующее: Сь = 8+1 — (2ьы — й — 2)/Л' = 16Ф вЂ” 1+с+(Й+2)/Л', (4) С~л = й + 2 — 2 +~/(Х+ 1) = 18(Л~ + 1) + е где 0 < е, с' < 0.0861 (см. 5.3.1-(35)). Итак, алгоритм В никогда не делает более (18 Л'1 + 1 сравнений; среднее количество сравнений при успешном поиске составляет около 18 Л' — 1. Никакой другой Эта формула, выведенная Т. Н. Хиббардом (Т, Н. Н1ЬЬагс)) (3.4СМ 9 (1962), 16-17), справедлива для всех методов, соответствующих бинарным деревьям, другими словами, она справедлива для всех методов, не использующих излишних сравнений.
Дисперсия среднего числа сравнений при успешном поиске также может быть выражена через дисперсию среднего числа сравнений при неудачном поиске (см. упр. 25). На основании приведенных выше формул мы можем сказать, что "наилучший" путь поиска методом сравнения тот, дерево которого имеет минимальную длину внешнего пути среди всех бпнарных деревьев с Х внутренними узлами. К счастью, можно доказать, что в атом смысле алгоритм В оптимален для любого Л' (как помните, в упр. 5.3,1-20 было доказано, что бинарное дерево имеет минимальную длину пути тогда и только тогда, когда все внешние узлы расположены не более чем на двух соседних уровнях).
Отсюда следует, что длина внешнего пути дерева, соответствующего алгоритму В, равна метод поиска, основанный на сравнении ключей, не может превзойтн этот результат. Среднее время работы программы В составляет приблизительно (18!8 Х вЂ” 16) и для успешного поиска, (1818Х+ 12)и для неудачного поиска (в предположении равновероятных исходов поиска), Важное изменение.
Вместо трех указателей (1, 1 н и) в процессе поиска можно использовать только два: текущее положение 1 и величину его изменения Ю. После каждого сравнения, не давшего равенства, мы можем установить 1 ~ — 1~8 и б ь- 6/2 (приблизительно). Это вполне возможный путь, хотя и требующий исключительного внимания к мельчайшим деталям, как в приведенном ниже алгоритме. Более простые подходы будут неработоспособны.
Алгоритм 11 (Однороднмв бинарный поиск (Уив/оггп Мпагу эеагсЬ)). Дана таблица записей Вм Вю ° °, В~ч, ключи которых расположены в порядке возрастания: Кг < Ке ( "° с К~д. Алгоритм обеспечивает поиск заданного аргумента К. В случае четного Ю алгоритм будет обращаться к фиктивному ключу Кс, значение которого должно быть равно — оо (или любому значению, меньшему К). Алгоритм работает в предгюложении, что Х > 1. Ш. (Инициализация.) Установиты <- (Х/2), ш <- 1Х/21. 112.
1Сравнение,, 'Если К < К;, перейти к шагу ПЗ; если К > К,, перейти к шагу 114; если К = К;, алгоритм успешно завершен. 113. (Уменьшить а,) (Мы определили интервал продолжения поиска, содержащий гп или пт — 1 записей; 1 указывает на первый элемент справа от интервала.) При гп = 0 алгоритм завершается неудачно.
В противном случае следует сначала установить 1 < — 1 — (гп/2), а затем — т +- 1гп/2) и перейти к шагу 1)2. 114. (Увеличение 1.) (Мы определили интервал продолжения поиска, содержащий гп или гп — 1 записей; 1 указывает на первый элемент слева от интервала.) При гп = 0 алгоритм завершается неудачно. В противном случае сведует сначала установить 1 +- 1+ (т/2), а затем — щ +- 1гп/2) и перейти к шагу П2.
] На рис. б показано бинарное дерево, соответствующее поиску при АГ = 10. В случае неудачного поиска алгоритм может выполнить излишнее сравнение непосредственно перед окончанием работы; такие узлы на рисунке заштрихованы. Мы называем этот процесс поиска однородным потому„что разность между числами узла на уровне 1 и его узла-предшественника на уровне 1 — 1 представляет собой константу 6 для всех узлов на уровне 1. Теория, лежащая в основе алгоритма П,может быть пояснена следующим обра» зом. Предположим, что у нас имеется интервал для поиска длиной и — 1; сравнение со средним элементом (для четного и) или с одним из средних элементов (для нечетного и) дает нам два интервала — длиной 1п/2) — 1 и (и/2) — 1, После повторения этого процесса я раз мы получим 2" интермлов, наименьший из которых имеет длину (п/2") — 1, а наибольший — ~'и/2ь) — 1.
Следовательно, длина двух интервалов на одном уровне отличается не более чем на единицу; это делает возможным выбор "среднего" элемента без запоминания точных значений длин интервалов. Рис. 0. Дерево сравнений дле "однородного" бинарного поиска при Х = 10. Алгоритм С (Однородный бинарный поиск), Этот алгоритм подобен алгоритму 11, но использует вспомогательную таблицу вместо вычислений. 1»У + 2~ ' 1 ОЕЬТА(у) = ~ ~ для 1 < 1 ( (180») + 2, (6) С1. (Инициализация.) Установить 1»- ОЕ1 ТА Ш, 1»- 2. С2. 1Сравнение.) Если К < К», перейти к шагу СЗ; если К > К», перейти к шагу С4; если К = Ко алгоритм успешно завершается. СЗ.
(Уменьшение Ц Если ОЕЬТАЦ) = О, алгоритм завершается неудачно, В противном случае установить»»- » — ОЕ1 ТАЦ), г' +- у'+ 1 и перейти к шагу С2. С4. )Увеличение Ц Если ОЕЬТА(Я = О, алгоритм завершается неудачно. В противном случае установить»»-1+ ОЕЬТАЯ, у' »-,у+ 1 и перейти к шагу С2, 3 В упр.
8 доказывается, что настоящий алгоритм использует искусственный ключ Ке = -оо только прн четных А«. Программа С (Однородный бинарный гюпск). Эта программа выполняет ту же задачу, что н программа В, нспсаьзуя алгоритм С; при этом гА аз К гП ш1, г12 «д у, г13 гй ОЕ1 ТАЮ. ЕНТ1 6+1»2 1 С .
Ийвцийлииийд «»- (%+1)% 00 ЕМТ2 2 1 1»-2. 00 ЬОА К 1 04 УНР 2Р 1 00 ЗН ЗЕ ЗОССЕЯЗ С1 Переход, если К = К». 00 ЛЗЕ РАПЛНЕ С1- Я Переход, если ОЕЬТА(у) «~ О. О» «««««.«а«-«-«««. ««~«~ 08 6Н ХНО2 1 С-1 у»-6+1, Принципиальное достоинство алгоритма П заключается в том, что нам совершенно не нужно хранить значение гп; необходима только ссылка на небольшую таблицу 6 для использования на каждом уровне дерева. Таким образом, алгоритм сводится к следующей процедуре, одинаково подходящей как для бинарных, так и для десятичных компьютеров. Рис.
Т. Дерево сравнений ллк почти равномерного поиска по методу Шара прн 1т" = 10. с о2 о~ С С С2 С2 1 — Я ок 2Н 193 10 СИРА Л ЛЕЕ 12 1НС1 1У УЗИЕ .Ц ГА11ЛВЕ ЕЦО ОИ.ТА, 2 ЕЕ1,1 ЗВ О,З ВВ Переход, если К < Ко С4. Увеличение 1. Переход если вйьТА121 а1 О Выход прн отсутствии в таблице. !8.5!ЕЮ вЂ” 6)и при успешном поиске, !8.51!ЕЮ) + 12)н при неудачном поиске. Это более чем в два раза быстрее программы В; прн этом специфика бинарного ком- пьютера не используется 1в случае времени работы (5) программы В предполагалось наличие команды битового сдвига в компьютере И11).
Другая модификация бинарного поиска, предложенная в 1971 году Л. 3. Шаром (1. Е. ВЬаг), на некоторых компьютерах будет работать еще быстрее, так как она однородна после первого шага и не требует использования таблицы, Первый шаг состоит в сравнении К и Кь где ! = 2", А = ! !Едет'1. Если К < Кн мы используем однородный поиск с 5 = 2а ~, 2" ~, ..., 1, О. С другой стороны, если К > Ко мы устанавливаем 1 = Г =- Ф+ 1 — 2', где 1 = ~18!Х вЂ” 2" + Ц~, и„делая вид, что первое сравнение на самом деле было К > Кг, используем бинарный поиск с 5 = 1 ~, 2~ а, ..., 1, О.
Метод Шара для Х = 10 проиллюстрирован на рис. 7. Подобно предыдущим алгоритмам„он никогда не выполняет больше ! 18 Ф) + 1 сравнений, Следовательно, выполняемое им количество сравнений превышает минимально возможное среднее значение не более чем на единицу — несмотря на то, что иногда алгоритму В случае успешного завершения поиска данный алгоритм соответствует бинарному дереву с такой же длиной внутреннего пути, как и в алгоритме В, поэтому среднее количество сравнений См остается прежним.
При неудачном поиске алгоритм С всегда выполняет в точности )!ЕЛА) + 1 сравнений. Общее время работы программы С не совсем симметрично по отношению к левым и правым ветвям, и С1 имеет больший вес, чем С2. Впрочем, в упр. 11 будет показано, что случаи К < К; имеют ту же вероятность, что и К > К;. Следовательно, программа С работает приблизительно следующее время; приходится проводить несколько избыточньп сравнений при успешном поиске (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
