503 509 512 612 653 677 703 765 897 908]

503 509 [512 612 653 677 703 765 897 908]

503 509 [512 612 653] 677 703 765 897 908

503 509 512 612 [653] 677 703 765 897 908

503 509 512 612 653 677 703 765 897 908]

503]509 512 612 653 677 703 765 897 908

503]509 512 612 653 677 703 765 897 908

503 509 512 612 653 677 703 765 897 908

503 509 512 612 653 677 703 765 897 908

Рис. 4. Примеры бинарного поиска.

Программа В {Бинарный поиск). Как и в программах из раздела 6.1, полагаем, что Ki представляет собой полное слово, находящееся по адресу KEY + i. В приведенном коде гП = /, г12 = и, г13 = г.

Эта процедура не вполне удачно реализуется на компьютере MIX в связи с небогатой арифметикой индексных регистров. Время работы составляет (18С - 105--12)и, где С = С1 + С2 - количество произведенных сравнений (количество выполнений шага ВЗ) и 5 = 1 при успешном (или О при неудачном) исходе поиска. Обратите внимание, что операция в строке 08 - SRB (shift right binary 1 - побитовый сдвиг вправо на единигу) - допустима лишь в бинарных версиях MIX; в общем случае ее следует изменить на MUL =1 2+1=, что приведет к увеличению времени работы программы до (26С - 185 -I- 20)и.

Представление в виде дерева. Для лучшего понимания работы алгоритма В представим описанную процедуру в виде бинарного дерева принятия решения, как показано на рис. 5, при N = 16.

[061 087 154 170 275 426

061 087 154 170 275 426

061 087 154 170 275 426

061 087 154 170 275 426

b) Поиск 400:

[061 087 154 170 275 426

[061 087 154 170 275 426

061 087 154 170 [275 426

061 087 154 170 [275] 426

061 087 154 170 275] [426

Рис. 5. Дерево сравнений, соответствующее бинарному поиску дая Л = 16.

При Л = 16 сначала согласно алгоритму сравниваются К я Kg; на рисунке это показано корневым узлом (?). Затем, если К < Kg, алгоритм переходит в левое поддерево и сравниваются К с К4; точно так же при К > Kg будет выполняться работа с правым поддеревом. Неудачный поиск приведет в один из внешних "квадратных" узлов, пронумерованных от [о] до Щ, например узел [Т] будет достигнут нами только при Кв < К < Ку.

Бинарное дерево, соответствующее бинарному поиску по N записям, может быть построено следующим образом: если N = О, дерево представляет собой просто один узел [о]. В противном случае корневой узел -

(МЮ-

При этом левое поддерево представляет собой бинарное дерево с \N/2] - 1 узлами, а правое - с [N/2\ узлами (все числа в узлах увеличены на "Л/2]).

Точно так в виде бинарного дерева с N узлами, в котором все узлы пронумерованы от 1 до N, может быть представлен любой алгоритм поиска в упорядоченной таблице длиной N (если только алгоритм не выполняет излишние сравнения). Верно и обратное - любое бинарное дерево соответствует некоторому методу поиска в упорядоченной таблице; достаточно просто пометить узлы

© ш © а -

UV-1

В симметричном порядке слева направо.

Если аргумент поиска алгоритма В равен Кю, алгоритм выполняет сравнения К > Kg, К < Ki2, К = Кю- На рис. 5 это соответствует пути от корня дерева к вершине (w). Точно так поведение алгоритма В при поиске других ключей соответствует некоторому пути из корня дерева. Метод построения бинарных деревьев, соответствующих алгоритму В, позволяет легко доказать с помощью индукции по N следующую теорему.

Теорема В. Для 2*~ < iV < 2* успешный поиск по алгоритму В требует (min 1, шах fc) сравнений; неудачный поиск при 2*~ < Л < 2* - 1 требует к-1 либо к сравнений.

Дальнейший анализ бинарного поиска. (Читателям, для которых математика не представляет интереса, рекомендуем пропустить материал до формулы (4).) Представление в виде дерева показывает нам также простой путь вычисления среднего числа сравнений. Пусть - среднее число сравнений при успешном поиске; предположим также, что все N ключей равновероятны в качестве аргумента поиска. Среднее число сравнений при неудачном поиске - С; все Л -I- 1 интервалов внутри и вне граничных значений также равновероятны. Тогда по определению длин внутреннего и внешнего путей

длина внутреннего пути дерева длина внешнего пути дерева Cn = 1 +---, С =--j-;-.

Из 2.3.4.5-(3) видно, что длина внешнего пути всегда на 2Л больше длины внутреннего пути. Отсюда следует несколько неожиданное соотношение между и Cf:

Cn = (i + J)cm-1. (2)

Эта формула, выведенная Т. И. Хиббардом (Т. N. Hibbard) [JACM 9 (1962), 16-17], справедлива для всех методов, соответствующих бинарным деревьям; другими словами, она справедлива для всех методов, не использующих излишних сравнений. Дисперсия среднего числа сравнений при успешном поиске также может быть выражена через дисперсию среднего числа сравнений при неудачном поиске (см. упр. 25).

На основании приведенных выше формул мы можем сказать, что "наилучший" путь поиска методом сравнения тот, дерево которого имеет минимальную длину внешнего пути среди всех бинарных деревьев с N внутренними узлами. К счастью, можно доказать, что в этом смысле алгоритм В оптимален для любого N (как помните, в упр. 5.3.1-20 было доказано, что бинарное дерево имеет минимальную длину пути тогда и только тогда, когда все внешние узлы расположены не более чем на двух соседних уровнях). Отсюда следует, что длина внешнего пути дерева, соответствующего алгоритму В, равна

(7V + l)([lg7VJ+2)-2L8J+i. (3)

(См. 5.3.1-(34).) Из формул (2) и (3) мы можем вычислить точные средние значения количества сравнений, полагая, что все аргументы поиска равновероятны.

ЛГ = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 C;v = l li 1 2 2i 2 2f 2 21 2 3 3 3 3 3 3 Cn = 1 If 2 2 2 2f 3 3 ЗА 3 3 ЗЩ 31 ЗИ 4 4

В общем случае при к = [Ig N\ мы имеем следующее:

= А; + 1 - (2*+1 -к- 2)/N = IgTV - 1 + 6 -Ь (jfc + 2)/N, Cjv = ife + 2 - 2*+V( + 1) = + 1) + «>

где 0 < б,б < 0.0861 (см. 5.3.1-(35)).

Итак, алгоритм В никогда не делает более [Ig Л] -I-1 сравнений; среднее количество сравнений при успешном поиске составляет около IgA - 1. Никакой другой