\input style
\chapno=6\subchno=1\chapnotrue

%% 483
\subchap{поиск посредством сравнения ключей} %% 6.2

в ЭТОМ ПАРАГРАФЕ МЫ РАССМОТРИМ МЕТОДЫ ПОИСКА, ОСНОВАННЫЕ НА ЛИНЕЙНОМ 
УПОРЯДОЧЕНИИ КЛЮЧЕЙ (НАПРИМЕР, ПОРЯДОК МОЖЕТ БЫТЬ ЧИСЛОВЫМ ИЛИ АЛФАВИТНЫМ).
 пОСЛЕ СРАВНЕНИЯ ДАННОГО АРГУМЕНТА~$K$ С КЛЮЧОМ~$K_i$ ИЗ ТАБЛИЦЫ ПОИСК 
ПРОДОЛЖАЕТСЯ ОДНИМ ИЗ ТРЕХ СПОСОБОВ В ЗАВИСИМОСТИ ОТ ТОГО, КАКОЕ ИЗ 
СООТНОШЕНИЙ ВЕРНО: $K<K_i$, $K=K_i$, $K>K_i$. пРИ 
ПОСЛЕДОВАТЕЛЬНОМ ПОИСКЕ МЫ, В СУЩНОСТИ, ДОЛЖНЫ ВЫБИРАТЬ ОДНО ИЗ ДВУХ 
ПРОДОЛЖЕНИЙ ($K=K_i$ ИЛИ~$K\ne K_i$), НО ЕСЛИ МЫ ОСВОБОДИМСЯ 
ОТ ОГРАНИЧЕНИЯ ИМЕТЬ ЛИШЬ ПОСЛЕДОВАТЕЛЬНЫЙ ДОСТУП К ТАБЛИЦЕ, ТО ПОЛУЧИМ 
ВОЗМОЖНОСТЬ ЭФФЕКТИВНО ИСПОЛЬЗОВАТЬ ОТНОШЕНИЕ ПОРЯДКА.

\subsubchap{ пОИСК В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ} % 6.2.1

чТО ВЫ СТАНЕТЕ ДЕЛАТЬ, ЕСЛИ ВАМ ВРУЧАТ БОЛЬШУЮ ТЕЛЕФОННУЮ КНИГУ И 
ПОПРОСЯТ НАЙТИ ИМЯ ЧЕЛОВЕКА, НОМЕР ТЕЛЕФОНА КОТОРОГО 795-68-41? зА 
НЕИМЕНИЕМ ЛУЧШЕГО ПРИДЕТСЯ ВОСПОЛЬЗОВАТЬСЯ МЕТОДАМИ ПОСЛЕДОВАТЕЛЬНОГО 
ПОИСКА, ИЗЛОЖЕННЫМИ В \S~6.1. (пРАВДА, ЛОВКИЙ ЧАСТНЫЙ ДЕТЕКТИВ МОГ БЫ 
ПОПЫТАТЬСЯ НАБРАТЬ НОМЕР И СПРОСИТЬ, КТО ГОВОРИТ; НЕ ИСКЛЮЧЕНО ТАКЖЕ, ЧТО 
У НЕГО ЕСТЬ ДРУЗЬЯ НА ТЕЛЕФОННОЙ СТАНЦИИ, ИМЕЮЩИЕ ДОСТУП К СПРАВОЧНИКАМ, 
ГДЕ ТЕЛЕФОНЫ РАСПОЛОЖЕНЫ В ПОРЯДКЕ ВОЗРАСТАНИЯ НОМЕРОВ.) дЕЛО В ТОМ, ЧТО 
ГОРАЗДО ЛЕГЧЕ НАЙТИ ЗАПИСЬ ПО ФАМИЛИИ АБОНЕНТА, А НЕ ПО НОМЕРУ, ХОТЯ 
ТЕЛЕФОННАЯ КНИГА СОДЕРЖИТ ВСЮ ИНФОРМАЦИЮ, НУЖНУЮ В ОБОИХ СЛУЧАЯХ. 
еСЛИ НЕОБХОДИМО НАЙТИ ЗАПИСЬ В БОЛЬШОМ ФАЙЛЕ, О ПОСЛЕДОВАТЕЛЬНОМ ПОИСКЕ 
ПОЧТИ НЕ МОЖЕТ БЫТЬ РЕЧИ, НО ИСПОЛЬЗОВАНИЕ ОТНОШЕНИЯ ПОРЯДКА В ОГРОМНОЙ 
СТЕПЕНИ ОБЛЕГЧАЕТ РАБОТУ.

в НАШЕМ РАСПОРЯЖЕНИИ ЕСТЬ МНОГО МЕТОДОВ СОРТИРОВКИ (ГЛ.~5), ПОЭТОМУ ДЛЯ 
НАС НЕ СОСТАВИТ ТРУДА УПОРЯДОЧИТЬ ФАЙЛ, ЧТОБЫ ЗАТЕМ БЫСТРЕЕ ПРОИЗВЕСТИ 
ПОИСК. рАЗУМЕЕТСЯ, ЕСЛИ НУЖЕН ЛИШЬ ОДНОКРАТНЫЙ ПРОСМОТР, ТО БЫСТРЕЕ 
ПРОИЗВЕСТИ ЕГО ПОСЛЕДОВАТЕЛЬНО, БЕЗ ПРЕДВАРИТЕЛЬНОЙ СОРТИРОВКИ. нО ЕСЛИ В 
ОДНОЙ И ТОЙ ЖЕ ТАБЛИЦЕ ПРИХОДИТСЯ ЧАСТО ПРОИЗВОДИТЬ ПОИСК, ТО 
ЭФФЕКТИВНЕЕ УПОРЯДОЧИТЬ ЕЕ. в ЭТОМ ПУНКТЕ МЫ ИЗУЧИМ МЕТОДЫ ПОИСКА В 
ТАБЛИЦАХ СО СЛУЧАЙНЫМ ДОСТУПОМ И УПОРЯДОЧЕННЫМИ КЛЮЧАМИ
$$
K_1<K_2<\ldots<K_N.
$$
%% 484
пОСЛЕ СРАВНЕНИЯ $K$ И~$K_i$ МЫ ИМЕЕМ ИЛИ
$$
\eqalign{
&\bullet K < K_i \rem{[$R_i$, $R_{i+1}$,~\dots, $R_N$ ИСКЛЮЧАЮТСЯ ИЗ РАССМОТРЕНИЯ],}\cr
\hbox{ИЛИ }&\bullet K=K_i \rem{[ПОИСК ЗАКОНЧЕН],}\cr
\hbox{ИЛИ }&\bullet K>K_i \rem{[$R_1$, $R_2$,~\dots, $R_i$ ИСКЛЮЧАЮТСЯ ИЗ РАССМОТРЕНИЯ].}\cr
}
$$
уМЕЛО ДЕЙСТВУЯ В КАЖДОМ ИЗ ЭТИХ СЛУЧАЕВ, МЫ СЭКОНОМИМ МНОГО ВРЕМЕНИ ПО 
СРАВНЕНИЮ С ПОСЛЕДОВАТЕЛЬНЫМ ПОИСКОМ, ЕСЛИ ТОЛЬКО $i$ НЕ СЛИШКОМ БЛИЗКО К 
КОНЦАМ ТАБЛИЦЫ. тАКИМ ОБРАЗОМ, УПОРЯДОЧЕНИЕ ВЕДЕТ К ЭФФЕКТИВНЫМ АЛГОРИТМАМ.

\section бИНАРНЫЙ ПОИСК. пОЖАЛУЙ, ПЕРВЫМ ПРИХОДИТ В ГОЛОВУ СЛЕДУЮЩИЙ 
ОЧЕВИДНЫЙ МЕТОД: СНАЧАЛА СРАВНИТЬ~$K$ СО СРЕДНИМ КЛЮЧОМ В ТАБЛИЦЕ. 
рЕЗУЛЬТАТ СРАВНЕНИЯ ПОЗВОЛИТ ОПРЕДЕЛИТЬ, В КАКОЙ ПОЛОВИНЕ ФАЙЛА ПРОДОЛЖИТЬ 
ПОИСК, ПРИМЕНЯЯ К НЕЙ ТУ ЖЕ ПРОЦЕДУРУ, И Т. Д. пОСЛЕ НЕ БОЛЕЕ ЧЕМ 
ПРИМЕРНО $\log_2 N$ СРАВНЕНИЙ ЛИБО КЛЮЧ БУДЕТ НАЙДЕН, ЛИБО БУДЕТ 
УСТАНОВЛЕНО ЕГО ОТСУТСТВИЕ. тАКАЯ ПРОЦЕДУРА ИНОГДА НАЗЫВАЕТСЯ 
"ЛОГАРИФМИЧЕСКИМ ПОИСКОМ" ИЛИ "МЕТОДОМ ДЕЛЕНИЯ ПОПОЛАМ", НО НАИБОЛЕЕ 
УПОТРЕБИТЕЛЬНЫЙ ТЕРМИН---\dfn{БИНАРНЫЙ ПОИСК.}

оСНОВНАЯ ИДЕЯ БИНАРНОГО ПОИСКА ДОВОЛЬНО ПРОСТА, ДЕТАЛИ ЖЕ НЕТРИВИАЛЬНЫ, И 
ДЛЯ МНОГИХ ХОРОШИХ ПРОГРАММИСТОВ НЕ ОДНА ПОПЫТКА НАПИСАТЬ ПРАВИЛЬНУЮ 
ПРОГРАММУ ЗАКОНЧИЛАСЬ НЕУДАЧЕЙ. оДНА ИЗ НАИБОЛЕЕ ПОПУЛЯРНЫХ РЕАЛИЗАЦИИ 
МЕТОДА ИСПОЛЬЗУЕТ ДВА УКАЗАТЕЛЯ---$l$ И~$u$, СООТВЕТСТВУЮЩИЕ ВЕРХНЕЙ 
И НИЖНЕЙ ГРАНИЦАМ ПОИСКА, И СОСТОИТ В СЛЕДУЮЩЕМ.

\alg в.(бИНАРНЫЙ ПОИСК.) с ПОМОЩЬЮ ДАННОГО АЛГОРИТМА РАЗЫСКИВАЕТСЯ 
АРГУМЕНТ~$K$ В ТАБЛИЦЕ ЗАПИСЕЙ $R_1$, $R_2$,~\dots, $R_N$, КЛЮЧИ КОТОРЫХ 
РАСПОЛОЖЕНЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ: $K_1<K_2<\ldots<K_N$.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $l\asg 1$, $u\asg N$.

\st[нАХОЖДЕНИЕ СЕРЕДИНЫ.] (в ЭТОТ МОМЕНТ МЫ ЗНАЕМ, ЧТО ЕСЛИ $K$ ЕСТЬ В 
ТАБЛИЦЕ, ТО ВЫПОЛНЯЮТСЯ НЕРАВЕНСТВА $K_l\le K\le K_u$. бОЛЕЕ ТОЧНОЕ 
ОПИСАНИЕ СИТУАЦИИ ПРИВОДИТСЯ НИЖЕ, В УПР.~1.) еСЛИ $u<l$, ТО АЛГОРИТМ 
ЗАКАНЧИВАЕТСЯ НЕУДАЧНО; В ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ 
$i\asg\floor{(l+u)/2}$: ТЕПЕРЬ $i$~УКАЗЫВАЕТ ПРИМЕРНО В СЕРЕДИНУ 
РАССМАТРИВАЕМОЙ ЧАСТИ ТАБЛИЦЫ.

\st[сРАВНЕНИЕ.] еСЛИ $K<K_i$, ТО ПЕРЕЙТИ НА \stp{4}; ЕСЛИ $K>K_i$, ТО 
ПЕРЕЙТИ НА~\stp{5}; ЕСЛИ $K=K_i$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ УДАЧНО.

\st[кОРРЕКТИРОВКА~$u$]. уСТАНОВИТЬ $u\asg i-1$ И ВЕРНУТЬСЯ К ШАГУ~\stp{2}.

\st[кОРРЕКТИРОВКА~$l$.] уСТАНОВИТЬ  $l\asg i+1$ И ВЕРНУТЬСЯ К ШАГУ~\stp{2}.
\algend
%%485
\picture{рИС. 3. бИНАРНЫЙ ПОИСК.}

рИСУНОК~4 ИЛЛЮСТРИРУЕТ ПОВЕДЕНИЕ АЛГОРИТМА в В ДВУХ СЛУЧАЯХ: КОГДА 
РАЗЫСКИВАЕТСЯ АРГУМЕНТ, РАВНЫЙ ИМЕЮЩЕМУСЯ В ТАБЛИЦЕ ЧИСЛУ~653, И КОГДА 
РАЗЫСКИВАЕТСЯ ОТСУТСТВУЮЩИЙ АРГУМЕНТ~400. сКОБКИ СООТВЕТСТВУЮТ УКАЗАТЕЛЯМ 
$l$ И~$u$, ПОДЧЕРКНУТЫЙ КЛЮЧ ПРЕДСТАВЛЯЕТ~$K_i$. в ОБОИХ СЛУЧАЯХ ПОИСК 
КОНЧАЕТСЯ ПОСЛЕ ЧЕТЫРЕХ СРАВНЕНИЙ.

\prog B.(бИНАРНЫЙ ПОИСК.) кАК И В ПРОГРАММАХ \S~6.1, ПРЕДПОЛАГАЕТСЯ, ЧТО 
$K_i$ ЗАНИМАЕТ ПОЛНОЕ СЛОВО ПО АДРЕСУ $|KEY|+i$. пРИВОДИМАЯ НИЖЕ ПРОГРАММА 
ИСПОЛЬЗУЕТ $|rI1|\equiv l$, $|rI2|\equiv u$, $|rI3|\equiv i$.
{\catcode`\!=\active\def!#1.{\underline{#1}}
 \catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}}
 \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}}
$$
\displaylines{
\matrix{
\vbox{\halign{$\phantom{[}#\phantom{]}$\bskip&&$\phantom{[}#\phantom{]}$\bskip\cr
\noalign{\hbox{a)~пОИСК ЧИСЛА 653:}}
[061 & 087 & 154 & 170 & 275 & 426 & 503 &!509.& 512 & 612 &  653  & 677 & 703 & 765 & 897 & 908]\cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 & 612 &  653  &!677.& 703 & 765 & 897 & 908]\cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 &!612.&  653] & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 &[!653.]& 677 & 703 & 765 & 897 & 908 \cr
}}\hfill\cr
\vbox{\halign{$#$\bskip&&$#$\bskip\cr
\noalign{\hbox{b)~пОИСК ЧИСЛА 400:}}
[061 & 087 & 154 & 170 &  275  & 426 & 503 &!509.& 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr
[061 & 087 & 154 &!170.&  275  & 426 & 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 & [275  &!426.& 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 &[!275.]& 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 &  275] &[426 & 503 & 509 & 512 & 612 & 658 & 677 & 703 & 765 & 897 & 908 \cr
}}\hfill\cr
}\cr
\hbox{рИС. 4.             пРИМЕРЫ БИНАРНОГО ПОИСКА.}\cr
}
$$
}
%%486
\code
START & ENT1 & 1       & 1   & Bl. нАЧАЛЬНАЯ УСТАНОВКА. $l\asg 1$.
      & ENT2 & N       & 1   & $u\asg N$.
      & JMP  & 2F      & 1   & нА B2.
5H    & JE   & SUCCESS & C1  & пЕРЕХОД, ЕСЛИ $K=K_i$.
      & ENT1 & 1,3     & C1-S& B5. кОРРЕКТИРОВКА $l$. $l\asg l+1$.
2H    & ENTA & 0,1     &C+1-S& B2. нАХОЖДЕНИЕ СЕРЕДИНЫ.
      & INCA & 0,2     &C+1-S& $|rA|\asg l+u$.
      & SRB  & 1       &C+1-S& $|rA|\asg\floor{|rA|/2}$. (мЕНЯЕТСЯ И~|rX|.)
      & STA  & TEMP    &C+1-S&
      & CMP1 & TEMP    &C+1-S&
      & JG   & FAILURE &C+1-S& пЕРЕХОД, ЕСЛИ $u<l$.
      & LD3  & TEMP    &C    & $i\asg\hbox{\rm СЕРЕДИНА}$.
3H    & LDA  & K       &C    & B3. сРАВНЕНИЕ.
      & смра & KEY,3   &C    &
      & JGE  & 5B      &C    & пЕРЕХОД, ЕСЛИ $K\ge K_i$.
      & ENT2 & -1,3    &C2   & B4. кОРРЕКТИРОВКА~$u$.
      & JMP  & 2B      &C2   & нА B2.
\endcode
\progend
дАННАЯ ПРОЦЕДУРА "РЕАЛИЗУЕТСЯ" НА МАШИНЕ \MIX\ МЕНЕЕ УДАЧНО, ЧЕМ 
ПРЕДЫДУЩИЕ, ТАК КАК РЕГИСТРОВАЯ АРИФМЕТИКА В \MIX\ НЕБОГАТА. вРЕМЯ, 
РАБОТЫ ПРОГРАММЫ РАВНО $(18C-10S+12)u$, ГДЕ
\picture{рИС. 5. бИНАРНОЕ ДЕРЕВО, СООТВЕТСТВУЮЩЕЕ БИНАРНОМУ ПОИСКУ  ($N=16$).}
$C=C1+C2$---КОЛИЧЕСТВО ПРОИЗВЕДЕННЫХ СРАВНЕНИЙ (СКОЛЬКО РАЗ ВЫПОЛНЯЕТСЯ 
ШАГ~B3), $S=1$ ИЛИ~0 В ЗАВИСИМОСТИ ОТ УДАЧНОГО ИЛИ НЕУДАЧНОГО ИСХОДА. 
зАМЕТИМ, ЧТО СТРОКА~08 ПРОГРАММЫ РАСШИФРОВЫВАЕТСЯ КАК "СДВИГ ВПРАВО НА 
1" (shift right binary 1),
%% 487
ЧТО ДОПУСТИМО ЛИШЬ В ДВОИЧНЫХ ВЕРСИЯХ \MIX; В ОБЩЕМ СЛУЧАЕ ЕЕ СЛЕДУЕТ 
ЗАМЕНИТЬ НА "|MUL =1//24+1=|", ТОГДА ВРЕМЯ РАБОТЫ ПРОГРАММЫ УВЕЛИЧИТСЯ 
ДО $(26C-18S +20)u$.

\section пРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВА. чТОБЫ ДОСКОНАЛЬНО РАЗОБРАТЬСЯ В 
АЛГОРИТМЕ~B, ЛУЧШЕ ВСЕГО ПРЕДСТАВИТЬ ЕГО В ВИДЕ БИНАРНОГО ДЕРЕВА РЕШЕНИЙ. 
(нА РИС.~5 ПОКАЗАНО ТАКОЕ ДЕРЕВО ДЛЯ СЛУЧАЯ $N=16$.)

пРИ $N=16$ ПЕРВЫМ ПРОИЗВОДИТСЯ СРАВНЕНИЕ~$K:K_8$, ЧТО ПРЕДСТАВЛЕНО НА 
РИСУНКЕ КОРНЕВЫМ УЗЛОМ~\node{8}. дАЛЕЕ, ЕСЛИ $K<K_8$,  АЛГОРИТМ 
ОБРАБАТЫВАЕТ ЛЕВОЕ ПОДДЕРЕВО, СРАВНИВАЯ $K$ И~$K_4$,. АНАЛОГИЧНО,  ЕСЛИ 
$K>K_8$, ИСПОЛЬЗУЕТСЯ ПРАВОЕ ПОДДЕРЕВО.
нЕУДАЧНЫЙ ПОИСК ВЕДЕТ В ОДИН ИЗ "ВНЕШНИХ" КВАДРАТНЫХ УЗЛОВ, ЗАНУМЕРОВАННЫХ 
ОТ~\leaf{0} ДО~\leaf{$N$}; НАПРИМЕР, МЫ ДОСТИГНЕМ УЗЛА~\leaf{6} ТОГДА И 
ТОЛЬКО ТОГДА, КОГДА $K_6<K<K_7$.

бИНАРНОЕ ДЕРЕВО, СООТВЕТСТВУЮЩЕЕ БИНАРНОМУ ПОИСКУ СРЕДИ $N$~ЗАПИСЕЙ, МОЖНО 
ПОСТРОИТЬ СЛЕДУЮЩИМ ОБРАЗОМ: ПРИ $N=0$ ДЕРЕВО СВОДИТСЯ К УЗЛУ~\leaf{0}. в 
ПРОТИВНОМ СЛУЧАЕ КОРНЕВЫМ УЗЛОМ ЯВЛЯЕТСЯ
\picture{рИС. СТР. 487}
ЛЕВОЕ ПОДДЕРЕВО СООТВЕТСТВУЕТ БИНАРНОМУ ДЕРЕВУ С $\ceil{N/2}-1$~УЗЛАМИ, А 
ПРАВОЕ---ДЕРЕВУ С $\floor{N/2}$~УЗЛАМИ И ЧИСЛАМИ В УЗЛАХ, УВЕЛИЧЕННЫМИ НА~$\ceil{N/2}$.

аНАЛОГИЧНЫМ ОБРАЗОМ \emph{ЛЮБОЙ} АЛГОРИТМ ПОИСКА В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ 
ДЛИНЫ~$N$, ПРОИЗВОДИМОГО ПУТЕМ СРАВНЕНИЙ, МОЖНО ПРЕДСТАВИТЬ БИНАРНЫМ 
ДЕРЕВОМ С УЗЛАМИ, ПОМЕЧЕННЫМИ ЧИСЛАМИ ОТ~$1$ ДО~$N$ (ПРЕДПОЛАГАЕТСЯ, ЧТО 
АЛГОРИТМ НЕ СОДЕРЖИТ ЛИШНИХ СРАВНЕНИЙ). оБРАТНО, ЛЮБОЕ БИНАРНОЕ ДЕРЕВО 
СООТВЕТСТВУЕТ НЕКОТОРОМУ МЕТОДУ ПОИСКА В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ; МЫ 
ПРОСТО ПОМЕЧАЕМ УЗЛЫ
\picture{рИС. СТР. 487}
В СИММЕТРИЧНОМ ПОРЯДКЕ СЛЕВА НАПРАВО.

еСЛИ АРГУМЕНТ ПОИСКА В АЛГОРИТМЕ~B ЕСТЬ $K_{10}$, ТО ПРОИЗВОДЯТСЯ 
СРАВНЕНИЯ $K>K_8$, $K<K_{12}$, $K=K_{10}$. нА РИС.~5 ЭТО СООТВЕТСТВУЕТ 
ПУТИ ОТ КОРНЯ К УЗЛУ~\node{10}. аНАЛОГИЧНО ПОВЕДЕНИЕ АЛГОРИТМА~B ПРИ 
ДРУГИХ~$K$ СООТВЕТСТВУЕТ ИНЫМ ПУТЯМ, ВЕДУЩИМ ИЗ КОРНЯ ДЕРЕВА. с ПОМОЩЬЮ 
МЕТОДА ПОСТРОЕНИЯ БИНАРНЫХ ДЕРЕВЬЕВ, СООТВЕТСТВУЮЩИХ АЛГОРИТМУ~B, И 
ИНДУКЦИИ ПО~$N$ ЛЕГКО ДОКАЗЫВАЕТСЯ

\proclaim тЕОРЕМА B. пРИ $2^{k-1}\le N <2^k$ УДАЧНЫЙ ПОИСК,  ИСПОЛЬЗУЮЩИЙ 
АЛГОРИТМ~B, ТРЕБУЕТ $(\min 1, \max k)$~СРАВНЕНИЙ. нЕУДАЧНЫЙ ПОИСК
%%488
ТРЕБУЕТ $k$~СРАВНЕНИЙ ПРИ~$N= 2^k-1$ ЛИБО $k-1$ ИЛИ $k$~СРАВНЕНИЙ ПРИ 
$2^{k-1}\le N<2^k-1$. \endmark

\section дАЛЬНЕЙШИЙ АНАЛИЗ БИНАРНОГО ПОИСКА. [рЕКОМЕНДУЕМ НЕ 
ИНТЕРЕСУЮЩИМСЯ МАТЕМАТИКОЙ ПЕРЕЙТИ СРАЗУ К СООТНОШЕНИЯМ~(4).] 
пРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВА ПОЗВОЛЯЕТ ЛЕГКО ПОДСЧИТАТЬ \emph{СРЕДНЕЕ} 
ЧИСЛО СРАВНЕНИЙ. чЕРЕЗ $C_N$ ОБОЗНАЧИМ СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ ПРИ УДАЧНОМ 
ПОИСКЕ В ПРЕДПОЛОЖЕНИИ, ЧТО КАЖДЫЙ ИЗ $N$~КЛЮЧЕЙ С РАВНОЙ ВЕРОЯТНОСТЬЮ 
ЯВЛЯЕТСЯ АРГУМЕНТОМ ПОИСКА. сРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ~$C'_N$ СООТВЕТСТВУЕТ 
НЕУДАЧНОМУ ПОИСКУ; ПРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ ИНТЕРВАЛЫ (ИХ $N+1$) МЕЖДУ 
КЛЮЧАМИ И ВНЕ КРАЙНИХ ЗНАЧЕНИЙ РАВНОВЕРОЯТНЫ. иМЕЕМ ПО ОПРЕДЕЛЕНИЮ 
ДЛИН ВНУТРЕННЕГО И ВНЕШНЕГО ПУТИ
$$
\eqalign{
C_N&=1+{\hbox{\rm дЛИНА ВНУТРЕННЕГО ПУТИ ДЕРЕВА}\over N};\cr
C'_N&={\hbox{\rm дЛИНА ВНЕШНЕГО ПУТИ ДЕРЕВА}\over N+1}.\cr
}
$$
иЗ ФОРМУЛЫ~(2.3.4.5-3) ВИДНО, ЧТО ДЛИНА ВНЕШНЕГО ПУТИ НА~$2N$ БОЛЬШЕ ДЛИНЫ 
ВНУТРЕННЕГО ПУТИ; ОТСЮДА СЛЕДУЕТ ДОВОЛЬНО НЕОЖИДАННОЕ СООТНОШЕНИЕ МЕЖДУ 
$C_N$ И~$C'_N$
$$
C_N=\left(1+{1\over N}\right) C'_N-1.
\eqno(2)
$$
эТА ФОРМУЛА, ПОЛУЧЕННАЯ хИББАРДОМ [{\sl JACM,\/} {\bf 9} (1962), 16--17],
 СПРАВЕДЛИВА ДЛЯ ВСЕХ МЕТОДОВ ПОИСКА, СООТВЕТСТВУЮЩИХ БИНАРНЫМ ДЕРЕВЬЯМ, 
Т.~Е.~ДЛЯ ВСЕХ МЕТОДОВ, НЕ СОДЕРЖАЩИХ ЛИШНИХ СРАВНЕНИЙ. дИСПЕРСИЯ~$C_N$ 
ТАКЖЕ МОЖЕТ БЫТЬ ВЫРАЖЕНА ЧЕРЕЗ ДИСПЕРСИЮ~$C'_N$ (СМ.~УПР.~25).

иЗ ПРИВЕДЕННЫХ ФОРМУЛ ВИДНО, ЧТО "НАИЛУЧШЕМУ" СПОСОБУ ПОИСКА ПУТЕМ 
СРАВНЕНИЙ СООТВЕТСТВУЕТ ДЕРЕВО С МИНИМАЛЬНОЙ ДЛИНОЙ ВНЕШНЕГО ПУТИ СРЕДИ 
ВСЕХ БИНАРНЫХ ДЕРЕВЬЕВ, СОДЕРЖАЩИХ $N$~ВНУТРЕННИХ УЗЛОВ. к СЧАСТЬЮ, 
МОЖНО ДОКАЗАТЬ, ЧТО АЛГОРИТМ~B ОПТИМАЛЕН В ЭТОМ СМЫСЛЕ, ТАК КАК БИНАРНОЕ 
ДЕРЕВО ИМЕЕТ МИНИМАЛЬНУЮ ДЛИНУ ПУТИ ТОГДА И ТОЛЬКО ТОГДА, КОГДА 
ВСЕ ВНЕШНИЕ УЗЛЫ НАХОДЯТСЯ НА ОДНОМ ИЛИ ДВУХ СОСЕДНИХ 
УРОВНЯХ. (сМ.~УПР.~5.3.1-20.) сЛЕДОВАТЕЛЬНО, ДЛИНА ВНЕШНЕГО ПУТИ 
БИНАРНОГО ДЕРЕВА, СООТВЕТСТВУЮЩЕГО АЛГОРИТМУ~B, РАВНА
$$
(N+1)(\floor{\log_2  N}+2)-2^{\floor{\log_2 N}+1}.
\eqno(3)
$$
(сМ.~(5.3.1-33).) иСПОЛЬЗУЯ~(3) И~(2), МОЖНО ТОЧНО ВЫЧИСЛИТЬ СРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ, ЕСЛИ ПРЕДПОЛОЖИТЬ, ЧТО ВСЕ АРГУМЕНТЫ ПОИСКА РАВНОВЕРОЯТНЫ:
{\def\f#1,#2/#3.{#1{#2\over#3}}
\ctable{
\hfill$#$\bskip&&$#$\bskip\hfill\cr
   N=&1&  2     &  3     &  4     &  5     &  6     &  7     &  8     &  9      &  10     &  11     & 12       & 13       &  14      &  15     &  16\cr
 C_N=&1&\f1,1/2.&\f1,2/3.&  2     &\f2,1/5.&\f2,2/6.&\f2,3/7.&\f2,5/8.&\f2,7/9. &\f2,9/10.&  3      &\f3,1/12. &\f3,2/13. &\f3,3/14. &\f3,4/15.&\f3,6/16.\cr
C'_N=&1&\f1,2/3.&  2     &\f2,2/5.&\f2,4/6.&\f2,6/7.&  3     &\f3,2/9.&\f3,4/10.&\f3,6/11.&\f3,8/12.&\f3,10/13.&\f3,12/14.&\f3,14/15.&  4      &\f4,2/17.\cr
}
}
%%489
в ОБЩЕМ СЛУЧАЕ, ЕСЛИ $k=\floor{\log_2 N}$, ИМЕЕМ (СР.~С~(5.3.1-34))
$$
\matrix{
\hfill C_N &=k+1-(2^{k+1}-k-2)/N\hfill&=\log_2 N-1+\varepsilon+(k+2)/N;\hfill\cr
\hfill C'_N&=k+2-2^{k+1}/(N+1)  \hfill&=\log_2N+\varepsilon',\hfill\cr
}
\eqno(4)
$$
ГДЕ $0\le\varepsilon$, $\varepsilon'<0.0861$.

иТАК, АЛГОРИТМ~B ТРЕБУЕТ МАКСИМУМ $\floor{\log_2 N} +1$~СРАВНЕНИЙ;
СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ ПРИ УДАЧНОМ ПОИСКЕ ПРИБЛИЖЕННО РАВНО~$\log_2N-1$. 
нИ ОДИН МЕТОД, ОСНОВАННЫЙ НА СРАВНЕНИИ КЛЮЧЕЙ, НЕ МОЖЕТ ДАТЬ ЛУЧШИХ 
РЕЗУЛЬТАТОВ. сРЕДНЕЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ в СОСТАВЛЯЕТ ПРИМЕРНО
$$
\eqalign{
&(18\log_2N-15)u\rem{ ДЛЯ УДАЧНОГО ПОИСКА;}\cr 
&(18\log_2N+13)u\rem{ ДЛЯ НЕУДАЧНОГО ПОИСКА}\cr
}
\eqno(5)
$$
(ПРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ ИСХОДЫ ПОИСКА РАВНОВЕРОЯТНЫ).

\section оДНА ВАЖНАЯ МОДИФИКАЦИЯ. сОБЛАЗНИТЕЛЬНО ВМЕСТО ТРЕХ УКАЗАТЕЛЕЙ 
$l$, $i$, $u$ ИСПОЛЬЗОВАТЬ ЛИШЬ ДВА: ТЕКУЩЕЕ ПОЛОЖЕНИЕ~$i$ И ВЕЛИЧИНУ ЕГО 
ИЗМЕНЕНИЯ~$\delta$; ПОСЛЕ КАЖДОГО СРАВНЕНИЯ, НЕ ДАВШЕГО РАВЕНСТВА, МЫ 
МОГЛИ БЫ УСТАНОВИТЬ $i\asg i\pm\delta$ И~$\delta\asg\delta/2$ 
(ПРИБЛИЗИТЕЛЬНО). эТОТ ПУТЬ РЕАЛИЗУЕМ, НО ОН ТРЕБУЕТ ОСОБОЙ АККУРАТНОСТИ В 
ДЕТАЛЯХ, КАК В ПРИВЕДЕННОМ НИЖЕ АЛГОРИТМЕ;
БОЛЕЕ ПРОСТЫЕ ПОДХОДЫ ОБРЕЧЕНЫ НА НЕУДАЧУ!

\alg U.(оДНОРОДНЫЙ БИНАРНЫЙ ПОИСК.) аЛГОРИТМ СЛУЖИТ ДЛЯ ОТЫСКАНИЯ 
АРГУМЕНТА~$K$ В ТАБЛИЦЕ ЗАПИСЕЙ $R_1$, $R_2$,~\dots, $R_N$, КЛЮЧИ КОТОРЫХ 
РАСПОЛОЖЕНЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ: $K_1<K_2<\ldots<K_N$. пРИ ЧЕТНОМ~$N$ 
ИНОГДА ПРОИСХОДИТ ОБРАЩЕНИЕ К ФИКТИВНОМУ КЛЮЧУ~$K_0$, КОТОРЫЙ НЕОБХОДИМО 
УСТАНОВИТЬ РАВНЫМ~$-\infty$ (ИЛИ ЛЮБОЙ ВЕЛИЧИНЕ, МЕНЬШЕЙ~$K$. 
пРЕДПОЛАГАЕТСЯ, ЧТО $N\ge1$.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $i\asg\ceil{N/2}$, $m\asg\floor{N/2}$.

\st[сРАВНЕНИЕ.] еСЛИ $K<K_i$, ТО ПЕРЕЙТИ НА~\stp{3}; ЕСЛИ $K>K_i$, ТО 
ПЕРЕЙТИ НА~\stp{4}; ПРИ $K=K_i$ АЛГОРИТМ ОКАНЧИВАЕТСЯ УДАЧНО.

\st[уМЕНЬШЕНИЕ $i$.] (мЫ ОПРЕДЕЛИЛИ ПОЛОЖЕНИЕ ИНТЕРВАЛА, ГДЕ НУЖНО 
ПРОДОЛЖАТЬ ПОИСК. оН СОДЕРЖИТ $m$ ИЛИ $m-1$~ЗАПИСЕЙ; $i$ УКАЗЫВАЕТ НА 
ПЕРВЫЙ ЭЛЕМЕНТ СПРАВА ОТ ИНТЕРВАЛА.) еСЛИ $m=0$, ТО АЛГОРИТМ ОКАНЧИВАЕТСЯ 
НЕУДАЧНО. в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $i\asg i-\ceil{m/2}$; 
$m\asg\floor{m/2}$ И ВЕРНУТЬСЯ НА~\stp{2}.

\st[уВЕЛИЧЕНИЕ $i$.] (сИТУАЦИЯ ТА ЖЕ, ЧТО И В ШАГЕ~\stp{3}, 
ТОЛЬКО $i$~УКАЗЫВАЕТ НА ПЕРВЫЙ ЭЛЕМЕНТ \emph{СЛЕВА} ОТ ИНТЕРВАЛА.) 
еСЛИ $m=0$, ТО АЛГОРИТМ ОКАНЧИВАЕТСЯ НЕУДАЧНО. в ПРОТИВНОМ
СЛУЧАЕ УСТАНОВИТЬ $i\asg i+\ceil{m/2}$; $m\asg\floor{m/2}$ И ВЕРНУТЬСЯ НА~\stp{2}.
\algend

нА РИС.~6 ПРЕДСТАВЛЕНО БИНАРНОЕ ДЕРЕВО, СООТВЕТСТВУЮЩЕЕ ПОИСКУ ПРИ $N=10$. 
пРИ НЕУДАЧНОМ ПОИСКЕ КАК РАЗ ПЕРЕД ОКОНЧАНИЕМ
%%490
РАБОТЫ АЛГОРИТМА МОЖЕТ ПРОИЗВОДИТЬСЯ ЛИШНЕЕ СРАВНЕНИЕ; УЗЛЫ, 
ОТВЕЧАЮЩИЕ ЭТИМ СРАВНЕНИЯМ, ЗАШТРИХОВАНЫ. дАННЫЙ ПРОЦЕСС ПОИСКА МОЖНО 
НАЗВАТЬ \emph{ОДНОРОДНЫМ}, ТАК КАК РАЗНОСТЬ МЕЖДУ ЧИСЛОМ В УЗЛЕ 
УРОВНЯ~$\ell$ И ЧИСЛОМ В УЗЛЕ-ПРЕДШЕСТВЕННИКЕ УРОВНЯ~$\ell-1$ ЕСТЬ 
ПОСТОЯННАЯ ВЕЛИЧИНА~$\delta$ ДЛЯ ВСЕХ УЗЛОВ УРОВНЯ~$\ell$.
оБОСНОВАТЬ ПРАВИЛЬНОСТЬ АЛГОРИТМА~U МОЖНО СЛЕДУЮЩИМ ОБРАЗОМ. пРЕДПОЛОЖИМ, 
ЧТО ПОИСК НУЖНО ПРОИЗВЕСТИ В ИНТЕРВАЛЕ
\picture{рИС. 6. бИНАРНОЕ ДЕРЕВО ДЛЯ "ОДНОРОДНОГО" БИНАРНОГО ПОИСКА ($N=10$).}
ДЛИНЫ~$n-1$; СРАВНЕНИЕ СО СРЕДНИМ ЭЛЕМЕНТОМ (ЕСЛИ $n$ ЧЕТНО) ИЛИ С ОДНИМ 
ИЗ ДВУХ СРЕДНИХ (ЕСЛИ $n$ НЕЧЕТНО) ВЫДЕЛЯЕТ ДВА ИНТЕРВАЛА 
ДЛИНЫ~$\floor{n/2}-1$ И~$\ceil{n/2}-1$. пОСЛЕ ПОВТОРЕНИЯ ЭТОЙ ПРОЦЕДУРЫ 
$k$~РАЗ МЫ ПОЛУЧИМ $2^k$~ИНТЕРВАЛОВ С МИНИМАЛЬНОЙ ДЛИНОЙ~$\floor{n/2^k}-1$ 
И МАКСИМАЛЬНОЙ ДЛИНОЙ~$\ceil{n/2^k}-1$. сЛЕДОВАТЕЛЬНО, НА КАЖДОМ ЭТАПЕ 
ДЛИНЫ ДВУХ ИНТЕРВАЛОВ РАЗЛИЧАЮТСЯ САМОЕ БОЛЬШЕЕ НА~1, ЧТО ДЕЛАЕТ ВОЗМОЖНЫМ 
ВЫБОР ПОДХОДЯЩЕГО "СРЕДНЕГО" ЭЛЕМЕНТА БЕЗ ЗАПОМИНАНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ 
ТОЧНЫХ ЗНАЧЕНИЙ ДЛИН.

вАЖНОЕ ПРЕИМУЩЕСТВО АЛГОРИТМА~U СОСТОИТ В ТОМ, ЧТО НАМ СОВСЕМ НЕ НУЖНО 
СОХРАНЯТЬ ЗНАЧЕНИЕ~$m$; НУЖНО ЛИШЬ ССЫЛАТЬСЯ НА КОРОТЕНЬКУЮ ТАБЛИЦУ 
ЗНАЧЕНИЙ~$\delta$ ДЛЯ КАЖДОГО УРОВНЯ. тАКИМ ОБРАЗОМ, АЛГОРИТМ СВОДИТСЯ К 
СЛЕДУЮЩЕЙ ПРОЦЕДУРЕ, ОДИНАКОВО ХОРОШЕЙ И ДЛЯ ДВОИЧНЫХ, И ДЛЯ ДЕСЯТИЧНЫХ эвм.

\alg C.(оДНОРОДНЫЙ БИНАРНЫЙ ПОИСК.) аЛГОРИТМ АНАЛОГИЧЕН АЛГОРИТМУ~U, НО 
ВМЕСТО ВЫЧИСЛЕНИЙ, ОТНОСЯЩИХСЯ К~$m$, ИСПОЛЬЗУЕТ ВСПОМОГАТЕЛЬНУЮ ТАБЛИЦУ ВЕЛИЧИН
$$
|DELTA|[j]=\floor{{N+2^{j-1}\over 2^j}}=\left({N\over 2^j}\right)
\hbox{ ОКРУГЛЕННОЕ}; \qquad 1\le j \le \floor{\log_2 N}+2.
\eqno(6)
$$
\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $i\asg|DELTA| [1]$, $j\asg2$.
%%491
\st[сРАВНЕНИЕ:] еСЛИ $K<K_i$, ТО ПЕРЕЙТИ НА \stp{3}; ЕСЛИ $K>K_i$, ТО 
ПЕРЕЙТИ НА~\stp{4}. пРИ $K=K_i$ АЛГОРИТМ ОКАНЧИВАЕТСЯ УДАЧНО.

\st[уМЕНЬШЕНИЕ $i$.] еСЛИ $|DELTA|[j]=0$, ТО АЛГОРИТМ ОКАНЧИВАЕТСЯ 
НЕУДАЧНО. в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $i\asg i-|DELTA|[j]$,  $j\asg j+1$ 
И ВЕРНУТЬСЯ НА~\stp{2}.

\st[уВЕЛИЧЕНИЕ~$i$.] еСЛИ $|DELTA|[j]=0$, АЛГОРИТМ ОКАНЧИВАЕТСЯ НЕУДАЧНО. 
в ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ $i\asg i+|DELTA|[j]$, $j\asg j+1$ И 
ВЕРНУТЬСЯ НА~\stp{2}. 
\algend

в УПР.~8 БУДЕТ ПОКАЗАНО, ЧТО АЛГОРИТМ ССЫЛАЕТСЯ НА ВСПОМОГАТЕЛЬНЫЙ 
КЛЮЧ~$K_0=-\infty$ ЛИШЬ ПРИ ЧЕТНЫХ~$N$.

\prog C.(оДНОРОДНЫЙ БИНАРНЫЙ ПОИСК.) эТА ПРОГРАММА НА БАЗЕ АЛГОРИТМА~C 
ПРОДЕЛЫВАЕТ ТУ ЖЕ РАБОТУ, ЧТО И ПРОГРАММА~B. иСПОЛЬЗУЮТСЯ $|rA|\equiv K$, 
$|rI1|\equiv i$, $|rI2|\equiv j$, 
$|rI3|\equiv |DELTA| [j]$.
\code
START  & ENT1 & N+1/2  & 1     & C1. нАЧАЛЬНАЯ УСТАНОВКА.
       & ENT2 & 2      & 1     & $j\asg 2$.
       & LDA  & к      & 1     &
       & JMP  & 2F     & 1     &
3H     & JE   & SUCCESS& C1    & пЕРЕХОД, ЕСЛИ $K=K_i$.
       & J3Z  & FAILURE& C1-S  & пЕРЕХОД, ЕСЛИ $|DELTA|[j]=0$.
       & DEC1 & 0,3    & C1-S-A& C3.  уМЕНЬШЕНИЕ~$i$.
5H     & INC2 & 1      & C-1   & $j\asg j+1$.
2H     & LD3  & DELTA,2& C     & C2. сРАВНЕНИЕ.
       & смра & KEY.1  & C     &
       & JLE  & 3B     & C     & пЕРЕХОД, ЕСЛИ $K\le K_i$.
       & INC1 & 0,3    & C2    & C4. уВЕЛИЧЕНИЕ $i$.
       & J3NZ & 5B     & C2    & пЕРЕХОД, ЕСЛИ $|DELTA|[j]\ne0$.
FAILURE& EQU  & *      & 1-S   & вЫХОД, ЕСЛИ НЕТ В ТАБЛИЦЕ.
\endcode
\progend

пРИ УДАЧНОМ ПОИСКЕ ЭТОТ АЛГОРИТМ СООТВЕТСТВУЕТ БИНАРНОМУ ДЕРЕВУ С ТОЙ ЖЕ 
ДЛИНОЙ ВНУТРЕННЕГО ПУТИ, ЧТО И АЛГОРИТМ~в, ПОЭТОМУ СРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ~$C_N$ ДАЕТСЯ ФОРМУЛОЙ~(4). пРИ НЕУДАЧНОМ ПОИСКЕ АЛГОРИТМ~C 
ВСЕГДА СОВЕРШАЕТ РОВНО $\floor{\log_2N}+1$~СРАВНЕНИЙ. пОЛНОЕ ВРЕМЯ РАБОТЫ 
ПРОГРАММЫ~C НЕ ВПОЛНЕ СИММЕТРИЧНО ПО ОТНОШЕНИЮ К ЛЕВЫМ И ПРАВЫМ ВЕТВЯМ, 
ТАК КАК $C1$ ИМЕЕТ ВЕС, БОЛЬШИЙ ЧЕМ $C2$, НО В УПР.~9 БУДЕТ ПОКАЗАНО, 
ЧТО СЛУЧАЙ $K>K_i$ ВСТРЕЧАЕТСЯ ПРИМЕРНО ТАК ЖЕ ЧАСТО, КАК И~$K<K_i$;
СЛЕДОВАТЕЛЬНО, ПРОГРАММА~C ТРЕБУЕТ ПРИБЛИЗИТЕЛЬНО
$$
\matrix{
(8.5\log_2N-6)u \hfill& \hbox{НА УДАЧНЫЙ ПОИСК};\cr
(8.5\floor{\log_2N}+12)u &\hbox{НА НЕУДАЧНЫЙ ПОИСК.}\cr
}
\eqno(7)
$$
%%492
эТО БОЛЕЕ ЧЕМ В ДВА РАЗА БЫСТРЕЕ ПРОГРАММЫ~B, ПРИЧЕМ НЕ ИСПОЛЬЗУЮТСЯ 
СПЕЦИАЛЬНЫЕ СВОЙСТВА ДВОИЧНЫХ эвм, В ТО ВРЕМЯ КАК В ФОРМУЛЕ~(5) 
ПРЕДПОЛАГАЕТСЯ, ЧТО \MIX{} ИМЕЕТ КОМАНДУ "ДВОИЧНЫЙ СДВИГ ВПРАВО".

дРУГАЯ МОДИФИКАЦИЯ БИНАРНОГО ПОИСКА, ПРЕДЛОЖЕННАЯ В 1971~Г. л.~э.~шЕРОМ, 
НА НЕКОТОРЫХ эвм ДОПУСКАЕТ ЕЩЕ БОЛЕЕ БЫСТРУЮ РЕАЛИЗАЦИЮ, ТАК КАК ОНА 
ОДНОРОДНА ПОСЛЕ ПЕРВОГО
\picture{рИС. 7. бИНАРНОЕ ДЕРЕВО ДЛЯ ПОЧТА ОДНОРОДНОГО ПОИСКА шЕРА ($N=10$).}
ШАГА И НЕ ТРЕБУЕТ ВСПОМОГАТЕЛЬНОЙ ТАБЛИЦЫ. сНАЧАЛА МЫ СРАВНИВАЕМ $K$ 
И~$K_i$, ГДЕ $i=2^k$, $k=\floor{\log_2 N}$. еСЛИ $K<K_i$, МЫ ИСПОЛЬЗУЕМ 
ОДНОРОДНЫЙ ПОИСК С ПОСЛЕДОВАТЕЛЬНОСТЬЮ $\delta=2^{k-1}$, $2^{k-2}$,~\dots, 
$1$, $0$. с ДРУГОЙ СТОРОНЫ, ПРИ $K>K_i$ И~$N>2^k$ УСТАНАВЛИВАЕМ 
$i=i'=N+1-2^\ell$, ГДЕ $\ell=\floor{\log_2(N-2^k)}+1$, И, ДЕЛАЯ ВИД, ЧТО 
ПЕРВЫМ СРАВНЕНИЕМ БЫЛО $K>K_{i'}$, ИСПОЛЬЗУЕМ ОДНОРОДНЫЙ ПОИСК С 
$\delta=2^{\ell-1}$, $2^{\ell-2}$,~\dots, $1$, $0$.

рИСУНОК~7 ИЛЛЮСТРИРУЕТ МЕТОД шЕРА ПРИ $N=10$. в МЕТОДЕ шЕРА НИКОГДА НЕ 
ТРЕБУЕТСЯ БОЛЕЕ $\floor{\log_2 N}+1$~СРАВНЕНИЙ; СЛЕДОВАТЕЛЬНО, ОН ДАЕТ 
ОДНО ИЗ ЛУЧШИХ СРЕДНИХ ЧИСЕЛ СРАВНЕНИЯ, НЕСМОТРЯ НА ТО ЧТО ИНОГДА ПРОХОДИТ 
ЧЕРЕЗ НЕСКОЛЬКО ПОСЛЕДОВАТЕЛЬНЫХ ИЗБЫТОЧНЫХ ШАГОВ (СР. С УПР.~12).

еЩЕ ОДНА МОДИФИКАЦИЯ БИНАРНОГО ПОИСКА, УЛУЧШАЮЩАЯ ВСЕ РАССМОТРЕННЫЕ МЕТОДЫ 
ПРИ ОЧЕНЬ БОЛЬШИХ $N$, ОБСУЖДАЕТСЯ В УПР.~23. в УПР.~24 ИЗЛОЖЕН ЕЩЕ БОЛЕЕ 
БЫСТРЫЙ МЕТОД!

\section фИБОНАЧЧИЕВ ПОИСК. пРИ РАССМОТРЕНИИ МНОГОФАЗНОГО 
СЛИЯНИЯ (П.~5.4.2) МЫ ВИДЕЛИ, ЧТО ЧИСЛА фИБОНАЧЧИ МОГУТ ИГРАТЬ РОЛЬ,
 АНАЛОГИЧНУЮ СТЕПЕНЯМ~$2$. пОХОЖЕЕ ЯВЛЕНИЕ ИМЕЕТ МЕСТО И В СЛУЧАЕ ПОИСКА,
 КОГДА С ПОМОЩЬЮ ЧИСЕЛ фИБОНАЧЧИ СОЗДАЮТСЯ МЕТОДЫ, СПОСОБНЫЕ СОПЕРНИЧАТЬ С 
БИНАРНЫМ ПОИСКОМ. пРЕДЛАГАЕМЫЙ МЕТОД ДЛЯ НЕКОТОРЫХ эвм ПРЕДПОЧТИТЕЛЬНЕЕ 
БИНАРНОГО, ТАК КАК ОН ВКЛЮЧАЕТ ЛИШЬ СЛОЖЕНИЕ И ВЫЧИТАНИЕ; НЕТ 
НЕОБХОДИМОСТИ В ДЕЛЕНИИ НА~$2$. сЛЕДУЕТ ОТЛИЧАТЬ ПРОЦЕДУРУ, КОТОРУЮ МЫ СОБИ-
%%493
РАЕМСЯ ОБСУЖДАТЬ, ОТ ИЗВЕСТНОЙ ЧИСЛЕННОЙ ПРОЦЕДУРЫ "ФИБОНАЧЧИЕВА ПОИСКА",
 КОТОРАЯ ИСПОЛЬЗУЕТСЯ ДЛЯ НАХОЖДЕНИЯ МАКСИМУМА ОДНОВЕРШИННОЙ ФУНКЦИИ 
[СР.~С~Fibonacci Quarterly, 4 (1966), 265--269]; СХОЖЕСТЬ НАЗВАНИЙ ВЕДЕТ К 
НЕКОТОРОЙ ПУТАНИЦЕ.

нА ПЕРВЫЙ ВЗГЛЯД ФИБОНАЧЧИЕВ ПОИСК КАЖЕТСЯ ВЕСЬМА ТАИНСТВЕННЫМ; ЕСЛИ 
ПРОСТО ВЗЯТЬ ПРОГРАММУ И ПОПЫТАТЬСЯ ОБоЯСНИТЬ ЕЕ РАБОТУ, ТО СОЗДАСТСЯ 
ВПЕЧАТЛЕНИЕ, ЧТО ОНА РАБОТАЕТ С ПОМОЩЬЮ МАГИИ. нО ТУМАН ТАИНСТВЕННОСТИ 
РАССЕЕТСЯ, КАК ТОЛЬКО МЫ ПОСТРОИМ
\picture{рИС. 8.   дЕРЕВО фИБОНАЧЧИ ПОРЯДКА 6.}
СООТВЕТСТВУЮЩЕЕ ДЕРЕВО ПОИСКА. пОЭТОМУ ИЗУЧЕНИЕ РАССМАТРИВАЕМОГО МЕТОДА 
НАЧНЕМ С РАССКАЗА О "ФИБОНАЧЧИЕВЫХ ДЕРЕВЬЯХ".

нА РИС.~8 ИЗОБРАЖЕНО ДЕРЕВО фИБОНАЧЧИ ПОРЯДКА~$6$. зАМЕТЬТЕ, ЧТО ОНО 
НЕСКОЛЬКО БОЛЬШЕ НАПОМИНАЕТ РЕАЛЬНЫЙ КУСТ, ЧЕМ РАССМАТРИВАВШИЕСЯ РАНЕЕ 
ДЕРЕВЬЯ, ВОЗМОЖНО, ПОТОМУ, ЧТО МНОГИЕ ПРИРОДНЫЕ ПРОЦЕССЫ УДОВЛЕТВОРЯЮТ 
ЗАКОНУ фИБОНАЧЧИ. вООБЩЕ ФИБОНАЧЧИЕВО ДЕРЕВО ПОРЯДКА~$k$ ИМЕЕТ 
$F_{k+1}-1$~ВНУТРЕННИХ (КРУГЛЫХ) УЗЛОВ И~$F_{k+1}$~ВНЕШНИХ (КВАДРАТНЫХ) 
УЗЛОВ; ОНО СТРОИТСЯ СЛЕДУЮЩИМ ОБРАЗОМ:

{\medskip\narrower
\item{еСЛИ}~$k=0$ ИЛИ~$k=1$, ДЕРЕВО СВОДИТСЯ ПРОСТО К~\leaf{0}.

\item{еСЛИ}~$k\ge2$, КОРНЕМ ЯВЛЯЕТСЯ~\node{F_k}; ЛЕВОЕ ПОДДЕРЕВО ЕСТЬ 
ДЕРЕВО фИБОНАЧЧИ ПОРЯДКА~$k-1$; ПРАВОЕ ПОДДЕРЕВО ЕСТЬ ДЕРЕВО фИБОНАЧЧИ 
ПОРЯДКА~$k-2$ С ЧИСЛАМИ В УЗЛАХ, УВЕЛИЧЕННЫМИ НА~$F_k$.

\medskip}

\noindent зАМЕТИМ, ЧТО, ЗА ИСКЛЮЧЕНИЕМ ВНЕШНИХ УЗЛОВ, ЧИСЛА, 
СООТВЕТСТВУЮЩИЕ ПРЕЕМНИКАМ КАЖДОГО ВНУТРЕННЕГО УЗЛА, ОТЛИЧАЮТСЯ ОТ ЧИСЛА 
В ЭТОМ УЗЛЕ НА ОДНУ И ТУ ЖЕ ВЕЛИЧИНУ, А ИМЕННО НА ЧИСЛО фИБОНАЧЧИ. тАК, 
$5=8-F_4$, $11=8+F_4$ (РИС.~8). еСЛИ РАЗНОСТЬ БЫЛА РАВНА~$F_j$, ТО НА 
СЛЕДУЮЩЕМ УРОВНЕ СООТВЕТСТВУЮЩАЯ
%%494
РАЗНОСТЬ СОСТАВИТ ДЛЯ ЛЕВОЙ ВЕТВИ $F_{j-1}$, А ДЛЯ ПРАВОЙ~$F_{j-2}$. тАК,
 НАПРИМЕР, $3=5-F_3$, a~$10=11-F_2$.

эТИ НАБЛЮДЕНИЯ В СОВОКУПНОСТИ С ПОДХОДЯЩИМ МЕХАНИЗМОМ РАСПОЗНАВАНИЯ 
ВНЕШНИХ УЗЛОВ ДАЮТ

\alg F.(фИБОНАЧЧИЕВ ПОИСК.) аЛГОРИТМ ПРЕДНАЗНАЧАЕТСЯ ДЛЯ ПОИСКА 
АРГУМЕНТА~$K$ В ТАБЛИЦЕ ЗАПИСЕЙ $R_1$, $R_2$,~\dots, $R_N$, РАСПОЛОЖЕННЫХ 
В ПОРЯДКЕ ВОЗРАСТАНИЯ КЛЮЧЕЙ $K_1<K_2<\ldots<K_N$.

дЛЯ УДОБСТВА ОПИСАНИЯ ПРЕДПОЛАГАЕТСЯ, ЧТО $N+1$ ЕСТЬ 
ЧИСЛО фИБОНАЧЧИ~$F_{k+1}$. пОДХОДЯЩЕЙ НАЧАЛЬНОЙ УСТАНОВКОЙ ДАННЫЙ МЕТОД 
МОЖНО СДЕЛАТЬ ПРИГОДНЫМ ДЛЯ ЛЮБОГО~$N$ (СМ.~УПР.~14).

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $i\asg F_k$, $p\asg F_{k-1}$, 
$q\asg F_{k-2}$. (в ЭТОМ АЛГОРИТМЕ $p$ И~$q$ ОБОЗНАЧАЮТ ПОСЛЕДОВАТЕЛЬНЫЕ 
ЧИСЛА фИБОНАЧЧИ.)

\st[сРАВНЕНИЕ.] еСЛИ $K<K_i$, ТО ПЕРЕЙТИ НА~\stp{3}; ЕСЛИ $K>K_i$, ТО 
ПЕРЕЙТИ НА~\stp{4}; ЕСЛИ $K=K_i$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ УДАЧНО.

\st[уМЕНЬШЕНИЕ~$i$.] еСЛИ~$q=0$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ НЕУДАЧНО. 
еСЛИ~$q\ne 0$, ТО УСТАНОВИТЬ $i\asg i-q$, ЗАМЕНИТЬ $(p, q)$ НА~$(q, p-q)$ 
И ВЕРНУТЬСЯ НА~\stp{2}.

\st[уВЕЛИЧЕНИЕ~$i$.] еСЛИ~$p=1$,  АЛГОРИТМ ЗАКАНЧИВАЕТСЯ НЕУДАЧНО. 
еСЛИ~$p\ne1$, УСТАНОВИТЬ $i\asg i+q$, $p\asg p-q$, $q\asg q-p$ И ВЕРНУТЬСЯ НА~\stp{2}.
\algend

в ПРИВОДИМОЙ НИЖЕ РЕАЛИЗАЦИИ АЛГОРИТМА~F ДЛЯ МАШИНЫ \MIX\ СКОРОСТЬ 
УВЕЛИЧИВАЕТСЯ ЗА СЧЕТ ДУБЛИРОВАНИЯ ВНУТРЕННЕГО ЦИКЛА, В ОДНОМ ИЗ 
ЭКЗЕМПЛЯРОВ КОТОРОГО $p$~ХРАНИТСЯ В~|rI2|, А~$q$---В~|rI3|, В ДРУГОМ ЖЕ 
РЕГИСТРЫ МЕНЯЮТСЯ РОЛЯМИ; ЭТО УПРОЩАЕТ ШАГ~F3. нА САМОМ ДЕЛЕ ПРОГРАММА 
ХРАНИТ В РЕГИСТРАХ $p-1$ И~$q-1$, ЧТО УПРОЩАЕТ ПРОВЕРКУ "$p=1$?" В ШАГЕ~F4.

\prog F.(фИБОНАЧЧИЕВ ПОИСК.) зНАЧЕНИЯ РЕГИСТРОВ: $|rA|\equiv K$,
 $|rI1|\equiv i$, $(|rI2|, |rI3|)\equiv p-l$, $(|rI3|, |rI2|)\equiv q-l$.
\code
START & LDA & K          & 1   & F1. нАЧАЛЬНАЯ УСТАНОВКА.
      & ENT1& $F_k$      & 1   & $i\asg F_k$.
      & ENT2& $F_{k-1}-1$& 1   & $p\asg F_{k-1}$.
      & ENT3& $F_{k-2}-1$& 1   & $q\asg F_{k-2}$.
      & JMP & F2A        & 1   &   нА F2.
\twocols
F4A & INC1 &1,3    & F4B &INC1 &1,2    & C2-S-A & F4. уВЕЛИЧЕНИЕ $i$. $i\asg i+q$.
    & DEC2 &1,3    &     &DEC3 &1,2    & G2-S-A & $p\asg p-q$.
    & DEC3 &1,2    &     &DEC2 &1,3    & G2-S-A & $q\asg q-p$.
F2A & CMPA &KEY, 1 & F2в &CMPA &KEY,1  & G      & F2. сРАВНЕНИЕ.
    & JL   &F3A    &     &JL   &F3B    & G      & нА Fз, ЕСЛИ $K<K_i$.
    & JE   &SUCCESS&     &JE   &SUCCESS& G2     & вЫХОД,  ЕСЛИ $K=K_i$.
%%495
    & J2NZ &F4A    &     &J3NZ &F4B    & C2-S   & нА F4, ЕСЛИ $p\ne1$.
    & JMP  &FAILURE&     &JMP  &FAILURE& A      & вЫХОД,  ЕСЛИ НЕТ В ТАБЛИЦЕ.
F3A & DEC1 &1,3    & F3B &DEC1 &1,2    & C1     & F3. уМЕНЬШЕНИЕ~$i$. $i\asg i-q$.
    & DEC2 &1,3    &     &DEC3 &1,2    & C1     & $p\asg p-q$.
    & J3NN &F2B    &     &J2NN &F2A    & C1     & сМЕНА РЕГИСТРОВ, ЕСЛИ~$q>0$.
    & JMP  &FAILURE&     &JMP  &FAILURE& 1-S-A  & вЫХОД,  ЕСЛИ НЕТ В ТАБЛИЦЕ.
\endtwocols
\endcode
\progend

в УПР.~18 АНАЛИЗИРУЕТСЯ ВРЕМЯ РАБОТЫ ЭТОЙ ПРОГРАММЫ. рИСУНОК~8 ПОКАЗЫВАЕТ, 
А АНАЛИЗ ДОКАЗЫВАЕТ, ЧТО ВЛЕВО МЫ ИДЕМ НЕСКОЛЬКО ЧАЩЕ, ЧЕМ ВПРАВО. чЕРЕЗ 
$C$, $C1$ И~$C2-S$ ОБОЗНАЧИМ ЧИСЛО ВЫПОЛНЕНИЙ ШАГОВ F2, F3 И~F4 
СООТВЕТСТВЕННО. иМЕЕМ
$$
\eqalign{
 C&=(\ave \phi k/sqrt{5}+O(1), \max k-1), \cr
C1&=(\ave k/\sqrt{5}+O(1), \max k-1),\cr
C2-S&=(\ave \phi^{-1} k/\sqrt{5}+O(1), \max \floor{k/2}).\cr
}
\eqno(8)
$$
зНАЧИТ, ЛЕВАЯ ВЕТВЬ ВЫБИРАЕТСЯ ПРИМЕРНО В $\phi=1.618$~РАЗА ЧАЩЕ ПРАВОЙ 
(ЭТО МОЖНО БЫЛО ПРЕДВИДЕТЬ, ТАК КАК КАЖДАЯ ПРОБА ДЕЛИТ РАССМАТРИВАЕМЫЙ 
ИНТЕРВАЛ НА ДВЕ ЧАСТИ, ПРИЧЕМ ЛЕВАЯ ЧАСТЬ ПРИМЕРНО В $\phi$~РАЗ ДЛИННЕЕ 
ПРАВОЙ). сРЕДНЕЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ F СОСТАВЛЯЕТ ПРИМЕРНО
$$
\eqalign{
(6\phi k/\sqrt{5}-(2+22\phi)/5)u &\approx (6.252\log_2 N-4.6)u 
\rem {ДЛЯ УДАЧНОГО ПОИСКА;}\cr
(6\phi k/\sqrt{5}+(58/(27\phi))/5)u&\approx (6.252\log_2 N+5.8)u
\rem{ДЛЯ НЕУДАЧНОГО ПОИСКА.}\cr
}
\eqno(9)
$$
эТО НЕСКОЛЬКО ЛУЧШЕ, ЧЕМ~(7), ХОТЯ В НАИХУДШЕМ СЛУЧАЕ ПРОГРАММА~F 
РАБОТАЕТ ПРИМЕРНО $(8.6\log_2 N)u$, Т.Е. ЧУТЬ-ЧУТЬ МЕДЛЕННЕЕ ПРОГРАММЫ~с.

\section иНТЕРПОЛЯЦИОННЫЙ ПОИСК. зАБУДЕМ НА МИНУТУ О 
ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ И ПРОАНАЛИЗИРУЕМ, КАК ПРОИЗВОДИТ ПОИСК 
ЧЕЛОВЕК. иНОГДА ПОВСЕДНЕВНАЯ ЖИЗНЬ ПОДСКАЗЫВАЕТ ПУТЬ К СОЗДАНИЮ ХОРОШИХ 
АЛГОРИТМОВ.

пРЕДСТАВЬТЕ, ЧТО ВЫ ИЩЕТЕ СЛОВО В СЛОВАРЕ. мАЛОВЕРОЯТНО, ЧТО ВЫ СНАЧАЛА 
ЗАГЛЯНЕТЕ В СЕРЕДИНУ СЛОВАРЯ, ЗАТЕМ ОТСТУПИТЕ ОТ НАЧАЛА НА~$1/4$ ИЛИ~$3/4$ 
И~Т.~Д., КАК В БИНАРНОМ ПОИСКЕ, И УЖ СОВСЕМ НЕВЕРОЯТНО, ЧТО ВЫ 
ВОСПОЛЬЗУЕТЕСЬ ФИБОНАЧЧИЕВЫМ ПОИСКОМ!

еСЛИ НУЖНОЕ СЛОВО НАЧИНАЕТСЯ С БУКВЫ~A, ВЫ, ПО-ВИДИМОМУ, НАЧНЕТЕ ПОИСК 
ГДЕ-ТО В НАЧАЛЕ СЛОВАРЯ. вО МНОГИХ СЛОВАРЯХ
%%496
ИМЕЮТСЯ "ПОБУКВЕННЫЕ ВЫСЕЧКИ" ДЛЯ БОЛЬШОГО ПАЛЬЦА, КОТОРЫЕ ПОКАЗЫВАЮТ 
СТРАНИЦУ, ГДЕ НАЧИНАЮТСЯ СЛОВА НА ДАННУЮ БУКВУ. тАКУЮ ПАЛЬЦЕВУЮ ТЕХНИКУ 
ЛЕГКО ПРИСПОСОБИТЬ К эвм, ЧТО УСКОРИТ ПОИСК; СООТВЕТСТВУЮЩИЕ АЛГОРИТМЫ 
ИССЛЕДУЮТСЯ В \S~6.3.

кОГДА НАЙДЕНА ОТПРАВНАЯ ТОЧКА ДЛЯ ПОИСКА, ВАШИ ДАЛЬНЕЙШИЕ ДЕЙСТВИЯ МАЛО 
ПОХОЖИ НА РАССМОТРЕННЫЕ МЕТОДЫ. еСЛИ ВЫ ЗАМЕТИТЕ, ЧТО НУЖНОЕ СЛОВО ДОЛЖНО 
НАХОДИТЬСЯ ГОРАЗДО ДАЛЬШЕ ОТКРЫТОЙ СТРАНИЦЫ, ВЫ ПРОПУСТИТЕ ПОРЯДОЧНОЕ ИХ 
КОЛИЧЕСТВО, ПРЕЖДЕ ЧЕМ СДЕЛАТЬ СЛЕДУЮЩУЮ ПОПЫТКУ. эТО В КОРНЕ ОТЛИЧАЕТСЯ 
ОТ ПРЕДЫДУЩИХ АЛГОРИТМОВ, КОТОРЫЕ НЕ ДЕЛАЮТ РАЗЛИЧИЯ МЕЖДУ "МНОГО 
БОЛЬШЕ" И "ЧУТЬ БОЛЬШЕ".

мЫ ПРИХОДИМ К ТАКОМУ АЛГОРИТМУ, НАЗЫВАЕМОМУ "ИНТЕРПОЛЯЦИОННЫМ ПОИСКОМ": 
ЕСЛИ ИЗВЕСТНО, ЧТО $K$ ЛЕЖИТ МЕЖДУ~$K_l$ И~$K_u$, ТО СЛЕДУЮЩУЮ ПРОБУ 
ДЕЛАЕМ ПРИМЕРНО НА РАССТОЯНИИ $(u-l)(K-K_l)/(K_u-K_l)$ ОТ~$l$, ПРЕДПОЛАГАЯ,
ЧТО КЛЮЧИ ЯВЛЯЮТСЯ ЧИСЛАМИ, ВОЗРАСТАЮЩИМИ ПРИБЛИЗИТЕЛЬНО КАК АРИФМЕТИЧЕСКАЯ 
ПРОГРЕССИЯ.

 иНТЕРПОЛЯЦИОННЫЙ ПОИСК АСИМПТОТИЧЕСКИ ПРЕДПОЧТИТЕЛЬНЕЕ БИНАРНОГО; ПО 
СУЩЕСТВУ, ОДИН ШАГ БИНАРНОГО ПОИСКА УМЕНЬШАЕТ
КОЛИЧЕСТВО "ПОДОЗРЕВАЕМЫХ" ЗАПИСЕЙ С~$n$ ДО~${1\over2}n$, А ОДИН ШАГ
ИНТЕРПОЛЯЦИОННОГО (ЕСЛИ КЛЮЧИ В ТАБЛИЦЕ РАСПРЕДЕЛЕНЫ СЛУЧАЙНЫМ 
ОБРАЗОМ)---С~$n$ ДО~$\sqrt{n}$. мОЖНО ПОКАЗАТЬ, ЧТО ИНТЕРПОЛЯЦИОННЫЙ ПОИСК 
ТРЕБУЕТ В СРЕДНЕМ ОКОЛО $\log_2 \log_2 N$~ШАГОВ (УПР.~22).

к СОЖАЛЕНИЮ, ЭКСПЕРИМЕНТЫ НА эвм ПОКАЗАЛИ, ЧТО ИНТЕРПОЛЯЦИОННЫЙ ПОИСК 
УМЕНЬШАЕТ ЧИСЛО СРАВНЕНИЙ НЕ НАСТОЛЬКО, ЧТОБЫ КОМПЕНСИРОВАТЬ ВОЗНИКАЮЩИЙ 
ДОПОЛНИТЕЛЬНЫЙ РАСХОД ВРЕМЕНИ, КОГДА ТАБЛИЦА, В КОТОРОЙ ПРОИЗВОДИТСЯ ПОИСК,
 ХРАНИТСЯ ВО ВНУТРЕННЕЙ ("БЫСТРОЙ") ПАМЯТИ. рАЗНОСТЬ МЕЖДУ $\log_2 
\log_2 N$ И~$\log_2 N$ СТАНОВИТСЯ СУЩЕСТВЕННОЙ ЛИШЬ ДЛЯ ВЕСЬМА БОЛЬШИХ~$N$,
 А ТИПИЧНЫЕ ФАЙЛЫ НЕДОСТАТОЧНО СЛУЧАЙНЫ. иНТЕРПОЛЯЦИЯ УСПЕШНА ДО 
НЕКОТОРОЙ СТЕПЕНИ ЛИШЬ В ПРИМЕНЕНИИ К ПОИСКУ НА \emph{ВНЕШНИХ} 
ЗАПОМИНАЮЩИХ УСТРОЙСТВАХ. (зАМЕТИМ, ЧТО РУЧНОЙ ПРОСМОТР СЛОВАРЯ ЕСТЬ, В 
СУЩНОСТИ, НЕ ВНУТРЕННИЙ, А ВНЕШНИЙ ПОИСК; ЭТО ЯВЛЯЕТСЯ ТЕМОЙ ПОСЛЕДУЮЩИХ 
РАССМОТРЕНИЙ.)

\section иСТОРИЯ И БИБЛИОГРАФИЯ. пЕРВЫМ ИЗВЕСТНЫМ ПРИМЕРОМ ДЛИННОГО 
ПЕРЕЧНЯ ЭЛЕМЕНТОВ, УПОРЯДОЧЕННЫХ ДЛЯ ОБЛЕГЧЕНИЯ ПОИСКА, ЯВЛЯЕТСЯ 
ЗНАМЕНИТАЯ ВАВИЛОНСКАЯ ТАБЛИЦА ОБРАТНЫХ ВЕЛИЧИН Inakibit-Anu, ДАТИРУЕМАЯ 
ПРИМЕРНО 200~Г. ДО~Н.Э. эТА ГЛИНЯНАЯ ПЛАСТИНКА, ОЧЕВИДНО, ОТКРЫВАЛА СЕРИЮ 
ИЗ ТРЕХ ТАБЛИЧЕК, СОДЕРЖАЩИХ БОЛЕЕ 500 МНОГОЗНАЧНЫХ ШЕСТИДЕСЯТЕРИЧНЫХ 
ЧИСЕЛ И ОБРАТНЫХ ИМ ВЕЛИЧИН, ОТСОРТИРОВАННЫХ В 
ЛЕКСИКОГРАФИЧЕСКОМ ПОРЯДКЕ. нАПРИМЕР, ВСТРЕЧАЕТСЯ ТАКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ:
%%497
\ctable{
\bskip$#$\bskip&&\bskip$#$\bskip\cr
01&13&09&34&29&08&08&53&20&\qquad&49&12&27\cr
01&13&14&31&52&30&  &  &  &      &49&09&07&12\cr
01&13&43&40&48&  &  &  &  &      &48&49&41&15\cr
01&13&48&40&30&  &  &  &  &      & 48&46&22&59&25&25&55&33&20\cr
01&14&04&26&40&  &  &  &  &      &48&36\cr
}
сОРТИРОВКА 500 ПОДОБНЫХ ЧИСЕЛ СРЕДСТВАМИ ТЕХ ВРЕМЕН КАЖЕТСЯ ФЕНОМЕНАЛЬНОЙ. 
[сМ. ТАКЖЕ D.~е.~Knuth, {\sl CACM\/}, {\bf 15} (1972), 671--677, ГДЕ 
СОДЕРЖИТСЯ МНОГО ДОПОЛНИТЕЛЬНЫХ СВЕДЕНИЙ.]

дОВОЛЬНО ЕСТЕСТВЕННО РАСПОЛАГАТЬ ПО ПОРЯДКУ ЧИСЛА, НО ОТНОШЕНИЕ ПОРЯДКА 
МЕЖДУ БУКВАМИ ИЛИ СЛОВАМИ НЕ ПРЕДСТАВЛЯЕТСЯ САМО СОБОЙ ОЧЕВИДНЫМ. оДНАКО 
ПОСЛЕДОВАТЕЛЬНОСТИ ДЛЯ СРАВНИВАНИЯ БУКВ ПРИСУТСТВОВАЛИ УЖЕ В НАИБОЛЕЕ 
ДРЕВНИХ АЛФАВИТАХ. нАПРИМЕР, МНОГИЕ БИБЛЕЙСКИЕ ПСАЛМЫ СОДЕРЖАТ СТИХИ, 
СЛЕДУЮЩИЕ ДРУГ ЗА ДРУГОМ В СТРОГО АЛФАВИТНОМ ПОРЯДКЕ: ПЕРВЫЙ 
СТИХ НАЧИНАЕТСЯ С~АЛЕФА, ВТОРОЙ С~БЕТА И~Т.~Д.; ЭТО ОБЛЕГЧАЛО 
ЗАПОМИНАНИЕ. иНОГДА СТАНДАРТНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ БУКВ ИСПОЛЬЗОВАЛАСЬ 
СЕМИТАМИ И ГРЕКАМИ ДЛЯ ОБОЗНАЧЕНИЯ ЧИСЕЛ; НАПРИМЕР, $\alpha$, $\beta$, 
$\gamma$ ОБОЗНАЧАЛИ 1, 2, 3 СООТВЕТСТВЕННО.

оДНАКО ИСПОЛЬЗОВАНИЕ АЛФАВИТНОГО ПОРЯДКА ДЛЯ СЛОВ ЦЕЛИКОМ БЫЛО, ВЕРОЯТНО, 
ГОРАЗДО БОЛЕЕ ПОЗДНИМ ИЗОБРЕТЕНИЕМ; ВЕЩИ, ОЧЕВИДНЫЕ СЕЙЧАС ДАЖЕ ДЛЯ 
РЕБЕНКА, КОГДА-ТО ТРЕБОВАЛОСЬ ОБоЯСНЯТЬ ВЗРОСЛЫМ! нЕКОТОРЫЕ ДОКУМЕНТЫ, 
ДАТИРУЕМЫЕ ПРИМЕРНО 300~Г. ДО~Н.Э., НАЙДЕННЫЕ НА ОСТРОВАХ эГЕЙСКОГО МОРЯ,
 СОДЕРЖАТ СПИСКИ ЧЛЕНОВ НЕСКОЛЬКИХ РЕЛИГИОЗНЫХ ОБЩИН; ОНИ УПОРЯДОЧЕНЫ, НО 
ТОЛЬКО ПО ПЕРВОЙ БУКВЕ, Т.~Е. ПРЕДСТАВЛЯЮТ СОБОЙ РЕЗУЛЬТАТ ЛИШЬ ПЕРВОГО 
ПРОХОДА СЛЕВА НАПРАВО ПОРАЗРЯДНОЙ СОРТИРОВКИ. гРЕЧЕСКИЕ ПАПИРУСЫ 
134--135~Г. Н.~Э. СОДЕРЖАТ ФРАГМЕНТЫ СЧЕТОВ, В КОТОРЫХ ФАМИЛИИ 
НАЛОГОПЛАТЕЛЬЩИКОВ УПОРЯДОЧЕНЫ ПО ПЕРВЫМ ДВУМ БУКВАМ. аПОЛЛОНИЙ сОФИСТ%
\note{1}{оДИН ИЗ ГРАММАТИКОВ ДРЕВНОСТИ, РОДОМ ИЗ аЛЕКСАНДРИИ.---{\sl пРИМ. ПЕРЕВ.\/}}
ИСПОЛЬЗОВАЛ АЛФАВИТНОЕ УПОРЯДОЧЕНИЕ ПО ПЕРВЫМ ДВУМ, А ЧАСТО И ПО 
ПОСЛЕДУЮЩИМ БУКВАМ В СВОЕМ "сЛОВАРЕ ГОМЕРОВСКИХ СЛОВ" (I~ВЕК Н.~Э.). 
иЗВЕСТНО НЕСКОЛЬКО ПРИМЕРОВ БОЛЕЕ СОВЕРШЕННОГО АЛФАВИТНОГО УПОРЯДОЧЕНИЯ, 
СКАЖЕМ ВЫДАЮЩИЕСЯ "кОММЕНТАРИИ К гИППОКРАТУ" гАЛЕНА%
\note{2}{рИМСКИЙ ВРАЧ И ЕСТЕСТВОИСПЫТАТЕЛЬ, КЛАССИК АНТИЧНОЙ 
МЕДИЦИНЫ.---{\sl пРИМ. ПЕРЕВ.\/}}
 (ОКОЛО 200~Г.), НО ЭТО БЫЛО ОЧЕНЬ РЕДКИМ ЯВЛЕНИЕМ. тАК, В ХРОНИКЕ сВ.~иСИДОРА%
\note{3}{иСИДОР сЕВИЛЬСКИЙ---ИСПАНСКИЙ ЕПИСКОП, ВЫДАЮЩИЙСЯ УЧЕНЫЙ И 
ПИСАТЕЛЬ.---{\sl пРИМ. ПЕРЕВ.\/}}
 "Etymologiarum" (ОКОЛО 630~Г., КНИГА~X) СЛОВА УПОРЯДОЧЕНЫ ЛИШЬ ПО 
ПЕРВОЙ БУКВЕ, А В НАИБОЛЕЕ РАННЕМ ИЗ ИЗВЕСТНЫХ ДВУЯЗЫЧНЫХ СЛОВАРЕЙ "Corpus 
Glossary" (ОКОЛО 725~Г.) --- ТОЛЬКО ПО ДВУМ ПЕРВЫМ. дВЕ ПОСЛЕДНИЕ РАБОТЫ 
БЫЛИ, ВЕРОЯТНО, КРУПНЕЙШИМИ НЕЧИСЛОВЫМИ ФАЙЛАМИ ДАННЫХ, СКОМПИЛИРОВАННЫМИ 
В СРЕДНИЕ ВЕКА.

%% 498

тОЛЬКО В КНИГЕ дЖОВАННИ гЕНУЭЗСКОГО "Catholicon" (1286~Г.) МЫ НАХОДИМ 
ПОДРОБНОЕ ОПИСАНИЕ ПРАВИЛЬНОГО АЛФАВИТНОГО ПОРЯДКА. в ПРЕДИСЛОВИИ дЖОВАННИ 
ОБоЯСНЯЕТ, ЧТО
\ctable{
\hfill\it # \bskip & ПРЕДШЕСТВУЕТ \it #\hfill\cr
amo & bibo \cr
abeo & adeo \cr
amatus & amor \cr
imprudens & impudens\cr
iusticia & iustus\cr
polisintheton & polissenus \cr
}
(Т.~Е. ПРИВОДИТ ПРИМЕРЫ СИТУАЦИЙ, КОГДА ПОРЯДОК ОПРЕДЕЛЯЕТСЯ
ПО $1$, $2$,~\dots, $6\hbox{-Й}$~БУКВАМ) "И ДАЛЕЕ АНАЛОГИЧНО". оН ЗАМЕЧАЕТ,
 .ЧТО ОТКРЫТИЕ ЭТОГО ПРАВИЛА ПОТРЕБОВАЛО ЗНАЧИТЕЛЬНЫХ.УСИЛИЙ.
"я ПРОШУ вАС, УВАЖАЕМЫЙ ЧИТАТЕЛЬ, НЕ ПРЕЗИРАТЬ ЭТУ МОЮ БОЛЬШУЮ РАБОТУ И 
ЭТОТ ПОРЯДОК КАК НЕЧТО НИЧЕГО НЕ СТОЯЩЕЕ".
рАЗВИТИЕ АЛФАВИТНОГО ПОРЯДКА ДО МОМЕНТА ИЗОБРЕТЕНИЯ КНИГОПЕЧАТАНИЯ 
ПОДРОБНО ИЗУЧИЛ л.~у.~дЕЙЛИ ({\sl Collection Latomus,\/}
{\bf 90} (1967), 100~pp.). оН ОБНАРУЖИЛ НЕСКОЛЬКО ИНТЕРЕСНЫХ
СТАРИННЫХ РУКОПИСЕЙ, КОТОРЫЕ, НЕСОМНЕННО, ИСПОЛЬЗОВАЛИСЬ
КАК ЧЕРНОВИКИ ПРИ СОРТИРОВКЕ СЛОВ ПО ПЕРВОЙ БУКВЕ (СМ. СТР.~87--90 ЕГО 
МОНОГРАФИИ).

пЕРВЫЙ СЛОВАРЬ АНГЛИЙСКОГО ЯЗЫКА рОБЕРТА кОДРИ "Table
Alphabeticall" (London, 1604) СОДЕРЖИТ СЛЕДУЮЩИЕ ИНСТРУКЦИИ:

{\narrower

еСЛИ СЛОВО, КОТОРОЕ ТЕБЕ НУЖНО НАЙТИ, НАЧИНАЕТСЯ С~(a), СМОТРИ В НАЧАЛО 
ЭТОЙ КНИГИ, А ЕСЛИ С~(v)---ТО В КОНЕЦ. оПЯТЬ ЕСЛИ СЛОВО НАЧИНАЕТСЯ С~(ca), 
СМОТРИ В НАЧАЛО БУКВЫ~(c), А ЕСЛИ С~(cu) ТО В КОНЕЦ. и ТАК ДО КОНЦА СЛОВА.

}
\noindent иНТЕРЕСНО ЗАМЕТИТЬ, ЧТО кОДРИ ВО ВРЕМЯ ПОДГОТОВКИ СЛОВАРЯ,
 ВЕРОЯТНО, САМ УЧИЛСЯ РАССТАВЛЯТЬ СЛОВА В АЛФАВИТНОМ ПОРЯДКЕ;
НА НЕСКОЛЬКИХ ПЕРВЫХ СТРАНИЦАХ ВСТРЕЧАЕТСЯ МНОГО НЕПРАВИЛЬНО СТОЯЩИХ СЛОВ, 
ЗАТО ДАЛЬШЕ ЧИСЛО ОШИБОК СУЩЕСТВЕННО УМЕНЬШАЕТСЯ.

бИНАРНЫЙ ПОИСК ВПЕРВЫЕ УПОМЯНУТ дЖОНОМ мОЧЛИ В ДИСКУССИИ, КОТОРАЯ БЫЛА, 
ПОЖАЛУЙ, ПЕРВЫМ ОПУБЛИКОВАННЫМ ОБСУЖДЕНИЕМ МЕТОДОВ НЕЧИСЛЕННОГО 
ПРОГРАММИРОВАНИЯ [СМ. Theory and techniques for the design of electronic 
digital computers, ed. by G.~W.~Patterson, 3 (1946); 22.8--22.9]. в 
ТЕЧЕНИЕ 50-Х~ГОДОВ МЕТОД СТАНОВИТСЯ "ХОРОШО ИЗВЕСТНЫМ", НО, КАЖЕТСЯ, НИКТО 
НЕ РАЗРАБАТЫВАЛ ДЕТАЛИ АЛГОРИТМА ДЛЯ~$N\ne 2^n-1$. [сМ. A.~D.~Booth, {\sl 
Nature,\/} {\bf 176} (1955), 565;  A.~I.~Dumey, {\sl Computers and 
Automation, \/} {\bf 5} (December, 1956), 7, ГДЕ БИНАРНЫЙ ПОИСК ИМЕЕТ 
НАЗВАНИЕ "дВАДЦАТЬ ВОПРОСОВ"; D.~D.~McCracken, Digital Computer 
Programming (Wiley, 1957), 201--203; M.~Halpern, {\sl CACM\/} {\bf 1, 
2} (February, 1958), 1--3.]

%%499

пО-ВИДИМОМУ, АЛГОРИТМ БИНАРНОГО ПОИСКА, ПРИГОДНЫЙ ДЛЯ ВСЕХ~$N$, ВПЕРВЫЕ 
ОПУБЛИКОВАН бОТТЕНБРУКОМ [{\sl JACM,\/} {\bf 9} (1962), 214]. оН 
ПРЕДСТАВИЛ ИНТЕРЕСНУЮ МОДИФИКАЦИЮ АЛГОРИТМА~B, КОГДА ПРОВЕРКИ НА РАВЕНСТВО 
ОТОДВИГАЮТСЯ В КОНЕЦ АЛГОРИТМА. иСПОЛЬЗУЯ В ШАГЕ~B2 $i\asg\ceil{(l+u)/2}$ 
ВМЕСТО~$\floor{(l+u)/2}$, ОН УСТАНАВЛИВАЕТ $l\asg i$ ПРИ~$K\ge K_i$; ТОГДА 
$u-l$ УМЕНЬШАЕТСЯ ПОСЛЕ КАЖДОГО ШАГА. в КОНЦЕ, КОГДА $l=u$, ИМЕЕМ $K_l\le 
K<K_{l+1}$, И МОЖНО ПРОВЕРИТЬ, БЫЛ ЛИ ПОИСК УДАЧНЫМ, ПРОИЗВЕДЯ ЕЩЕ 
ОДНО СРАВНЕНИЕ. (оН ПРЕДПОЛАГАЛ, ЧТО ПЕРВОНАЧАЛЬНО~$K\ge K_1$.) эТА ИДЕЯ 
ПОЗВОЛЯЕТ НЕСКОЛЬКО УСКОРИТЬ ВНУТРЕННИЙ ЦИКЛ НА МНОГИХ звм; ТО ЖЕ ВЕРНО И 
ДЛЯ ВСЕХ ОБСУЖДАВШИХСЯ В ДАННОМ ПУНКТЕ АЛГОРИТМОВ, ОДНАКО ТАКОЕ ИЗМЕНЕНИЕ 
ОПРАВДАНО ЛИШЬ ДЛЯ БОЛЬШИХ~$N$ (СМ. УПР.~23).

к.~э.~аЙВЕРСОН [A Programming Language (Wiley, 1962), 141] ПРИВЕЛ 
ПРОЦЕДУРУ АЛГОРИТМА~B, НО БЕЗ РАССМОТРЕНИЯ ВОЗМОЖНОСТИ НЕУДАЧНОГО ПОИСКА.
 д.~кНУТ ({\sl CACM,\/} {\bf 6} (1963), 556--558) ПРЕДСТАВИЛ АЛГОРИТМ~B 
КАК ПРИМЕР ИСПОЛЬЗОВАНИЯ АВТОМАТИЧЕСКОЙ СИСТЕМЫ ПОСТРОЕНИЯ БЛОК-СХЕМ. 
оДНОРОДНЫЙ БИНАРНЫЙ ПОИСК (АЛГОРИТМ~C) ПРЕДЛОЖИЛ АВТОРУ В~1971~Г. 
а.~к.~чАНДРА (сТАНДФОРДСКИЙ УНИВЕРСИТЕТ).

фИБОНАЧЧИЕВ ПОИСК ИЗОБРЕТЕН д.~фЕРГЮСОНОМ [{\sl CACM,\/} {\bf 3} (1960), 
648], НО ЕГО БЛОК-СХЕМА И АНАЛИЗ БЫЛИ НЕКОРРЕКТНЫ. дЕРЕВО фИБОНАЧЧИ (БЕЗ 
МЕТОК) ПОЯВИЛОСЬ ГОРАЗДО РАНЬШЕ КАК КУРЬЕЗ В ПЕРВОМ ИЗДАНИИ ПОПУЛЯРНОЙ 
КНИГИ гУГО шТЕЙНГАУЗА "мАТЕМАТИЧЕСКИЙ КАЛЕЙДОСКОП" (м., гОСТЕХИЗДАТ, 1949) 
НА СТР.~34;
ОНО БЫЛО НАРИСОВАНО КОРНЕМ ВНИЗ И ВЫГЛЯДЕЛО, КАК ОБЫЧНОЕ ДЕРЕВО; ПРАВЫЕ 
ВЕТВИ БЫЛИ СДЕЛАНЫ В ДВА РАЗА ДЛИННЕЕ ЛЕВЫХ, ТАК ЧТО ВСЕ ЛИСТЬЯ ОКАЗАЛИСЬ 
НА ОДНОМ УРОВНЕ.

иНТЕРПОЛЯЦИОННЫЙ ПОИСК ПРЕДЛОЖЕН у.~у.~пЕТЕРСОНОМ 
[{\sl IBM J.~Res.~\& Devel.,\/} {\bf 1} (1957), 131--132]. оН ДАЛ 
ТЕОРЕТИЧЕСКУЮ ОЦЕНКУ СРЕДНЕГО 
ЧИСЛА СРАВНЕНИЙ ДЛЯ СЛУЧАЯ, КОГДА КЛЮЧИ СЛУЧАЙНО ВЫБИРАЮТСЯ ИЗ РАВНОМЕРНО 
РАСПРЕДЕЛЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, ОДНАКО ЭТИ ОЦЕНКИ РАСХОДЯТСЯ С 
ЭКСПЕРИМЕНТАЛЬНЫМИ ДАННЫМИ.

\excercises
\rex[21] дОКАЖИТЕ, ЧТО ЕСЛИ~$u<l$ В ШАГЕ~B2 БИНАРНОГО ПОИСКА, ТО 
$u=l-1$ И~$K_u<K<K_l$. (бУДЕМ СЧИТАТЬ, ЧТО $K_0=-\infty$ 
И~$K_{N+1}=\infty$, ХОТЯ АЛГОРИТМ НЕ ИСПОЛЬЗУЕТ ЭТИ ДОБАВОЧНЫЕ КЛЮЧИ, Т.~Е.
 ОНИ НЕ ДОЛЖНЫ ПРИСУТСТВОВАТЬ В ТАБЛИЦЕ.)

\rex[22] бУДЕТ ЛИ АЛГОРИТМ~B РАБОТАТЬ ПРАВИЛЬНО, ЕСЛИ (a)~ЗАМЕНИТЬ В 
ШАГЕ~B5 "$l\asg i+1$" НА~"$l\asg i$"? (b) зАМЕНИТЬ В ШАГЕ~B4 "$u\asg i-1$" 
НА "$u\asg i$"? (c) вНЕСТИ ОБА ИЗМЕНЕНИЯ?

%% 500
\ex[15] кАКОЙ МЕТОД ПОИСКА СООТВЕТСТВУЕТ ДЕРЕВУ
\picture{рИС. СТР. 500}
кАКОВО СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ ПРИ УДАЧНОМ ПОИСКЕ? ПРИ НЕУДАЧНОМ?

\ex[20] еСЛИ ПОИСК, ПРОИЗВОДИМЫЙ ПРОГРАММОЙ~S ИЗ \S~6.1 
(ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК), ТРЕБУЕТ 638~ЕДИНИЦ ВРЕМЕНИ, ТО СКОЛЬКО БУДЕТ 
РАБОТАТЬ ПРОГРАММА~B (БИНАРНЫЙ ПОИСК)?

\ex[м24] пРИ КАКИХ $N$ ПРОГРАММА~B В СРЕДНЕМ \emph{МЕДЛЕННЕЕ} 
ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА (ПРОГРАММА $6.1Q'$), ЕСЛИ ПРЕДПОЛАГАЕТСЯ, ЧТО 
ПОИСК УДАЧЕН?

\ex[28] (к.~э.~аЙВЕРСОН) в СИЛУ УПР.~5 ЛУЧШЕ ВСЕГО БЫЛО БЫ ИМЕТЬ 
НЕКИЙ "ГИБРИДНЫЙ" МЕТОД, ПЕРЕХОДЯЩИЙ ОТ БИНАРНОГО ПОИСКА К 
ПОСЛЕДОВАТЕЛЬНОМУ, КОГДА ДЛИНА ОСТАЮЩЕГОСЯ ИНТЕРВАЛА МЕНЬШЕ НЕКОТОРОЙ 
РАЗУМНО ВЫБРАННОЙ ВЕЛИЧИНЫ. нАПИШИТЕ ЭФФЕКТИВНУЮ ПРОГРАММУ ДЛЯ \MIX{} И 
ОПРЕДЕЛИТЕ НАИЛУЧШИЙ МОМЕНТ СМЕНЫ МЕТОДОВ ПОИСКА.

\rex[M22] бУДЕТ ЛИ АЛГОРИТМ~U РАБОТАТЬ ПРАВИЛЬНО, ЕСЛИ МЫ ИЗМЕНИМ ШАГ~U1 
ТАК, ЧТО (a) КАК $i$, ТАК И~$m$ УСТАНАВЛИВАЮТСЯ РАВНЫМИ $\floor{N/2}$; (b) 
КАК $i$, ТАК И~$m$ УСТАНАВЛИВАЮТСЯ РАВНЫМИ~$\ceil{N/2}$? [\emph{уКАЗАНИЕ:} 
ПРЕДПОЛОЖИМ, ЧТО ПЕРВЫЙ ШАГ ВЫГЛЯДЕЛ БЫ ТАК: "уСТАНОВИТЬ $i\asg 0$, $m\asg 
N$ (ИЛИ~$N+1$), ПЕРЕЙТИ НА~U4".]

\ex[м20] (a)~чЕМУ РАВНА СУММА~$\sum_{0\le j\le \floor{\log_2N}+2} 
|DELTA|[j]$ ПРИРАЩЕНИЙ В АЛГОРИТМЕ~C? (b)~кАКОВЫ МИНИМАЛЬНОЕ И 
МАКСИМАЛЬНОЕ ЗНАЧЕНИЯ~$i$, КОТОРЫЕ МОГУТ ПОЯВИТЬСЯ В ШАГЕ~C2?

\ex[м26] пРОВЕДИТЕ ЧАСТОТНЫЙ АНАЛИЗ ДЛЯ ПРОГРАММЫ~C И НАЙДИТЕ 
ТОЧНУЮ ЗАВИСИМОСТЬ СРЕДНИХ ЗНАЧЕНИЙ $C1$, $C2$ И~$A$ ОТ~$N$ И~$S$.

\ex[20] сУЩЕСТВУЮТ ЛИ $N>1$, ПРИ КОТОРЫХ АЛГОРИТМЫ~в И~с 
АБСОЛЮТНО ЭКВИВАЛЕНТНЫ В ТОМ СМЫСЛЕ, ЧТО ОНИ СОВЕРШАЮТ ОДИНАКОВЫЕ, 
ПОСЛЕДОВАТЕЛЬНОСТИ СРАВНЕНИЙ ПРИ ВСЕХ АРГУМЕНТАХ ПОИСКА?

\ex[21] оБоЯСНИТЕ, КАК НАПИСАТЬ \MIX-ПРОГРАММУ ДЛЯ АЛГОРИТМА~C, СОДЕРЖАЩУЮ 
ПРИМЕРНО $7\log_2 N$~КОМАНД, ВРЕМЯ РАБОТЫ КОТОРОЙ СОСТАВИТ 
ПРИБЛИЗИТЕЛЬНО $4.5\log_2 N$~ЕДИНИЦ?

\ex[20] нАРИСУЙТЕ ДЕРЕВО БИНАРНОГО ПОИСКА, СООТВЕТСТВУЮЩЕЕ МЕТОДУ шЕРА ПРИ~$N=12$.

\ex[м24] зАТАБУЛИРУЙТЕ СРЕДНИЕ ЧИСЛА СРАВНЕНИЙ В МЕТОДЕ шЕРА ДЛЯ $1\le 
N<16$, РАССМАТРИВАЯ КАК УДАЧНЫЕ, ТАК И НЕУДАЧНЫЕ ПОИСКИ.

\ex[21] оБоЯСНИТЕ, КАК ПРИСПОСОБИТЬ АЛГОРИТМ~F ДЛЯ РАБОТЫ С ЛЮБЫМ~$N\ge 1$.

\ex[21] нА РИС.~9 ИЗОБРАЖЕНА ДИАГРАММА РАЗМНОЖЕНИЯ КРОЛИКОВ В ИСХОДНОЙ 
ЗАДАЧЕ фИБОНАЧЧИ (СР.~С~П.~1.2.8). сУЩЕСТВУЕТ ЛИ ПРОСТАЯ СВЯЗЬ МЕЖДУ ЭТОЙ 
ДИАГРАММОЙ И ФИБОНАЧЧИЕВЫМ ДЕРЕВОМ РЕШЕНИЙ?

\ex[м19] пРИ КАКИХ ЗНАЧЕНИЯХ~$k$ ФИБОНАЧЧИЕВО ДЕРЕВО ПОРЯДКА~$k$ 
ОПРЕДЕЛЯЕТ ОПТИМАЛЬНУЮ ПРОЦЕДУРУ ПОИСКА, Т.~Е. ТАКУЮ, ПРИ КОТОРОЙ 
СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ МИНИМАЛЬНО?

\ex[м21] иЗ УПР.~1.2.8-34 (ИЛИ УПР.~5.4.2-10) МЫ ЗНАЕМ, ЧТО ЛЮБОЕ 
НАТУРАЛЬНОЕ ЧИСЛО~$n$ ЕДИНСТВЕННЫМ ОБРАЗОМ ПРЕДСТАВЛЯЕТСЯ В ВИДЕ СУММУ 
ЧИСЕЛ фИБОНАЧЧИ: $n=F_{a_1}+F_{a_2}+\cdots+F_{a_r}$, ГДЕ $r\ge 1$, $a_j\ge 
a_{j+1}+2$  ПРИ~$1\le j<r$ И~$a_r\ge2$. дОКАЖИТЕ, ЧТО В ФИБОНАЧЧИЕВОМ 
ДЕРЕВЕ ПОРЯДКА~$k$ ПУТЬ ОТ КОРНЯ ДО УЗЛА~\node{$n$} ИМЕЕТ ДЛИНУ~$k+1-r-a_r$.

%% 501

\picture{рИС. 9. пАРЫ КРОЛИКОВ, РАЗМНОЖАЮЩИЕСЯ ПО ПРАВИЛУ фИБОНАЧЧИ.}

\ex[м30] пРОВЕДИТЕ ЧАСТОТНЫЙ АНАЛИЗ ДЛЯ ПРОГРАММЫ~F И НАЙДИТЕ ТОЧНЫЕ 
ФОРМУЛЫ ДЛЯ СРЕДНИХ ЗНАЧЕНИЙ $C1$, $C2$ И~$A$ КАК ФУНКЦИЙ ОТ~$k$, $F_k$,
 $F_{k+1}$ И~$S$.

\ex[м42] пРОВЕДИТЕ ДЕТАЛЬНЫЙ АНАЛИЗ СРЕДНЕГО ВРЕМЕНИ РАБОТЫ АЛГОРИТМА, 
ПРЕДЛОЖЕННОГО В УПР.~14.

\ex[м22] чИСЛО СРАВНЕНИЙ, ТРЕБУЮЩИХСЯ ПРИ БИНАРНОМ ПОИСКЕ, ПРИБЛИЖЕННО 
РАВНО~$\log_2N$, ПРИ ФИБОНАЧЧИЕВОМ---$(\phi/\sqrt{5})\log_\phi N$. цЕЛЬ 
ЭТОГО УПРАЖНЕНИЯ---ПОКАЗАТЬ, ЧТО ЭТИ ФОРМУЛЫ ЯВЛЯЮТСЯ ЧАСТНЫМИ СЛУЧАЯМИ 
БОЛЕЕ ОБЩЕГО РЕЗУЛЬТАТА.

пУСТЬ $p$ И~$q$---ПОЛОЖИТЕЛЬНЫЕ ЧИСЛА И~$p+q=1$. рАССМОТРИМ АЛГОРИТМ ПОИСКА 
ПО ТАБЛИЦЕ ИЗ $N$~ЗАПИСЕЙ С ВОЗРАСТАЮЩИМИ КЛЮЧАМИ, КОТОРЫЙ, НАЧИНАЯ СО 
СРАВНЕНИЯ АРГУМЕНТА С $(pN)\hbox{-М}$~КЛЮЧОМ, ПОВТОРЯЕТ ЭТУ ПРОЦЕДУРУ 
ДЛЯ МЕНЬШИХ БЛОКОВ. (дЛЯ БИНАРНОГО ПОИСКА $p=q=1/2$; ДЛЯ 
ФИБОНАЧЧИЕВА $p=1/\phi$, $q=1/\phi^2$.)

оБОЗНАЧИМ СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ, ТРЕБУЕМЫХ ДЛЯ ПОИСКА В 
ТАБЛИЦЕ РАЗМЕРА~$N$, ЧЕРЕЗ $C(N)$; ОНО ПРИБЛИЖЕННО УДОВЛЕТВОРЯЕТ СООТНОШЕНИЯМ
$$
C(1)=0, \quad C(N)=1+pC(pN)+qC(qN) \rem{ ДЛЯ $N>1$.}
$$
эТО ПРОИСХОДИТ ПОТОМУ, ЧТО ПОСЛЕ ПЕРВОГО СРАВНЕНИЯ ПОИСК ПРИМЕРНО С 
ВЕРОЯТНОСТЬЮ~$p$ СВОДИТСЯ К ПОИСКУ СРЕДИ $pN$~ЭЛЕМЕНТОВ И С 
ВЕРОЯТНОСТЬЮ $q$---К ПОИСКУ СРЕДИ $qN$~ЭЛЕМЕНТОВ. пРИ БОЛЬШИХ~$N$ МОЖНО 
ПРЕНЕБРЕЧЬ ЭФФЕКТОМ НИЗШЕГО ПОРЯДКА, СВЯЗАННЫМ С ТЕМ, ЧТО ЧИСЛА~$pN$ 
И~$qN$ НЕ ЦЕЛЫЕ.
\medskip
\item{a)} пОКАЖИТЕ, ЧТО $C(N)=\log_b N$ ТОЧНО УДОВЛЕТВОРЯЕТ УКАЗАННЫМ 
СООТНОШЕНИЯМ ПРИ НЕКОТОРОМ~$b$. дЛЯ БИНАРНОГО И ФИБОНАЧЧИЕВА ПОИСКОВ 
ВЕЛИЧИНА~$b$ ПОЛУЧАЕТСЯ ИЗ ВЫВЕДЕННЫХ РАНЕЕ ФОРМУЛ.

\item{b)} нЕКТО РАССУЖДАЛ ТАК: "с ВЕРОЯТНОСТЬЮ~$p$ ДЛИНА РАССМАТРИВАЕМОГО  
ИНТЕРВАЛА ДЕЛИТСЯ НА~$1/p$, С ВЕРОЯТНОСТЬЮ~$q$---НА~$1/q$. 
сЛЕДОВАТЕЛЬНО ИНТЕРВАЛ ДЕЛИТСЯ В СРЕДНЕМ НА~$p(1/p)+q (1/q)=2$, ТАК ЧТО 
АЛГОРИТМ В ТОЧНОСТИ ТАК ЖЕ ХОРОШ, КАК И БИНАРНЫЙ ПОИСК, НЕЗАВИСИМО ОТ~$p$ 
И~$q$". еСТЬ ЛИ ОШИБКА В ЭТИХ РАССУЖДЕНИЯХ?
\medskip

\ex[20] нАРИСУЙТЕ БИНАРНОЕ ДЕРЕВО, СООТВЕТСТВУЮЩЕЕ ИНТЕРПОЛЯЦИОННОМУ 
ПОИСКУ ПРИ~$N=10$.

\ex[м43] (э.~к.~яО И~ф.~ф.~яО.) пОКАЖИТЕ,, ЧТО ДОЛЖНЫМ ОБРАЗОМ ОФОРМЛЕННЫЙ 
ИНТЕРПОЛЯЦИОННЫЙ ПОИСК В СРЕДНЕМ ТРЕБУЕТ (АСИМПТОТИЧЕСКИ) $\log_2\log_2 
N$~СРАВНЕНИЙ, ЕСЛИ $N$~ОТСОРТИРОВАННЫХ КЛЮЧЕЙ ИМЕЮТ 
НЕЗАВИСИМЫЕ РАВНОМЕРНЫЕ РАСПРЕДЕЛЕНИЯ. бОЛЕЕ ТОГО, ВСЕ АЛГОРИТМЫ ПОИСКА ПО ТАКИМ
ТАБЛИЦАМ ДОЛЖНЫ СОВЕРШАТЬ В СРЕДНЕМ $\log_2 \log_2  N$~СРАВНЕНИЙ (ОЦЕНКА АСИМПТОТИЧЕСКАЯ).

\rex[25] аЛГОРИТМ БИНАРНОГО ПОИСКА г.~бОТТЕНБРУКА, УПОМЯНУТЫЙ В 
КОНЦЕ ПУНКТА, "ОТКЛАДЫВАЕТ" ПРОВЕРКИ НА РАВЕНСТВО ДО САМОГО КОНЦА ПОИСКА. (вО
%%502
ВРЕМЯ РАБОТЫ АЛГОРИТМА МЫ ЗНАЕМ, ЧТО $K_l\le K<K_{u+1}$, ПРОВЕРКА НА 
РАВЕНСТВО ПРОВОДИТСЯ ЛИШЬ ПРИ~$l=u$.) тАКОЙ ТРЮК СДЕЛАЛ БЫ ПРОГРАММУ~B 
ЧУТЬ БЫСТРЕЕ ПРИ БОЛЬШИХ~$N$, ТАК КАК МЫ ИЗБАВИЛИСЬ БЫ ОТ КОМАНДЫ "|JF|," 
ВО ВНУТРЕННЕМ ЦИКЛЕ. (оДНАКО ЭТА ИДЕЯ ПРАКТИЧЕСКИ НЕРЕАЛЬНА, ТАК КАК 
$\log_2  N$ ОБЫЧНО МАЛ;
ЛИШЬ ПРИ~$N>2^{36}$ КОМПЕНСИРУЕТСЯ НЕОБХОДИМОСТЬ ДОПОЛНИТЕЛЬНОЙ ИТЕРАЦИИ!)

пОКАЖИТЕ, ЧТО \emph{ЛЮБОЙ} АЛГОРИТМ ПОИСКА, СООТВЕТСТВУЮЩИЙ БИНАРНОМУ 
ДЕРЕВУ И РАЗВЕТВЛЯЮЩИЙСЯ ПО ТРЕМ НАПРАВЛЕНИЯМ ($<$, $=$, ИЛИ~$>$), МОЖНО 
ПЕРЕДЕЛАТЬ В АЛГОРИТМ, РАЗВЕТВЛЯЮЩИЙСЯ ВО ВНУТРЕННИХ УЗЛАХ ЛИШЬ ПО ДВУМ 
НАПРАВЛЕНИЯМ ($<$ ИЛИ~$\ge$). в ЧАСТНОСТИ, МОДИФИЦИРУЙТЕ ТАКИМ СПОСОБОМ АЛГОРИТМ~C. 

\rex[23] пОЛНОЕ БИНАРНОЕ ДЕРЕВО ЯВЛЯЕТСЯ УДОБНЫМ СПОСОБОМ ПРЕДСТАВЛЕНИЯ 
В ПОСЛЕДОВАТЕЛЬНЫХ ЯЧЕЙКАХ ДЕРЕВА С МИНИМАЛЬНОЙ ДЛИНОЙ ПУТИ. (сР. С 
П.~2.3.4.5.) пРИДУМАЙТЕ ЭФФЕКТИВНЫЙ МЕТОД ПОИСКА, ОСНОВАННЫЙ НА 
ТАКОМ ПРЕДСТАВЛЕНИИ. [\emph{уКАЗАНИЕ:} МОЖНО ЛИ В БИНАРНОМ ПОИСКЕ 
ИСПОЛЬЗОВАТЬ УМНОЖЕНИЕ НА~$2$ ВМЕСТО ДЕЛЕНИЯ НА~$2$?]

\rex[м25] пРЕДПОЛОЖИМ, ЧТО У БИНАРНОГО ДЕРЕВА ИМЕЕТСЯ $a_k$~ВНУТРЕННИХ И 
$b_k$~ВНЕШНИХ УЗЛОВ НА УРОВНЕ~$k$, $k=0$, $1$,~\dots. (кОРЕНЬ НАХОДИТСЯ НА 
НУЛЕВОМ УРОВНЕ.) тАК, ДЛЯ РИС.~8 ИМЕЕМ $(a_0, a_1,~\ldots, a_6)=(1, 2, 4, 4,
 1, 0)$ И $(b_0, b_1,~\ldots, b_6)=(0, 0, 0, 4, 7, 2)$. (a)~пОКАЖИТЕ, ЧТО 
СУЩЕСТВУЕТ ПРОСТОЕ АЛГЕБРАИЧЕСКОЕ СООТНОШЕНИЕ, СВЯЗЫВАЮЩЕЕ ПРОИЗВОДЯЩИЕ 
ФУНКЦИИ $A(z)=\sum_{k}a_kz^k$ И~$B(z)=\sum_k b_kz^k$. (b)~рАСПРЕДЕЛЕНИЕ 
ВЕРОЯТНОСТЕЙ ПРИ УДАЧНОМ ПОИСКЕ ПО БИНАРНОМУ ДЕРЕВУ ИМЕЕТ ПРОИЗВОДЯЩУЮ 
ФУНКЦИЮ $g(z)=zA(z)/N$, А ПРИ НЕУДАЧНОМ ПОИСКЕ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ ЕСТЬ 
$h(z)=B(z)/(N+1)$. (в ОБОЗНАЧЕНИЯХ П.~6.2.1 $C_N=\mean(g)$, 
$C'_N=\mean(h)$, А СООТНОШЕНИЕ~(2) СВЯЗЫВАЕТ ЭТИ ВЕЛИЧИНЫ.) нАЙДИТЕ 
ЗАВИСИМОСТЬ МЕЖДУ $\var(g)$ И~$\var(h)$.

\ex[22] пОКАЖИТЕ, ЧТО ДЕРЕВО фИБОНАЧЧИ СВЯЗАНО С СОРТИРОВКОЙ МНОГОФАЗНЫМ 
СЛИЯНИЕМ НА ТРЕХ ЛЕНТАХ.

\ex[M30] (X.~с.~сТОУН И дЖ.~лИНИ.) рАССМОТРИМ ПРОЦЕСС ПОИСКА, ОСНОВАННЫЙ 
ТОЛЬКО НА СРАВНЕНИЯХ КЛЮЧЕЙ И ИСПОЛЬЗУЮЩИЙ ОДНОВРЕМЕННО $k$~ПРОЦЕССОРОВ. 
пРИ КАЖДОМ ШАГЕ ПОИСКА ОПРЕДЕЛЯЮТСЯ $k$~ИНДЕКСОВ $i_1$, $i_2$,~\dots, 
$i_k$  И МЫ СОВЕРШАЕМ $k$~ОДНОВРЕМЕННЫХ СРАВНЕНИЙ: ЕСЛИ~$K=K_j$ ДЛЯ 
НЕКОТОРОГО~$j$, ПОИСК КОНЧАЕТСЯ УДАЧНО, В ПРОТИВНОМ СЛУЧАЕ ПЕРЕХОДИМ К 
СЛЕДУЮЩЕМУ ШАГУ ПОИСКА, ОСНОВЫВАЯСЬ НА $2^k$~ВОЗМОЖНЫХ ИСХОДАХ~$K<K_{i_j}$ 
ИЛИ~$K>K_{i_j}$, $1\le j\le k$.

пОКАЖИТЕ, ЧТО ТАКОЙ ПРОЦЕСС ПРИ~$N\to\infty$ ДОЛЖЕН СОВЕРШАТЬ В СРЕДНЕМ 
ПО КРАЙНЕЙ МЕРЕ $\log_{k+1}N$~ШАГОВ. (пРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ КЛЮЧИ В 
ТАБЛИЦЕ, ТАКЖЕ КАК И АРГУМЕНТ ПОИСКА, РАВНОВЕРОЯТНЫ.) (зНАЧИТ, ПО 
СРАВНЕНИЮ С ОДНОПРОЦЕССОРНЫМ БИНАРНЫМ ПОИСКОМ МЫ ВЫИГРЫВАЕМ В СКОРОСТИ 
НЕ В $k$~РАЗ, КАК МОЖНО БЫЛО БЫ ОЖИДАТЬ, А ЛИШЬ В $\log_2(k+1)$~РАЗ. в 
ЭТОМ СМЫСЛЕ ВЫГОДНЕЕ КАЖДЫЙ ПРОЦЕССОР ИСПОЛЬЗОВАТЬ ДЛЯ ОТДЕЛЬНОГО ПОИСКА, 
А НЕ ОБоЕДИНЯТЬ ИХ.)

\subsubchap{пОИСК ПО БИНАРНОМУ ДЕРЕВУ} %% 6.2.2

в ПРЕДЫДУЩЕМ ПУНКТЕ МЫ ВИДЕЛИ, ЧТО ИСПОЛЬЗОВАНИЕ НЕЯВНОЙ  СТРУКТУРЫ 
БИНАРНОГО ДЕРЕВА ОБЛЕГЧАЕТ ПОНИМАНИЕ БИНАРНОГО И ФИБОНАЧЧИЕВА ПОИСКОВ. 
рАССМОТРЕНИЕ СООТВЕТСТВУЮЩИХ ДЕРЕВЬЕВ ПОЗВОЛИЛО ЗАКЛЮЧИТЬ, ЧТО ПРИ 
ДАННОМ~$N$ СРЕДИ ВСЕХ МЕТОДОВ ПОИСКА ПУТЕМ СРАВНЕНИЯ КЛЮЧЕЙ БИНАРНЫЙ ПОИСК 
СОВЕРШАЕТ МИНИМАЛЬНОЕ ЧИСЛО СРАВНЕНИЙ. нО МЕТОДЫ ПРЕДЫДУЩЕГО 
ПУНКТА ПРЕДНАЗНАЧЕНЫ ГЛАВНЫМ ОБРАЗОМ ДЛЯ ТАБЛИЦ ФИКСИРОВАННОГО РАЗМЕРА, 
ТАК КАК ПОСЛЕДОВАТЕЛЬНОЕ РАСПОЛОЖЕНИЕ ЗАПИСЕЙ ДЕЛАЕТ ВСТАВКИ И УДАЛЕНИЯ 
ДОВОЛЬНО ТРУДОЕМКИМИ. еСЛИ ТАБЛИЦА
%%503
ДИНАМИЧЕСКИ ИЗМЕНЯЕТСЯ, ТО ЭКОНОМИЯ ОТ ИСПОЛЬЗОВАНИЯ БИНАРНОГО ПОИСКА НЕ 
ПОКРОЕТ ЗАТРАТ НА ПОДДЕРЖАНИЕ УПОРЯДОЧЕННОГО РАСПОЛОЖЕНИЯ КЛЮЧЕЙ.

\emph{яВНОЕ} ИСПОЛЬЗОВАНИЕ СТРУКТУРЫ БИНАРНОГО ДЕРЕВА ПОЗВОЛЯЕТ БЫСТРО 
ВСТАВЛЯТЬ И УДАЛЯТЬ ЗАПИСИ И ПРОИЗВОДИТЬ ЭФФЕКТИВНЫЙ ПОИСК ПО ТАБЛИЦЕ. в 
РЕЗУЛЬТАТЕ МЫ ПОЛУЧАЕМ МЕТОД, ПОЛЕЗНЫЙ КАК ДЛЯ ПОИСКА, ТАК И ДЛЯ 
СОРТИРОВКИ. тАКАЯ ГИБКОСТЬ ДОСТИГАЕТСЯ
\picture{рИС. 10.  бИНАРНОЕ ДЕРЕВО ПОИСКА.}
ПУТЕМ ДОБАВЛЕНИЯ В КАЖДУЮ ЗАПИСЬ ДВУХ ПОЛЕЙ ДЛЯ ХРАНЕНИЯ ССЫЛОК.

мЕТОДЫ ПОИСКА ПО РАСТУЩИМ ТАБЛИЦАМ, ЧАСТО НАЗЫВАЮТ \emph{АЛГОРИТМАМИ 
ТАБЛИЦ СИМВОЛОВ}, ТАК КАК АССЕМБЛЕРЫ, КОМПИЛЯТОРЫ И ДРУГИЕ СИСТЕМНЫЕ 
ПРОГРАММЫ ОБЫЧНО ИСПОЛЬЗУЮТ ИХ ДЛЯ ХРАНЕНИЯ ОПРЕДЕЛЯЕМЫХ ПОЛЬЗОВАТЕЛЕМ 
СИМВОЛОВ. нАПРИМЕР, КЛЮЧОМ ЗАПИСИ В КОМПИЛЯТОРЕ МОЖЕТ СЛУЖИТЬ 
СИМВОЛИЧЕСКИЙ ИДЕНТИФИКАТОР, ОБОЗНАЧАЮЩИЙ ПЕРЕМЕННУЮ В НЕКОТОРОЙ ПРОГРАММЕ 
НА фОРТРАНЕ ИЛИ аЛГОЛЕ, А ОСТАЛЬНЫЕ ПОЛЯ ЗАПИСИ МОГУТ СОДЕРЖАТЬ 
ИНФОРМАЦИЮ О ТИПЕ ПЕРЕМЕННОЙ И ЕЕ РАСПОЛОЖЕНИИ В ПАМЯТИ. иЛИ ЖЕ КЛЮЧОМ 
МОЖЕТ БЫТЬ СИМВОЛ ПРОГРАММЫ ДЛЯ \MIX, А ОСТАВШАЯСЯ ЧАСТЬ ЗАПИСИ МОЖЕТ 
СОДЕРЖАТЬ ЭКВИВАЛЕНТ ЭТОГО СИМВОЛА. пРОГРАММЫ ПОИСКА С ВСТАВКОЙ ПО ДЕРЕВУ, 
КОТОРЫЕ БУДУТ ОПИСАНЫ В ЭТОМ ПУНКТЕ, ОТЛИЧНО ПОДХОДЯТ ДЛЯ ИСПОЛЬЗОВАНИЯ В 
КАЧЕСТВЕ АЛГОРИТМОВ ТАБЛИЦ СИМВОЛОВ, ОСОБЕННО ЕСЛИ ЖЕЛАТЕЛЬНО 
РАСПЕЧАТЫВАТЬ СИМВОЛЫ В АЛФАВИТНОМ ПОРЯДКЕ. дРУГИЕ АЛГОРИТМЫ, 
ТАБЛИЦ СИМВОЛОВ ОПИСАНЫ В \S~6.3 И~6.4.

%%504

нА РИС.~10 ИЗОБРАЖЕНО БИНАРНОЕ ДЕРЕВО ПОИСКА, СОДЕРЖАЩЕЕ НАЗВАНИЯ 
ОДИННАДЦАТИ ЗНАКОВ ЗОДИАКА%
\note{1}{зНАКИ ЗОДИАКА, УПОРЯДОЧЕННЫЕ ПО МЕСЯЦАМ: кОЗЕРОГ, вОДОЛЕЙ, рЫБЫ,
 оВЕН, тЕЛЕЦ, бЛИЗНЕЦЫ, рАК, лЕВ, дЕВА, вЕСЫ, сКОРПИОН, сТРЕЛЕЦ,---{\sl пРИМ. ПЕРЕВ.\/}}.
 еСЛИ ТЕПЕРЬ, ОТПРАВЛЯЯСЬ ОТ КОРНЯ ДЕРЕВА, МЫ БУДЕМ ИСКАТЬ ДВЕНАДЦАТОЕ 
НАЗВАНИЕ, |SAGITTARIUS|, ТО УВИДИМ, ЧТО ОНО БОЛЬШЕ, ЧЕМ |CAPRICORN|, 
ПОЭТОМУ НУЖНО ИДТИ ВПРАВО; ОНО БОЛЬШЕ, ЧЕМ |PISCES|,---СНОВА ИДЕМ ВПРАВО; 
ОНО МЕНЬШЕ, ЧЕМ |TAURUS|,---ИДЕМ ВЛЕВО; ОНО МЕНЬШЕ, ЧЕМ |SCORPIO|,--- И МЫ 
ПОПАДАЕМ ВО ВНЕШНИЙ УЗЕЛ~\leaf{8}. пОИСК БЫЛ НЕУДАЧНЫМ; ТЕПЕРЬ ПО 
ОКОНЧАНИИ ПОИСКА МЫ МОЖЕМ \emph{ВСТАВИТЬ} |SAGITTARIUS|, "ПОДВЯЗЫВАЯ" ЕГО 
К ДЕРЕВУ ВМЕСТО ВНЕШНЕГО УЗЛА~\leaf{8}. тАКИМ ОБРАЗОМ, ТАБЛИЦА МОЖЕТ РАСТИ 
БЕЗ ПЕРЕМЕЩЕНИЯ СУЩЕСТВУЮЩИХ ЗАПИСЕЙ. рИСУНОК~10 ПОЛУЧЕН ПОСЛЕДОВАТЕЛЬНОЙ 
ВСТАВКОЙ, НАЧИНАЯ С ПУСТОГО ДЕРЕВА, КЛЮЧЕЙ |CAPRICORN|, |AQUARIUS|, 
|PISCES|, |ARIES|, |TAURUS|, |GEMINI|, |CANCER|, |LEO|, |VIRGO|, |LIBRA|,
 |SCORPIO| В УКАЗАННОМ ПОРЯДКЕ.

нА РИС.~10 ВСЕ КЛЮЧИ ЛЕВОГО ПОДДЕРЕВА КОРНЯ ПРЕДШЕСТВУЮТ ПО АЛФАВИТУ 
СЛОВУ |CAPRICORN|, А В ПРАВОМ ПОДДЕРЕВЕ СТОЯТ ПОСЛЕ НЕГО. аНАЛОГИЧНОЕ 
УТВЕРЖДЕНИЕ СПРАВЕДЛИВО ДЛЯ ЛЕВОГО И ПРАВОГО ПОДДЕРЕВЬЕВ ЛЮБОГО УЗЛА. 
оТСЮДА СЛЕДУЕТ, ЧТО ПРИ ОБХОДЕ ДЕРЕВА В \emph{СИММЕТРИЧНОМ ПОРЯДКЕ} КЛЮЧИ 
РАСПОЛАГАЮТСЯ СТРОГО В АЛФАВИТНОМ ПОРЯДКЕ:
$$
\displaylines{
|AQUARIUS|, |ARIES|, |CANCER|, |CAPRICORN|, |GEMINI|, \cr
|LEO|, \ldots, |VIRGO|,\cr
}
$$
ТАК КАК СИММЕТРИЧНЫЙ ПОРЯДОК ОСНОВАН НА ПРОХОЖДЕНИИ СНАЧАЛА ЛЕВОГО 
ПОДДЕРЕВА КАЖДОГО УЗЛА, ЗАТЕМ САМОГО УЗЛА, А ЗАТЕМ ЕГО ПРАВОГО ПОДДЕРЕВА 
(СР. С П.~2.3.1).

нИЖЕ ДАЕТСЯ ПОДРОБНОЕ ОПИСАНИЕ ПРОЦЕССА ПОИСКА С ВСТАВКОЙ.

\alg т.(пОИСК С ВСТАВКОЙ ПО ДЕРЕВУ.) дАНА ТАБЛИЦА ЗАПИСЕЙ, ОБРАЗУЮЩИХ 
БИНАРНОЕ ДЕРЕВО. пРОИЗВОДИТСЯ ПОИСК ЗАДАННОГО АРГУМЕНТА~$K$. еСЛИ ЕГО 
НЕТ В ТАБЛИЦЕ, ТО В ПОДХОДЯЩЕМ МЕСТЕ В ДЕРЕВО ВСТАВЛЯЕТСЯ НОВЫЙ УЗЕЛ, 
СОДЕРЖАЩИЙ~$K$.

пРЕДПОЛАГАЕТСЯ, ЧТО УЗЛЫ ДЕРЕВА СОДЕРЖАТ ПО КРАЙНЕЙ МЕРЕ СЛЕДУЮЩИЕ ПОЛЯ:
$$
\eqalign{
|KEY|(|P|)&=\hbox{КЛЮЧ, ХРАНЯЩИЙСЯ В УЗЛЕ $|NODE|(|P|)$};\cr
|LLINK|(|P|)&=\hbox{УКАЗАТЕЛЬ НА ЛЕВОЕ ПОДДЕРЕВО УЗЛА~$|NODE|(|P|)$};\cr
|RLINK|(|P|)&=\hbox{УКАЗАТЕЛЬ НА ПРАВОЕ ПОДДЕРЕВО УЗЛА~$|NODE|(|P|)$}.\cr
}
$$
пУСТЫЕ ПОДДЕРЕВЬЯ (ВНЕШНИЕ УЗЛЫ НА РИС.~10) ПРЕДСТАВЛЯЮТСЯ ПУСТЫМИ 
УКАЗАТЕЛЯМИ~$\NULL$. пЕРЕМЕННАЯ~|ROOT| УКАЗЫВАЕТ НА КОРЕНЬ ДЕРЕВА. дЛЯ 
УДОБСТВА ПРЕДПОЛАГАЕТСЯ, ЧТО ДЕРЕВО НЕ ПУСТО
%%505
($|ROOT|\ne\NULL$), ТАК КАК ПРИ~$|ROOT|=\NULL$ ОПЕРАЦИИ СТАНОВЯТСЯ 
ТРИВИАЛЬНЫМИ.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $|P|\asg |ROOT|$. (уКАЗАТЕЛЬ~|P| БУДЕТ 
ПРОДВИГАТЬСЯ ВНИЗ ПО ДЕРЕВУ.)

\st[сРАВНЕНИЕ.] еСЛИ~$K<|KEY|(|P|)$, ТО ПЕРЕЙТИ НА~\stp{3}; 
ЕСЛИ $K>|KEY|(|P|)$, ТО ПЕРЕЙТИ НА~\stp{4}; ЕСЛИ $K=|KEY|(|P|)$, 
ПОИСК ЗАВЕРШЕН УДАЧНО.

\st[шАГ ВЛЕВО.] еСЛИ~$|LLINK|(|P|)\ne\NULL$, УСТАНОВИТЬ 
$|P|\asg|LLINK|(|P|)$ И ВЕРНУТЬСЯ НА~\stp{2}. в ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ НА~\stp{5}.

\st[шАГ ВПРАВО.] еСЛИ~$|RLINK|(|P|)\ne\NULL$, УСТАНОВИТЬ 
$|P|\asg|RLINK|(|P|)$ И ВЕРНУТЬСЯ НА~\stp{2}.

\st[вСТАВКА В ДЕРЕВО.] (пОИСК НЕУДАЧЕН; ТЕПЕРЬ МЫ ПОМЕСТИМ $K$ В ДЕРЕВО.) 
вЫПОЛНИТЬ $|Q|\Asg|AVAIL|$; |Q| ТЕПЕРЬ УКАЗЫВАЕТ НА НОВЫЙ УЗЕЛ. уСТАНОВИТЬ 
$|KEY|(|Q|)\asg K$, $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. (нА САМОМ 
ДЕЛЕ НУЖНО ПРОИЗВЕСТИ НАЧАЛЬНУЮ УСТАНОВКУ И ДРУГИХ ПОЛЕЙ НОВОГО УЗЛА.) 
еСЛИ $K$ БЫЛО МЕНЬШЕ $|KEY|(|P|)$, УСТАНОВИТЬ $|LLINK|(|P|)\asg|Q|$; В 
ПРОТИВНОМ  СЛУЧАЕ УСТАНОВИТЬ $|RLINK|(|P|)\asg|Q|$. (в ЭТОТ МОМЕНТ МЫ 
МОГЛИ БЫ ПРИСВОИТЬ $|P|\asg|Q|$ И УДАЧНО ЗАВЕРШИТЬ РАБОТУ АЛГОРИТМА.)
\algend

аЛГОРИТМ САМ ПОДСКАЗЫВАЕТ РЕАЛИЗАЦИЮ НА ЯЗЫКЕ~\MIXAL. пРЕДПОЛОЖИМ, 
НАПРИМЕР, ЧТО УЗЛЫ ДЕРЕВА ИМЕЮТ СЛЕДУЮЩУЮ СТРУКТУРУ:
\picture{рИС. СТР. 505}
вОЗМОЖНО, ДАЛЕЕ РАСПОЛОЖЕНЫ ДОПОЛНИТЕЛЬНЫЕ СЛОВА |INFO|. кАК И В ГЛ.~2, 
|AVAIL| ЕСТЬ СПИСОК СВОБОДНОЙ ПАМЯТИ. иТАК, ПОЛУЧАЕТСЯ СЛЕДУЮЩАЯ ПРОГРАММА 
ДЛЯ \MIX.

\prog т.(пОИСК С ВСТАВКОЙ ПО ДЕРЕВУ.) $|rA|\equiv K$, $|rI1|\equiv|P|$,
 $|rI2|\equiv Q$.
\code
LLINK & EQU  &2:3
RLINK & EQU  &4:5
START & LDA  &к           & 1    & т1. нАЧАЛЬНАЯ УСТАНОВКА.
      & LD1  &ROOT        & 1    & $|P|\asg|ROOT|$.
      & JMP  &2F          & 1
4H    & LD2  &0,1(RLINK)  & C2   & T4. шАГ ВПРАВО. $|Q|\asg|RLlNK|(|P|)$.
      & J2Z  &5F          & C2   & нА T5, ЕСЛИ $|Q|=\NULL$.
1H    & ENT1 &0,2         & C-l  & $|P|\asg|Q|$.
2H    & CMPA &1,1         & C    & T2. сРАВНЕНИЕ.
      & JG   & 4в         & C    & нА T4, ЕСЛИ $K>|KEY|(|P|)$.
      & JE   &SUCCESS     & C1   & вЫХОД, ЕСЛИ $K=|KEY|(|P|)$.
      & LD2  &0,1 (LLINK) & C1-S & Tз. шАГ ВЛЕВО. $|Q|\asg|LLINK|(|P|)$.
%%506
     & J2NZ & 1B         & C1-S  & нА T2, ЕСЛИ $|Q|\ne\NULL$.
5н   & LD2  & AVAIL      & 1-S   & T5 вСТАВКИ В ДЕРЕВО.
     & J2Z  & OVERFLOW   & 1-S
     & LDX  & 0,2(RLINK) & 1-S
     & STX  & AVAIL      & 1-S   & $|Q|\Asg|AVAIL|$.
     & STA  & 1,2        & 1-S   & $|KEY|(|Q|)\asg|K|$.
     & STZ  & 0,2        & 1-S   & $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$.
     & JL   & 1F         & 1-S   & $K$ БЫЛ МЕНЬШЕ $|KEY|(|P|)$?
     & ST2  & 0,1(RLINK) & A     & $|RLINK|(|P|)\asg|Q|$.
     & JMP  & *+2        & A
1H   & ST2  & 0,1(LLINK) & 1-S-A & $|LLINK|(|P|)\asg|Q|$.
DONE & EQU  & *          & 1-S   & вЫХОД ПОСЛЕ ВСТАВКИ. 
\endcode
\progend
пЕРВЫЕ 13~СТРОК ПРОГРАММЫ ОСУЩЕСТВЛЯЮТ ПОИСК, ПОСЛЕДНИЕ 11~СТРОК---ВСТАВКУ. 
вРЕМЯ РАБОТЫ ПОИСКОВОЙ ФАЗЫ РАВНО $(7C+C1-3S+4)u$, ГДЕ
$$
\eqalign{
C &=\hbox{ЧИСЛО ПРОИЗВЕДЕННЫХ СРАВНЕНИЙ};\cr
Cl& =\hbox{ЧИСЛО СЛУЧАЕВ, КОГДА $K\le|KEY|(|P|)$};\cr
S& =\hbox{ 1 ПРИ УДАЧНОМ ПОИСКЕ И 0 В ПРОТИВНОМ СЛУЧАЕ}.\cr
}
$$
в СРЕДНЕМ ИМЕЕМ $C1={1\over2}(C+S)$; ДЕЙСТВИТЕЛЬНО, $C1+C2=C$ 
И $C1-S\approx C2$. пОЭТОМУ ВРЕМЯ ПОИСКА ПРИМЕРНО РАВНО $(7.5C-2.5S+4)u$.
\picture{рИС 11. пОИСК С ВСТАВКОЙ ПО ДЕРЕВУ.}
пРОГРАММЫ БИНАРНОГО ПОИСКА, ИСПОЛЬЗУЮЩИЕ НЕЯВНЫЕ ДЕРЕВЬЯ, РАБОТАЮТ ДОЛЬШЕ! 
(сР. С ПРОГРАММОЙ~6.2.1с.) пРОДУБЛИРОВАВ КОМАНДЫ, КАК. И В 
ПРОГРАММЕ~6.2.1F, МОЖНО ИЗБАВИТЬСЯ ОТ СТРОКИ~08 В ПРОГРАММЕ~т, УМЕНЬШИВ 
ТЕМ САМЫМ ВРЕМЯ ПОИСКА ДО~$(6.5C-2.5S+5)u$. еСЛИ ПОИСК НЕУДАЧЕН, 
ФАЗА ВСТАВКИ ЗАЙМЕТ ЕЩЕ ВРЕМЯ $14u$ ИЛИ~$15u$.

аЛГОРИТМ~т ЛЕГКО ПРИСПОСОБИТЬ К РАБОТЕ С КЛЮЧАМИ И ЗАПИСЯМИ 
\emph{ПЕРЕМЕННОЙ ДЛИНЫ}. нАПРИМЕР, ЕСЛИ МЫ РАСПРЕДЕЛЯЕМ
%%507
ИМЕЮЩЕЕСЯ В НАЛИЧИИ ПРОСТРАНСТВО ПОСЛЕДОВАТЕЛЬНО, СПОСОБОМ "ПОСЛЕДНИМ 
ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ" (LIFO), ТО ЛЕГКО СМОЖЕМ СОЗДАВАТЬ УЗЛЫ 
РАЗЛИЧНОГО РАЗМЕРА; ПЕРВОЕ СЛОВО ДЕРЕВА~(1) МОЖЕТ УКАЗЫВАТЬ ДЛИНУ. тАКОЕ 
ЭФФЕКТИВНОЕ ИСПОЛЬЗОВАНИЕ ПАМЯТИ ДЕЛАЕТ АЛГОРИТМЫ ТАБЛИЦ СИМВОЛОВ, 
ОСНОВАННЫЕ НА ДРЕВОВИДНОЙ СТРУКТУРЕ, ОСОБЕННО ПРИВЛЕКАТЕЛЬНЫМИ ДЛЯ 
РАЗРАБОТЧИКОВ КОМПИЛЯТОРОВ, АССЕМБЛЕРОВ И ЗАГРУЗЧИКОВ.

\qsection а КАК НАСЧЕТ НАИХУДШЕГО СЛУЧАЯ? мНОГИЕ ПРОГРАММИСТЫ СНАЧАЛА 
СКЕПТИЧЕСКИ ВОСПРИНИМАЮТ АЛГОРИТМ~T. еСЛИ БЫ КЛЮЧИ РИС.~10 ПОСТУПАЛИ В 
АЛФАВИТНОМ ПОРЯДКЕ |AQUARIUS|,~\dots, |VIRGO|, a НЕ В КАЛЕНДАРНОМ 
|CAPRICORN|,~\dots, |SCORPIO|, ТО АЛГОРИТМ ВЫСТРОИЛ БЫ ВЫРОЖДЕННОЕ ДЕРЕВО, 
КОТОРОЕ, В СУЩНОСТИ, ОПРЕДЕЛЯЕТ \emph{ПОСЛЕДОВАТЕЛЬНЫЙ} ПОИСК. (вСЕ ПОЛЯ 
|LLINK| РАВНЯЛИСЬ БЫ ~$\NULL$.) аНАЛОГИЧНО, ЕСЛИ КЛЮЧИ ПОСТУПАЮТ В 
НЕОБЫЧНОМ ПОРЯДКЕ:
$$
\displaylines{
|AQUARIUS|, |VIRGO|, |ARIES|, |TAURUS|, |CANCER|, |SCORPIO|,\cr
|CAPRICORN|, |PISCES|, |GEMINI|, |LIBRA|, |LEO|,\cr
}
$$
МЫ ПОЛУЧИМ ЗИГЗАГООБРАЗНОЕ ДЕРЕВО, ЧТО НИЧУТЬ НЕ ЛУЧШЕ. (пОСТРОЙТЕ ЭТО ДЕРЕВО!)

с ДРУГОЙ СТОРОНЫ, ДЛЯ УДАЧНОГО ПОИСКА ПО ДЕРЕВУ РИС.~10
ТРЕБУЕТСЯ В СРЕДНЕМ ВСЕГО ЛИШЬ $3{2\over11}$~СРАВНЕНИЙ, ЧТО НЕМНОГИМ
БОЛЬШЕ ОПТИМАЛЬНОГО СРЕДНЕГО ЧИСЛА СРАВНЕНИЙ~3, КОТОРОЕ ДОСТИГАЕТСЯ ПРИ 
ПОИСКЕ ПО НАИЛУЧШЕМУ ИЗ ВОЗМОЖНЫХ БИНАРНЫХ ДЕРЕВЬЕВ.

дЛЯ ДОСТАТОЧНО ХОРОШО СБАЛАНСИРОВАННОГО ДЕРЕВА ВРЕМЯ ПОИСКА ПРИМЕРНО, 
ПРОПОРЦИОНАЛЬНО~$\log_2N$, А ДЛЯ ВЫРОЖДЕННОГО ДЕРЕВА---$N$. в УПР.~2.3.4.5-5 
ДОКАЗЫВАЕТСЯ, ЧТО, ЕСЛИ СЧИТАТЬ ВСЕ БИНАРНЫЕ ДЕРЕВЬЯ ИЗ $N$~УЗЛОВ 
РАВНОВЕРОЯТНЫМИ, СРЕДНЕЕ ВРЕМЯ ПОИСКА ПРИБЛИЗИТЕЛЬНО 
ПРОПОРЦИОНАЛЬНО~$\sqrt{N}$. чЕГО ЖЕ НАМ ОЖИДАТЬ ОТ АЛГОРИТМА~T?

к СЧАСТЬЮ, МОЖНО ДОКАЗАТЬ, ЧТО ПОИСК ПО ДЕРЕВУ ТРЕБУЕТ ЛИШЬ ОКОЛО $2\ln N 
\approx 1.386\log_2 N$ СРАВНЕНИЙ, ЕСЛИ КЛЮЧИ ДОБАВЛЯЮТСЯ К ДЕРЕВУ В 
СЛУЧАЙНОМ ПОРЯДКЕ; ХОРОШО СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ---ПРАВИЛО, А ВЫРОЖДЕННЫЕ---ИСКЛЮЧЕНИЕ.

дОКАЗАТЬ ЭТОТ ФАКТ УДИВИТЕЛЬНО ПРОСТО. пРЕДПОЛОЖИМ, ЧТО КАЖДАЯ ИЗ 
$N!$~ПЕРЕСТАНОВОК $N$~КЛЮЧЕЙ С РАВНОЙ ВЕРОЯТНОСТЬЮ ИСПОЛЬЗУЕТСЯ ДЛЯ 
ПОСТРОЕНИЯ ДЕРЕВА ПУТЕМ ВСТАВОК. чИСЛО СРАВНЕНИЙ, НУЖНЫХ ДЛЯ 
НАХОЖДЕНИЯ КЛЮЧА, РОВНО НА ЕДИНИЦУ БОЛЬШЕ ЧИСЛА СРАВНЕНИЙ, ПОТРЕБОВАВШИХСЯ 
ПРИ ВСТАВКЕ ЕГО В ДЕРЕВО. сЛЕДОВАТЕЛЬНО, ЕСЛИ ЧЕРЕЗ $C_N$ ОБОЗНАЧИТЬ 
СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ ПРИ УДАЧНОМ ПОИСКЕ, А ЧЕРЕЗ $C'_N$---ПРИ НЕУДАЧНОМ,
 МЫ ПОЛУЧИМ
$$
C_N=1+{C'_0+C'_1+\cdots+C'_{N-1}\over N}.
\eqno(2)
$$
%%508
нО СОГЛАСНО СООТНОШЕНИЮ МЕЖДУ ДЛИНАМИ ВНУТРЕННЕГО И ВНЕШНЕГО ПУТЕЙ (6.2.1-2)
$$
C_N=\left(1+{1\over N}\right)C'_N-1.
\eqno(3)
$$
пОДСТАВЛЯЯ $C_N$ ИЗ~(3) В~(2), ИМЕЕМ
$$
(N+1)C'_N=2N+C'_0+C'_1+\cdots+C'_{N-1}.
\eqno(4)
$$
иЗ ЭТОГО РЕКУРРЕНТНОГО СООТНОШЕНИЯ $C'_N$ НАХОДИТСЯ ЛЕГКО. вЫЧИТАНИЕ РАВЕНСТВА
$$
NC'_{N-1}=2(N-1)+C'_0+C'_1+\cdots+C'_{N-2}
$$
ДАЕТ
$$
\eqalign{
(N+1)C'_N-NC'_{N-1}&=2+C'_{N-1},\cr
C'_N&=C'_{N-1}+2/(N+1).\cr
}
$$
тАК КАК $C'_0=0$, ТО
$$
C'_N=2H_{N+1}-2.
\eqno(5)
$$
пРИМЕНИВ~(3), ПОСЛЕ УПРОЩЕНИЙ ПОЛУЧАЕМ
$$
C_N=2\left(1+{1\over N}\right) H_N-3.
\eqno(3)
$$
уПРАЖНЕНИЯ 6--8 ДАЮТ БОЛЕЕ ДЕТАЛЬНУЮ ИНФОРМАЦИЮ: МОЖНО НАЙТИ НЕ ТОЛЬКО 
СРЕДНИЕ ЗНАЧЕНИЯ~$C_N$ И~$C'_N$, НО И ИХ ВЕРОЯТНОСТНЫЕ РАСПРЕДЕЛЕНИЯ.

\section сОРТИРОВКА ВСТАВКОЙ В ДЕРЕВО. аЛГОРИТМ~T ПРЕДНАЗНАЧАЛСЯ 
ДЛЯ ПОИСКА, НО ЕГО МОЖНО ПРИНЯТЬ ЗА ОСНОВУ АЛГОРИТМА 
ВНУТРЕННЕЙ \emph{СОРТИРОВКИ}, ТАК КАК ОН ЯВЛЯЕТСЯ ЕСТЕСТВЕННЫМ ОБОБЩЕНИЕМ 
АЛГОРИТМА ВСТАВОК В СПИСОК~5.2.1L. уМЕЛО ЗАПРОГРАММИРОВАННЫЙ, ОН БУДЕТ 
РАБОТАТЬ ЛИШЬ НЕМНОГО МЕДЛЕННЕЕ ЛУЧШИХ АЛГОРИТМОВ, ОБСУЖДАВШИХСЯ В ГЛ.~5. 
кОГДА ПОСТРОЕНИЕ ДЕРЕВА ЗАВЕРШЕНО, ОСТАЕТСЯ СИММЕТРИЧНО ОБОЙТИ ЕГО 
(АЛГОРИТМ~2.3.1T)---МЫ "ПОСЕТИМ" ЗАПИСИ В ОТСОРТИРОВАННОМ ПОРЯДКЕ.

оДНАКО НЕОБХОДИМО БЫТЬ ОСТОРОЖНЫМ. яСНО, ЧТО В ШАГЕ~T2 ПРИ $K=|KEY|(|P|)$ 
НАДО ДЕЙСТВОВАТЬ ПО-ДРУГОМУ, ТАК КАК МЫ СОРТИРУЕМ, А НЕ ИЩЕМ. мОЖНО, 
НАПРИМЕР, РЕАГИРОВАТЬ НА $K=|KEY|(|P|)$ ТАК ЖЕ, КАК И НА $K>|KEY|(|P|)$; 
ЭТО ДАСТ ПРАВИЛЬНЫЙ МЕТОД СОРТИРОВКИ. (зАМЕТИМ, ВПРОЧЕМ, ЧТО РАВНЫЕ КЛЮЧИ 
НЕ ОБЯЗАТЕЛЬНО ДОЛЖНЫ НАХОДИТЬСЯ В СМЕЖНЫХ УЗЛАХ, ЛИШЬ БЫ ОНИ ПРОХОДИЛИСЬ 
ПОСЛЕДОВАТЕЛЬНО ПРИ СИММЕТРИЧНОМ ОБХОДЕ.) пРИ БОЛЬШОМ КОЛИЧЕСТВЕ 
ПОВТОРЯЮЩИХСЯ КЛЮЧЕЙ ЭТОТ МЕТОД ПРИВЕДЕТ К ВЕСЬМА НЕСБАЛАНСИРОВАННОМУ 
ДЕРЕВУ, И СОРТИРОВКА ЗАМЕДЛИТСЯ. дРУГИМ МЕТОДОМ ЯВЛЯЕТСЯ ХРАНЕНИЕ В КАЖДОМ 
УЗЛЕ СПИСКА ЗАПИСЕЙ С ОДНИМ И ТЕМ ЖЕ КЛЮЧОМ; ПОТРЕБУЕТСЯ 
ДОПОЛНИТЕЛЬНОЕ ПОЛЕ ДЛЯ ССЫЛКИ, НО ЭТО УСКОРИТ СОРТИРОВКУ В СЛУЧАЕ, 
КОГДА ВСТРЕЧАЕТСЯ МНОГО ОДИНАКОВЫХ КЛЮЧЕЙ.

%%509

тАКИМ ОБРАЗОМ, АЛГОРИТМ~T, ПРИМЕНЯЕМЫЙ ТОЛЬКО ДЛЯ СОРТИРОВКИ, НЕПЛОХ, НО 
ЕСТЬ И ЛУЧШИЕ. еСЛИ ЖЕ НУЖНО СОЧЕТАТЬ ПОИСК И СОРТИРОВКУ, ИСПОЛЬЗОВАНИЕ 
ДРЕВОВИДНОЙ СТРУКТУРЫ СЛЕДУЕТ НАСТОЯТЕЛЬНО РЕКОМЕНДОВАТЬ.

иНТЕРЕСНО ОТМЕТИТЬ ТЕСНУЮ СВЯЗЬ МЕЖДУ АНАЛИЗОМ СОРТИРОВКИ ВСТАВКОЙ В 
ДЕРЕВО И АНАЛИЗОМ ОБМЕННОЙ СОРТИРОВКИ С РАЗДЕЛЕНИЕМ ("БЫСТРОЙ 
СОРТИРОВКИ"), ХОТЯ НА ПЕРВЫЙ ВЗГЛЯД ЭТИ МЕТОДЫ СОВЕРШЕННО РАЗЛИЧНЫ. пРИ 
ВСТАВКЕ В ПЕРВОНАЧАЛЬНО ПУСТОЕ ДЕРЕВО $N$~КЛЮЧЕЙ В СРЕДНЕМ СОВЕРШАЕТСЯ 
ТО ЖЕ ЧИСЛО СРАВНЕНИЙ, ЧТО И В АЛГОРИТМЕ~5.2.2Q (ЗА НЕБОЛЬШИМИ 
ИСКЛЮЧЕНИЯМИ). нАПРИМЕР, ПРИ ВСТАВКЕ В ДЕРЕВО КАЖДЫЙ КЛЮЧ СРАВНИВАЕТСЯ С 
$K_1$, А КАЖДЫЙ КЛЮЧ, МЕНЬШИЙ $K_1$, СРАВНИВАЕТСЯ С ПЕРВЫМ КЛЮЧОМ, МЕНЬШИМ 
$K_1$, И Т. Д.; ПРИ БЫСТРОЙ СОРТИРОВКЕ КАЖДЫЙ КЛЮЧ СРАВНИВАЕТСЯ С ПЕРВЫМ 
РАЗДЕЛЯЮЩИМ ЭЛЕМЕНТОМ~$K$, А ЗАТЕМ КАЖДЫЙ КЛЮЧ, МЕНЬШИЙ $K$, 
СРАВНИВАЕТСЯ С ОПРЕДЕЛЕННЫМ, МЕНЬШИМ $K$ ЭЛЕМЕНТОМ И Т.~Д. сРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ В ОБОИХ СЛУЧАЯХ РАВНО $NC_N$. (пРАВДА, НА САМОМ ДЕЛЕ, ЧТОБЫ 
УСКОРИТЬ ВНУТРЕННИЙ ЦИКЛ, АЛГОРИТМ~5.2.2Q СОВЕРШАЕТ НЕСКОЛЬКО БОЛЬШЕ СРАВНЕНИЙ.)

\section уДАЛЕНИЯ. иНОГДА БЫВАЕТ НУЖНО ЗАСТАВИТЬ эвм ЗАБЫТЬ ОДИН 
ИЗ ЭЛЕМЕНТОВ ТАБЛИЦЫ. лЕГКО УДАЛИТЬ "ЛИСТ" (УЗЕЛ, ОБА ПОДДЕРЕВА КОТОРОГО 
ПУСТЫ) ИЛИ УЗЕЛ, В КОТОРОМ $|LLINK|=\NULL$ ИЛИ~$|RLINK|=\NULL$. нО ЕСЛИ 
ОБЕ ССЫЛКИ НЕ ПУСТЫ, НАДО ДЕЙСТВОВАТЬ ОСОБЫМ ОБРАЗОМ---ВЕДЬ НЕЛЬЗЯ В ОДНОМ 
МЕСТЕ ХРАНИТЬ ДВА УКАЗАТЕЛЯ.

в КАЧЕСТВЕ ПРИМЕРА СНОВА РАССМОТРИМ РИС.~10. кАК УДАЛИТЬ |CAPRICORN|? вОТ 
ОДНО ИЗ РЕШЕНИЙ: УДАЛИТЬ \emph{СЛЕДУЮЩИЙ} БЛИЖАЙШИЙ УЗЕЛ, ЛЕВАЯ ССЫЛКА 
КОТОРОГО ПУСТА, И ЗАТЕМ ВЕРНУТЬ ЕГО НА МЕСТО УЗЛА, КОТОРЫЙ ДЕЙСТВИТЕЛЬНО 
ТРЕБУЕТСЯ УДАЛИТЬ. нАПРИМЕР, НА РИС.~10 СНАЧАЛА УДАЛЯЕТСЯ |GEMINI|, 
ЗАТЕМ |CAPRICORN| ЗАМЕНЯЕТСЯ НА |GEMINI|. тАКАЯ ОПЕРАЦИЯ СОХРАНЯЕТ ПОРЯДОК 
ЭЛЕМЕНТОВ ТАБЛИЦЫ. аЛГОРИТМ~D РЕАЛИЗУЕТ ЭТУ ИДЕЮ.

\alg D.(уДАЛЕНИЕ ИЗ ДЕРЕВА.) чЕРЕЗ |Q| ОБОЗНАЧИМ ПЕРЕМЕННУЮ, УКАЗЫВАЮЩУЮ 
НА УЗЕЛ БИНАРНОГО ДЕРЕВА ПОИСКА, КОТОРОЕ ПРЕДСТАВЛЕНО КАК В АЛГОРИТМЕ~T. 
дАННЫЙ АЛГОРИТМ УДАЛЯЕТ ЭТОТ УЗЕЛ, ОСТАВЛЯЯ БИНАРНОЕ ДЕРЕВО ПОИСКА. (нА 
САМОМ ДЕЛЕ МЫ ИМЕЕМ ИЛИ $|Q|\equiv|ROOT|$, ИЛИ $|Q|\equiv|LLINK|(|P|)$, 
ИЛИ $|Q|\equiv|RLINK|(|P|)$ ДЛЯ НЕКОТОРОГО УЗЛА~|P|. аЛГОРИТМ ИЗМЕНЯЕТ В 
ПАМЯТИ ЗНАЧЕНИЕ~|Q| В СООТВЕТСТВИИ С ОСУЩЕСТВЛ╕ННЫМ УДАЛЕНИЕМ.)

\st[сСЫЛКА |RLINK|  ПУСТА?] уСТАНОВИТЬ $|T|\asg |Q|$. еСЛИ 
$|RLINK|(|T|)=\NULL$, УСТАНОВИТЬ $|Q|\asg|LLINK|(|T|)$ И ПЕРЕЙТИ НА~\stp{4}.

\st [нАЙТИ ПРЕЕМНИКА.] уСТАНОВИТЬ $|R|\asg|RLINK|(|T|)$. еСЛИ
$|LLINK|(|R|)=\NULL$, УСТАНОВИТЬ $|LLINK|(|R|)\asg|LLINK|(|T|)$, 
$|Q|\asg|R|$ И ПЕРЕЙТИ НА~\stp{4}.
%%510
\st[нАЙТИ ПУСТУЮ ССЫЛКУ |LLINK|.] уСТАНОВИТЬ $|S|\asg|LLINK|(|R|)$. еСЛИ 
$|LLINK|(|S|)\ne\NULL$, УСТАНОВИТЬ $|R|\asg|S|$ И ПОВТОРЯТЬ ШАГ ДО ТЕХ ПОР,
 ПОКА НЕ ПОЛУЧИМ $|LLINK|(|S|)=\NULL$. (тЕПЕРЬ |S| УКАЗЫВАЕТ НА 
СЛЕДУЮЩИЙ ПОСЛЕ |Q| ЭЛЕМЕНТ ПРИ СИММЕТРИЧНОМ ОБХОДЕ.) нАКОНЕЦ, УСТАНОВИТЬ  
$|LLINK|(|S|)\asg|LLINK|(|T|)$, $|LLINK|(|R|)\asg|RLINK|(|S|)$, 
$|RLINK|(|S|)\asg|RLINK|(|T|)$, $|Q|\asg|S|$.

\st[оСВОБОДИТЬ УЗЕЛ.] вЫПОЛНИТЬ $|AVAIL|\Asg|T|$ (Т.~Е. ВЕРНУТЬ УЗЕЛ В ПУЛ 
СВОБОДНОЙ ПАМЯТИ).
\algend

чИТАТЕЛЬ МОЖЕТ ИСПЫТАТЬ ЭТОТ АЛГОРИТМ, УДАЛЯЯ УЗЛЫ |AQUARIUS|, |CANCER| 
И~|CAPRICORN| ДЕРЕВА РИС.~10; КАЖДЫЙ СЛУЧАЙ ИМЕЕТ СВОИ ОСОБЕННОСТИ. 
вНИМАТЕЛЬНЫЙ ЧИТАТЕЛЬ, ВЕРОЯТНО, ЗАМЕТИЛ, ЧТО ОТДЕЛЬНО НЕ ВЫДЕЛЕН СЛУЧАЙ 
$|RLINK|(|T|)\ne\NULL$, $|LLINK|(|T|)=\NULL$; МЫ ОБСУДИМ ЭТО НЕСКОЛЬКО 
ПОЗЖЕ, ТАК КАК АЛГОРИТМ В ТОМ ВИДЕ, В КОТОРОМ ОН ПРЕДСТАВЛЕН ЗДЕСЬ, 
ОБЛАДАЕТ ВЕСЬМА ИНТЕРЕСНЫМИ СВОЙСТВАМИ.

пОСКОЛЬКУ В АЛГОРИТМЕ~D НЕТ НИКАКОЙ СИММЕТРИИ МЕЖДУ ПРАВЫМ И ЛЕВЫМ, ТО 
КАЖЕТСЯ, ЧТО ДЛИННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ СЛУЧАЙНЫХ УДАЛЕНИЙ И ВСТАВОК 
РАЗБАЛАНСИРУЕТ ДЕРЕВО, И ВЫВЕДЕННЫЕ ОЦЕНКИ ЭФФЕКТИВНОСТИ ПОТЕРЯЮТ СИЛУ. 
нО В ДЕЙСТВИТЕЛЬНОСТИ ВЫРОЖДЕНИЯ ВОВСЕ НЕ ПРОИЗОЙДЕТ!

\proclaim {тЕОРЕМА н (т.~н.~хИББАРД, 1962)}. пОСЛЕ УДАЛЕНИЯ ПОСРЕДСТВОМ 
АЛГОРИТМА~D СЛУЧАЙНОГО УЗЛА СЛУЧАЙНОГО ДЕРЕВА ВНОВЬ ПОЛУЧАЕТСЯ СЛУЧАЙНОЕ ДЕРЕВО.

[нЕ ЛЮБЯЩИЕ МАТЕМАТИКУ, ПРОПУСТИТЕ, ПОЖАЛУЙСТА, ВПЛОТЬ ДО (10)!] тАКАЯ 
ФОРМУЛИРОВКА ТЕОРЕМЫ, РАЗУМЕЕТСЯ, ВЕСЬМА ТУМАННА. оПИШЕМ СИТУАЦИЮ БОЛЕЕ 
ТОЧНО. пУСТЬ $\cJ$---ДЕРЕВО ИЗ $n$~ЭЛЕМЕНТОВ, А $P(\cJ)$---ВЕРОЯТНОСТЬ 
ПОЯВЛЕНИЯ~$\cJ$, ЕСЛИ ЕГО КЛЮЧИ ВСТАВЛЯЮТСЯ СЛУЧАЙНЫМ ОБРАЗОМ С ПОМОЩЬЮ 
АЛГОРИТМА~T. нЕКОТОРЫЕ ДЕРЕВЬЯ ПОЯВЛЯЮТСЯ С БОЛЬШЕЙ ВЕРОЯТНОСТЬЮ, ЧЕМ 
ДРУГИЕ. чЕРЕЗ $Q(\cJ)$ ОБОЗНАЧИМ ВЕРОЯТНОСТЬ ПОЛУЧЕНИЯ~$\cJ$ ПОСЛЕ 
ВСТАВКИ В СЛУЧАЙНОМ ПОРЯДКЕ $n+1$~КЛЮЧЕЙ (ПОСРЕДСТВОМ АЛГОРИТМА~T) И 
ПОСЛЕДУЮЩЕГО УДАЛЕНИЯ С ПОМОЩЬЮ АЛГОРИТМА~D ОДНОГО ИЗ ЭТИХ ЭЛЕМЕНТОВ, 
ВЫБРАННОГО СЛУЧАЙНО. пРИ ВЫЧИСЛЕНИИ~$P(\cJ)$ ПРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ 
$n~$~ПЕРЕСТАНОВОК КЛЮЧЕЙ РАВНОВЕРОЯТНЫ;
ПРИ НАХОЖДЕНИИ $Q(\cJ)$ МЫ СЧИТАЕМ, ЧТО $(n+1)(n+1)!$~ПЕРЕСТАНОВОК 
КЛЮЧЕЙ И ВЫБОРОВ КЛЮЧА ДЛЯ УДАЛЕНИЯ РАВНОВЕРОЯТНЫ. тЕОРЕМА УТВЕРЖДАЕТ, ЧТО 
$P(\cJ)=Q(\cJ)$ ДЛЯ ВСЕХ~$\cJ$.

\proof пО УСЛОВИЮ РАВНОВЕРОЯТНЫ НЕ ДЕРЕВЬЯ, А ПЕРЕСТАНОВКИ, ПОЭТОМУ 
БУДЕМ ДОКАЗЫВАТЬ ТЕОРЕМУ, РАССМАТРИВАЯ В КАЧЕСТВЕ СЛУЧАЙНЫХ ОБоЕКТОВ 
\emph{ПЕРЕСТАНОВКИ}. оПРЕДЕЛИМ СНАЧАЛА УДАЛЕНИЕ ИЗ ПЕРЕСТАНОВКИ И ЗАТЕМ 
ДОКАЖЕМ, ЧТО "ПОСЛЕ УДАЛЕНИЯ ИЗ СЛУЧАЙНОЙ ПЕРЕСТАНОВКИ СЛУЧАЙНОГО 
ЭЛЕМЕНТА ОСТАЕТСЯ СЛУЧАЙНАЯ ПЕРЕСТАНОВКА".

%%511

пУСТЬ $a_1$ $a_2$~\dots $a_{n+1}$---ПЕРЕСТАНОВКА МНОЖЕСТВА 
$\{\,1, 2,~\ldots, n+1\,\}$;
МЫ ХОТИМ ОПРЕДЕЛИТЬ ОПЕРАЦИЮ УДАЛЕНИЯ ЭЛЕМЕНТА~$a_i$, ПОЛУЧИВ В РЕЗУЛЬТАТЕ 
ПЕРЕСТАНОВКУ $b_1$ $b_2$~\dots $b_n$  МНОЖЕСТВА 
$\{\,1, 2,~\ldots, n\,\}$. эТА ОПЕРАЦИЯ ДОЛЖНА БЫТЬ СОГЛАСОВАНА С 
АЛГОРИТМАМИ~т И~D, Т.~Е. ЕСЛИ ОТПРАВИТЬСЯ ОТ ДЕРЕВА, ПОСТРОЕННОГО 
ПОСЛЕДОВАТЕЛЬНЫМИ ВСТАВКАМИ $a_1$, $a_2$,~\dots, $a_{n+1}$, И 
УДАЛИТЬ~$a_i$  С ПЕРЕНУМЕРАЦИЕЙ КЛЮЧЕЙ ЧИСЛАМИ ОТ~1 ДО~$n$, ТО ПОЛУЧИТСЯ 
ДЕРЕВО, КОТОРОЕ МОГЛО БЫТЬ ПОСТРОЕНО ПОСЛЕДОВАТЕЛЬНЫМИ ВСТАВКАМИ $b_1$ 
$b_2$~\dots $b_n$.

к СЧАСТЬЮ, ОПРЕДЕЛИТЬ ТАКУЮ ОПЕРАЦИЮ НЕТРУДНО. вОЗМОЖНЫ ДВА СЛУЧАЯ:

\medskip{
\narrower
\noindent{\sl сЛУЧАЙ 1:\/}
 $a_i=n+1$ ИЛИ~$a_i+1=a_j$ ДЛЯ НЕКОТОРОГО $j<i$. (эТО, В СУЩНОСТИ, ЕСТЬ 
УСЛОВИЕ "$|RLINK|(a_i)=\NULL$".) уДАЛЯЕМ~$a_i$ ИЗ ПОСЛЕДОВАТЕЛЬНОСТИ И 
ВЫЧИТАЕМ ЕДИНИЦУ ИЗ ВСЕХ ЭЛЕМЕНТОВ, БОЛЬШИХ~$a_i$.

\smallskip
\noindent{\sl сЛУЧАЙ 2:\/}
 $a_i+1=a_j$ ДЛЯ НЕКОТОРОГО $j>i$. зАМЕНЯЕМ $a_i$ НА~$a_j$, УДАЛЯЕМ $a_j$ 
С ПЕРВОНАЧАЛЬНОЙ ПОЗИЦИИ И ВЫЧИТАЕМ, ЕДИНИЦУ ИЗ ВСЕХ ЭЛЕМЕНТОВ, БОЛЬШИХ~$a_i$.

}\medskip

нАПРИМЕР, РАССМОТРИМ ПЕРЕСТАНОВКУ 4~6~1~3~5~2. еСЛИ ПОМЕТИТЬ ЭЛЕМЕНТ, 
КОТОРЫЙ НУЖНО УДАЛИТЬ, ЗАКЛЮЧИВ ЕГО В КРУЖОК, ТО ПОЛУЧИТСЯ
{\def\r#1{\roundit{$#1$}}
$$
\matrix{
\r4 & 6 & 1 & 3 & 5 & 2 & = & 4 & 5 & 1 & 3 & 2 \cr
    4&\r6&1 & 3 & 5 & 2 & = & 4 & 1 & 3 & 5 & 2 \cr
    4& 6 &\r1&3 & 5 & 2 & = & 3 & 5 & 1 & 2 & 4 \cr
}
\qquad
\matrix{
4 & 6 & 1 &\r3& 5 & 2  & = & 3 & 5 & 1 & 4 & 2 \cr
4 & 6 & 1 & 3 &\r5& 2  & = & 4 & 5 & 1 & 3 & 2 \cr
4 & 6 & 1 &3  & 5 &\r2 & = & 3 & 5 & 1 & 2 & 4 \cr
}
$$
}
пОСКОЛЬКУ ВСЕГО МОЖНО СДЕЛАТЬ $(n+1)(n+1)!$ РАЗЛИЧНЫХ УДАЛЕНИЙ, ТЕОРЕМА 
БУДЕТ УСТАНОВЛЕНА, ЕСЛИ МЫ ПОКАЖЕМ, ЧТО КАЖДУЮ ПЕРЕСТАНОВКУ МНОЖЕСТВА 
$\{\, 1, 2,~\dots, n\,\}$ МОЖНО ПОЛУЧИТЬ КАК РЕЗУЛЬТАТ ПРИМЕНЕНИЯ РОВНО $(n+1)^2$~УДАЛЕНИЙ.

рАССМОТРИМ ПЕРЕСТАНОВКУ $b_1$ $b_2$~\dots $b_n$ МНОЖЕСТВА 
$\{\, 1, 2,~\dots, n\,\}$. оПРЕДЕЛИМ $(n+1)^2$~УДАЛЕНИЙ, НО ОДНОМУ ДЛЯ 
КАЖДОЙ ПАРЫ $i, j$ ($1\le i,j\le n+1$).

еСЛИ $i<j$, ИСКОМЫМ УДАЛЕНИЕМ БУДЕТ
$$
b'_1\ldots b'_{i-1} \roundit{b_i} b'_{i+1}\ldots b'_{j-1} (b_i+1) 
b'_j\ldots b'_n.
\eqno(7)
$$
зДЕСЬ И ДАЛЕЕ $b'_k$ ОБОЗНАЧАЕТ $b_k$ ИЛИ~$b_k+1$ В ЗАВИСИМОСТИ ОТТОГО, 
МЕНЬШЕ $b_k$ ПОМЕЧЕННОГО ЭЛЕМЕНТА ИЛИ НЕТ. эТО УДАЛЕНИЕ СООТВЕТСТВУЕТ {\sl СЛУЧАЮ~2.\/}

еСЛИ $i>j$, ИСКОМЫМ УДАЛЕНИЕМ БУДЕТ
$$
b'_1\ldots b'_{i-1} \roundit{b_j} b'_i \ldots b'_n,
\eqno(8)
$$
ЧТО СООТВЕТСТВУЕТ {\sl СЛУЧАЮ~1.\/}

%% 512

нАКОНЕЦ, ПРИ $i=j$ ИМЕЕМ ДРУГИЕ УДАЛЕНИЯ:
\picture{рИС. СТР. 512}
КОТОРЫЕ ТОЖЕ ОПИСЫВАЮТСЯ {\sl СЛУЧАЕМ~1.\/}

пОЛОЖИВ $n=4$, РАССМОТРИМ В КАЧЕСТВЕ ПРИМЕРА 25~УДАЛЕНИЙ, ПРИВОДЯЩИХ К 
ПЕРЕСТАНОВКЕ 3~1~4~2:
{\def\r#1{\node{#1}}
\ctable{\hfill$#$\hfill\bskip\bskip&&\hfill$#$\hfill\bskip\bskip\cr
   & i=1 & i=2 & i=3 & i=4 & i=5\cr
j=1&\r5~3~1~4~2 &4~\r3~1~5~2 &4~1~\r3~5~2 &4~1~5~\r3~2 &4~1~5~2~\r3\cr
j=2&\r3~4~1~5~2 &3~\r5~1~4~2 &4~2~\r1~5~3 &4~2~5~\r1~3 &4~2~5~3~\r1\cr
j=3&\r3~1~4~5~2 &4~\r1~2~5~3 &3~1~\r5~4~2 &3~1~5~\r4~2 &3~1~5~2~\r4\cr
j=4&\r3~1~5~4~2 &4~\r1~5~2~3 &3~1~\r4~5~2 &3~1~4~\r5~2 &4~1~5~3~\r2\cr
j=5&\r3~1~5~2~4 &4~\r1~5~3~2 &3~1~\r4~2~5 &4~1~5~\r2~3 &3~1~4~2~\r5\cr
}}

пОМЕЧЕННЫЙ ЭЛЕМЕНТ ВСЕГДА СТОИТ В $i\hbox{-Й}$ ПОЗИЦИИ, И ДЛЯ 
ФИКСИРОВАННОГО~$i$ МЫ ПОСТРОИЛИ $(n+1)$ РАЗЛИЧНЫХ УДАЛЕНИЙ, ПО ОДНОМУ 
ДЛЯ КАЖДОГО~$j$; СЛЕДОВАТЕЛЬНО, ДЛЯ КАЖДОЙ ПЕРЕСТАНОВКИ $b_1$ $b_2$~\dots 
$b_n$ ПОСТРОЕНО $(n+1)^2$ РАЗЛИЧНЫХ УДАЛЕНИЙ. дЛЯ ЗАВЕРШЕНИЯ ДОКАЗАТЕЛЬСТВА 
ЗАМЕТИМ, ЧТО ВСЕГО ИМЕЕТСЯ $(n+1)^2!$~УДАЛЕНИЙ.
\proofend

дОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~H НЕ ТОЛЬКО ОПИСЫВАЕТ СИТУАЦИЮ ПОСЛЕ УДАЛЕНИЙ, НО И 
ПОМОГАЕТ ПРИ АНАЛИЗЕ СРЕДНЕГО ВРЕМЕНИ УДАЛЕНИЯ. уПРАЖНЕНИЕ~12 ПОКАЗЫВАЕТ, 
ЧТО ПРИ УДАЛЕНИИ СЛУЧАЙНОГО ЭЛЕМЕНТА ИЗ СЛУЧАЙНОЙ ТАБЛИЦЫ ШАГ~D2 
ВЫПОЛНЯЕТСЯ В СРЕДНЕМ ЧУТЬ РЕЖЕ, ЧЕМ В ПОЛОВИНЕ СЛУЧАЕВ.

рАССМОТРИМ ТЕПЕРЬ, СКОЛЬКО РАЗ ПРОХОДИТСЯ ЦИКЛ В ШАГЕ~D3. пРЕДПОЛОЖИМ, ЧТО 
УДАЛЯЕТСЯ УЗЕЛ, РАСПОЛОЖЕННЫЙ НА УРОВНЕ~$l$, А \emph{ВНЕШНИЙ} УЗЕЛ, 
НЕПОСРЕДСТВЕННО СЛЕДУЮЩИЙ ЗА НИМ ПРИ СИММЕТРИЧНОМ ОБХОДЕ, НАХОДИТСЯ НА 
УРОВНЕ~$k$. нАПРИМЕР, ПРИ УДАЛЕНИИ УЗЛА |CAPRICORN| (РИС.~10) ИМЕЕМ 
$l=0$ И~$k=3$, ТАК КАК УЗЕЛ~\leaf{4} РАСПОЛОЖЕН НА УРОВНЕ~3. еСЛИ $k=l+1$, 
ТО $|RLINK|(|T|)=\NULL$  В ШАГЕ~D1; ЕСЛИ $k>l+1$, МЫ БУДЕМ ПРИСВАИВАТЬ 
$|S|\asg |LLINK|(|R|)$ (ШАГ~D3) РОВНО $k-l-2$~РАЗ. сРЕДНЕЕ ЗНАЧЕНИЕ~$l$ РАВНО
$$
(\hbox{ДЛИНА ВНУТРЕННЕГО ПУТИ})/N;
$$
СРЕДНЕЕ ЗНАЧЕНИЕ~$k$ РАВНО
$$
(\hbox{ДЛИНА ВНЕШНЕГО ПУТИ})/N
-(\hbox{РАССТОЯНИЕ ДО САМОГО ЛЕВОГО ВНЕШНЕГО УЗЛА})/N.
$$
рАССТОЯНИЕ ДО САМОГО ЛЕВОГО ВНЕШНЕГО УЗЛА РАВНО КОЛИЧЕСТВУ ТАКИХ~$a_i$ ИЗ 
ВСТАВЛЯЕМОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, ЧТО $a_i<a_j$, $1\le j<i$ (ВКЛЮЧАЯ~$a_1$); 
СРЕДНЕЕ ЗНАЧЕНИЕ ЭТОЙ ВЕЛИЧИНЫ, СОГЛАСНО П.~1.2.10,
%%513
ЕСТЬ~$H_N$. тАК КАК ДЛИНА ВНЕШНЕГО ПУТИ НА $2N$ БОЛЬШЕ ДЛИНЫ ВНУТРЕННЕГО, 
СРЕДНЕЕ ЗНАЧЕНИЕ~$k-l-2$ РАВНО~$-H_N/N$. дОБАВЛЯЯ СЮДА СРЕДНЕЕ КОЛИЧЕСТВО 
СЛУЧАЕВ, КОГДА $k-l-2$ ЕСТЬ~$-1$, ПОЛУЧАЕМ, ЧТО ПРИ СЛУЧАЙНОМ УДАЛЕНИИ 
\emph{ОПЕРАЦИЯ $|S|\asg|LLINK|(|R|)$ В ШАГЕ~D3 ВЫПОЛНЯЕТСЯ В СРЕДНЕМ ЛИШЬ
$$
{1\over2}+{{1\over2}-H_N\over N}
\eqno(10)
$$
РАЗ.} эТО УСПОКАИВАЕТ, ТАК КАК В НАИХУДШЕМ СЛУЧАЕ УДАЛЕНИЯ МОГУТ 
ПРОИЗВОДИТЬСЯ ДОВОЛЬНО МЕДЛЕННО (СМ. УПР.~11).

вЫШЕ ОТМЕЧАЛОСЬ, ЧТО В АЛГОРИТМЕ~D НЕТ ПРОВЕРКИ $|LLINK|(|T|)=\NULL$, ХОТЯ 
УДАЛИТЬ ТАКУЮ ВЕРШИНУ ЛЕГКО. мОЖНО ДОБАВИТЬ НОВЫЙ ШАГ МЕЖДУ~D1 И~D2:
\medskip
D$1{1\over2}$.~[сСЫЛКА |LLINK| ПУСТА?] еСЛИ $|LLINK|(|T|)=\NULL$, 
УСТАНОВИТЬ $|Q|\asg|RLINK|(|T|)$ И ПЕРЕЙТИ НА~D4.
\medskip
\noindent уПРАЖНЕНИЕ~14 ПОКАЗЫВАЕТ, ЧТО ДЕРЕВО ПОСЛЕ РАБОТЫ АЛГОРИТМА~D 
С ДОПОЛНИТЕЛЬНЫМ ШАГОМ ИМЕЕТ НЕ ТОЛЬКО НЕ БОЛЬШУЮ, А ИНОГДА ДАЖЕ МЕНЬШУЮ 
ДЛИНУ ПУТИ, ЧЕМ ПОСЛЕ РАБОТЫ ОБЫЧНОГО АЛГОРИТМА~D. тАК ЧТО 
ПОСЛЕДОВАТЕЛЬНОСТЬ ВСТАВОК И УДАЛЕНИЙ С ПОМОЩЬЮ МОДИФИКАЦИИ АЛГОРИТМА~D 
ПРИВОДИТ К ДЕРЕВЬЯМ, КОТОРЫЕ В ДЕЙСТВИТЕЛЬНОСТИ \emph{ЛУЧШЕ}, ЧЕМ 
ПРЕДСКАЗЫВАЕТ ТЕОРИЯ СЛУЧАЙНЫХ ДЕРЕВЬЕВ; СРЕДНЕЕ ВРЕМЯ ПОИСКА С ВСТАВКОЙ 
ИМЕЕТ ТЕНДЕНЦИЮ К УМЕНЬШЕНИЮ.

\section чАСТОТА ОБРАЩЕНИЙ. дО СИХ ПОР ПРЕДПОЛАГАЛОСЬ, ЧТО ВСЕ КЛЮЧИ С 
РАВНОЙ ВЕРОЯТНОСТЬЮ МОГУТ БЫТЬ АРГУМЕНТАМИ ПОИСКА. рАССМОТРИМ ТЕПЕРЬ 
БОЛЕЕ ОБЩИЙ СЛУЧАЙ, КОГДА С ВЕРОЯТНОСТЬЮ~$p_k$ ОТЫСКИВАЕТСЯ ЭЛЕМЕНТ, 
$k\hbox{-М}$ ВСТАВЛЕННЫЙ В ТАБЛИЦУ, ПРИЧЕМ $p_1+\cdots+p_N=1$. пРИ 
СОХРАНЕНИИ ПРЕДПОЛОЖЕНИЯ О СЛУЧАЙНОМ ПОРЯДКЕ (ФОРМА ДЕРЕВА ОСТАЕТСЯ 
СЛУЧАЙНОЙ) МОДИФИКАЦИЯ ВЫРАЖЕНИЯ~(2) ПОКАЗЫВАЕТ, ЧТО СРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ В ПРОЦЕССЕ УДАЧНОГО ПОИСКА СОСТАВЛЯЕТ
$$
1+\sum_{1\le k\le N} p_k(2H_k-2)=2\sum_{1\le k\le N} p_kH_k-1.
\eqno(11)
$$
(сР. С~(5).)

нАПРИМЕР, ЕСЛИ ВЕРОЯТНОСТИ ПОДЧИНЯЮТСЯ ЗАКОНУ зИПФА (6.1-8), СРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ СВОДИТСЯ К
$$
H_N-1+H^{(2)}_N/H_N
\eqno(12)
$$
(ПРЕДПОЛАГАЕТСЯ, ЧТО МЫ ВСТАВЛЯЕМ КЛЮЧИ В ПОРЯДКЕ УМЕНЬШЕНИЯ .ВАЖНОСТИ; СМ.
 УПР.~18). фОРМУЛА~(6) ПРЕДСКАЗЫВАЕТ ПРИМЕРНО В ДВА РАЗА БОЛЬШУЮ ВЕЛИЧИНУ; 
ПРИ БИНАРНОМ ПОИСКЕ МЫ ТАКЖЕ ПРОИЗВЕЛИ БЫ БОЛЬШЕ СРАВНЕНИЙ.
%%514
нАПРИМЕР, НА РИС.~12 ИЗОБРАЖЕНО ДЕРЕВО, ПОЛУЧЕННОЕ ПОСЛЕДОВАТЕЛЬНЫМИ 
ВСТАВКАМИ В ПОРЯДКЕ УБЫВАНИЯ ЧАСТОТ 31~НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО 
АНГЛИЙСКОГО СЛОВА. оТНОСИТЕЛЬНАЯ ЧАСТОТА ПОМЕЩЕНА ПОД КАЖДЫМ СЛОВОМ. [сР. 
н.~F.~Gaines, Cryptanalysis (New York: Dover, 1956), 226.] сРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ ПРИ
\picture{рИС. 12 31 НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОЕ АНГЛИЙСКОЕ СЛОВО; ВСТАВКИ В 
ПОРЯДКЕ УМЕНЬШЕНИЯ ЧАСТОТ.}
УДАЧНОМ ПОИСКЕ ПО ТАКОМУ ДЕРЕВУ РАВНО~$4.042$; СООТВЕТСТВУЮЩИЙ БИНАРНЫЙ 
ПОИСК, ИСПОЛЬЗУЮЩИЙ АЛГОРИТМ~6.2.1в ИЛИ~C, ПОТРЕБОВАЛ БЫ $4.393$~СРАВНЕНИЯ.

\section оПТИМАЛЬНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА. уМЕСТНО СПРОСИТЬ, КАКОЕ 
ДЕРЕВО ЯВЛЯЕТСЯ НАИЛУЧШИМ ДЛЯ ПОИСКА ПО ТАБЛИЦЕ, ЕСЛИ КЛЮЧИ ЗАПРАШИВАЮТСЯ 
С ДАННЫМИ ЧАСТОТАМИ? нАПРИМЕР, ОПТИМАЛЬНОЕ ДЕРЕВО ДЛЯ 31~НАИБОЛЕЕ 
УПОТРЕБИТЕЛЬНОГО АНГЛИЙСКОГО СЛОВА ИЗОБРАЖЕНО НА РИС.~13; В СРЕДНЕМ НА 
УДАЧНЫЙ ПОИСК ТРЕБУЕТСЯ 3.437 СРАВНЕНИЯ.

иССЛЕДУЕМ ПРОБЛЕМУ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО ДЕРЕВА. в СЛУЧАЕ $N=3$ И ПРИ 
СООТВЕТСТВЕННЫХ ВЕРОЯТНОСТЯХ $p$, $q$, $m$ КЛЮЧЕЙ
%%515
%%515
\picture{рИС. 13 оПТИМАЛЬНОЕ ДЕРЕВО ПОИСКА ДЛЯ 31 НАИБОЛЕЕ 
УПОТРЕБИТЕЛЬНОГО АНГЛИЙСКОГО СЛОВА.}
%%516
$K_1<K_2<K_3$ ВОЗМОЖНЫ ПЯТЬ ДЕРЕВЬЕВ:
\picture{рИС. СТР. 516}
нА РИС.~14 ПОКАЗАНЫ ДИАПАЗОНЫ ВЕЛИЧИН $p$, $q$, $r$, ДЛЯ КОТОРЫХ КАЖДОЕ ИЗ 
ДЕРЕВЬЕВ ОПТИМАЛЬНО; СБАЛАНСИРОВАННОЕ ДЕРЕВО ЯВЛЯЕТСЯ НАИЛУЧШИМ ПРИМЕРНО 
В 45\% СЛУЧАЕВ, ЕСЛИ $p$, $q$, $r$ СЛУЧАЙНЫ (СМ. УПР.~21).

\picture{рИС. 14.             зДЕСЬ $(p, q, r)$ СУТЬ ОТНОСИТЕЛЬНЫЕ ЧАСТОТЫ 
$(k_1, k_2, k_3)$, ЭТОТ РИСУНОК ПОКАЗЫВАЕТ; КАКОЕ ИЗ ПЯТИ ДЕРЕВЬЕВ (13) 
ЯВЛЯЕТСЯ НАИЛУЧШИМ. тОТ ФАКТ, ЧТО $p+q+r=1$, ДЕЛАЕТ РИСУНОК ДВУМЕРНЫМ, 
НЕСМОТРЯ НА НАЛИЧИЕ ТРЕХ КООРДИНАТ.
}

к СОЖАЛЕНИЮ, ПРИ БОЛЬШИХ $N$ СУЩЕСТВУЕТ
$$
\perm{2N}{N}/(N+1)\approx 4^N/(\sqrt{\pi}N^{3/2})
$$
БИНАРНЫХ ДЕРЕВЬЕВ, ТАК ЧТО МЫ НЕ В СОСТОЯНИИ ВСЕ ИХ ПЕРЕБРАТЬ И ВЫБРАТЬ 
НАИЛУЧШЕЕ. пОЭТОМУ, ЧТОБЫ ПРИДУМАТЬ БОЛЕЕ
%%517
УДАЧНЫЙ СПОСОБ ОТЫСКИВАТЬ ОПТИМАЛЬНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА, НУЖНО БЛИЖЕ 
ПОЗНАКОМИТЬСЯ С ИХ СВОЙСТВАМИ.

дО СИХ ПОР МЫ ИЗУЧАЛИ ЛИШЬ ВЕРОЯТНОСТИ ПРИ УДАЧНОМ ПОИСКЕ; ОКАЗЫВАЕТСЯ, 
СЛУЧАЙ НЕУДАЧИ СТОЛЬ ЖЕ ВАЖЕН. нАПРИМЕР, 31 СЛОВО (РИС.~13) СОСТАВЛЯЕТ 
ЛИШЬ ОКОЛО 36\% ТИПИЧНОГО АНГЛИЙСКОГО ТЕКСТА; ОСТАЛЬНЫЕ 64\%, НЕСОМНЕННО, 
ПОВЛИЯЮТ НА СТРУКТУРУ ОПТИМАЛЬНОГО ДЕРЕВА ПОИСКА.

сЛЕДОВАТЕЛЬНО, ПОСТАВИМ ЗАДАЧУ ТАКИМ ОБРАЗОМ: ДАНО $2n+1$~ЧИСЕЛ $p_1$, 
$p_2$,~\dots, $p_n$ И~$q_0$, $q_1$,~\dots, $q_n$, ГДЕ
$$
\eqalign{
p_i&=\hbox{ ВЕРОЯТНОСТЬ ТОГО, ЧТО АРГУМЕНТОМ ПОИСКА ЯВЛЯЕТСЯ $K_i$};\cr
q_i&=\hbox{ ВЕРОЯТНОСТЬ ТОГО, ЧТО АРГУМЕНТ ПОИСКА ЛЕЖИТ МЕЖДУ $K_i$ И~$K_{i+1}$}.\cr
}
$$
(пО ОПРЕДЕЛЕНИЮ $q_0$ ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО АРГУМЕНТ ПОИСКА МЕНЬШЕ 
$K_1$, a $q_n$ ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО АРГУМЕНТ ПОИСКА БОЛЬШЕ~$K_n$.) 
тАКИМ ОБРАЗОМ, 
$p_1+p_2+\cdots+p_n+q_0+q_1+\cdots+q_n=1$, И МЫ ХОТИМ НАЙТИ БИНАРНОЕ 
ДЕРЕВО, МИНИМИЗИРУЮЩЕЕ МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ ЧИСЛА СРАВНЕНИЙ ПРИ ПОИСКЕ, 
А ИМЕННО
$$
\sum_{1\le j\le n} p_i(\hbox{УРОВЕНЬ (\node{$j$})}+1)
+\sum_{0\le k\le n} q_k(\hbox{УРОВЕНЬ (\leaf{$k$})}),
\eqno(14)
$$
ГДЕ \node{j} ЕСТЬ $j\hbox{-Й}$~ВНУТРЕННИЙ УЗЕЛ ПРИ СИММЕТРИЧНОМ ОБХОДЕ, a 
\leaf{$k$} ЕСТЬ $(k+1)\hbox{-Й}$~ВНЕШНИЙ УЗЕЛ; КОРЕНЬ НАХОДИТСЯ НА НУЛЕВОМ 
УРОВНЕ. тАК, МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ ЧИСЛА СРАВНЕНИЙ ДЛЯ БИНАРНОГО ДЕРЕВА
\picture{ рИС. СТР. 517.}
РАВНО $2q_0+2p_1+3q_1+3p_2+3q_2+p_3+q_3$. нАЗОВЕМ ЭТО \dfn{ЦЕНОЙ} ДЕРЕВА; 
СКАЖЕМ, ЧТО ДЕРЕВО С МИНИМАЛЬНОЙ ЦЕНОЙ \emph{ОПТИМАЛЬНО}. пРИ ТАКОМ 
ОПРЕДЕЛЕНИИ НЕТ НУЖДЫ ТРЕБОВАТЬ, ЧТОБЫ $p$ И~$q$ ДАВАЛИ В СУММЕ ЕДИНИЦУ, 
МОЖНО ИСКАТЬ ДЕРЕВО С МИНИМАЛЬНОЙ ЦЕНОЙ ДЛЯ ДАННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ 
"ВЕСОВ" ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$).

в П.~2.3.4.5 МЫ ИЗУЧИЛИ ПРОЦЕДУРУ хАФФМЭНА ДЛЯ ПОСТРОЕНИЯ ДЕРЕВЬЕВ С 
МИНИМАЛЬНОЙ ВЗВЕШЕННОЙ ДЛИНОЙ ПУТИ, НО ЭТОТ МЕТОД ТРЕБУЕТ, ЧТОБЫ ВСЕ $p$ 
РАВНЯЛИСЬ НУЛЮ, А В ПОРОЖДЕННОМ ИМ ДЕРЕВЕ ВНЕШНИЕ УЗЛЫ, ИМЕЮЩИЕ ВЕСА 
($q_0$,~\dots, $q_n$), ОБЫЧНО НЕ
%%518
РАСПОЛАГАЮТСЯ В НУЖНОМ СИММЕТРИЧНОМ ПОРЯДКЕ СЛЕВА НАПРАВО. зНАЧИТ, 
НЕОБХОДИМО ДЕЙСТВОВАТЬ ИНАЧЕ.

вОСПОЛЬЗУЕМСЯ СЛЕДУЮЩИМ ПРИНЦИПОМ: \emph{ЛЮБОЕ ПОДДЕРЕВО ОПТИМАЛЬНОГО 
ДЕРЕВА ОПТИМАЛЬНО}. нАПРИМЕР, ЕСЛИ~(15) ЕСТЬ ОПТИМАЛЬНОЕ ДЕРЕВО ДЛЯ 
ВЕСОВ $(p_1, p_2, p_3; q_0, q_1, q_2, q_3)$, ТО ЛЕВОЕ ПОДДЕРЕВО КОРНЯ 
ДОЛЖНО БЫТЬ ОПТИМАЛЬНЫМ ДЛЯ 
$(p_1, p_2; q_0, q_1, q_2)$, Т.~Е. ЛЮБОЕ УЛУЧШЕНИЕ ПОДДЕРЕВА ВЕДЕТ К 
УЛУЧШЕНИЮ ВСЕГО ДЕРЕВА.

эТОТ ПРИНЦИП ПОДСКАЗЫВАЕТ ВЫЧИСЛИТЕЛЬНУЮ ПРОЦЕДУРУ, С ПОМОЩЬЮ КОТОРОЙ 
СИСТЕМАТИЧЕСКИ НАХОДЯТСЯ ВС╕ БОЛЬШИЕ И БОЛЬШИЕ ОПТИМАЛЬНЫЕ ПОДДЕРЕВЬЯ. мЫ 
ВОСПОЛЬЗОВАЛИСЬ АБСОЛЮТНО ТОЙ ЖЕ ИДЕЕЙ В П.~5.4.9 ДЛЯ ПОСТРОЕНИЯ СХЕМ 
ОПТИМАЛЬНОГО СЛИЯНИЯ; ОБЩИЙ ПОДХОД, ИЗВЕСТНЫЙ ПОД НАЗВАНИЕМ 
"ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ", БУДЕТ ИЗУЧЕН В ГЛ.~7.

чЕРЕЗ $c(i, j)$ ОБОЗНАЧИМ ЦЕНУ ОПТИМАЛЬНОГО ПОДДЕРЕВА С ВЕСАМИ $(p_{i+1},
~\ldots, p_j, q_i,~\ldots, q_j)$, И ПУСТЬ 
$w(i,j)=p_{i+1}+\cdots+p_j+q_i+\cdots+q_j$ БУДЕТ СУММОЙ ЭТИХ ВЕСОВ; $c(i, 
j)$ И~$w(i,j)$ ОПРЕДЕЛЯЮТСЯ ДЛЯ $0\le i\le j\le n$. тАК КАК МИНИМАЛЬНО 
ВОЗМОЖНАЯ ЦЕНА ДЕРЕВА С КОРНЕМ~\node{$k$} РАВНА 
$w(i,j)+c(i, k-1)+c(k,j)$, ИМЕЕМ
$$
\eqalign{
c(i,i)&=0;\cr
c(i,j)&=w(i,j)+\min_{i\le k <j} (c(i,k-1)+c(k,j)) \rem{ ПРИ $i<j$.}\cr
}
\eqno(16)
$$
еСЛИ $i<j$, ТО ЧЕРЕЗ $R(i, j)$ ОБОЗНАЧИМ МНОЖЕСТВО ВСЕХ~$k$, ПРИ КОТОРЫХ 
ДОСТИГАЕТСЯ МИНИМУМ В~(16); ЭТО МНОЖЕСТВО ОПРЕДЕЛЯЕТ ВОЗМОЖНЫЕ КОРНИ 
ОПТИМАЛЬНЫХ ПОДДЕРЕВЬЕВ.

сООТНОШЕНИЯ~(16) ПОЗВОЛЯЮТ НАЙТИ ЗНАЧЕНИЯ~$c(i, j)$ ДЛЯ
$j-i=1$, 2, 3,~\dots, $n$; СУЩЕСТВУЕТ ПРИМЕРНО ${1\over2}n^2$ ТАКИХ 
ЗНАЧЕНИЙ, А ОПЕРАЦИЯ МИНИМИЗАЦИИ ВЫПОЛНЯЕТСЯ ДЛЯ ПРИБЛИЗИТЕЛЬНО 
${1\over6}n^3$ ВЕЛИЧИН~$k$. эТО ЗНАЧИТ, ЧТО ОПТИМАЛЬНОЕ ДЕРЕВО МОЖНО НАЙТИ 
ЗА $O(n^3)$~ЕДИНИЦ ВРЕМЕНИ, ИСПОЛЬЗУЯ $O(n^2)$~ЯЧЕЕК ПАМЯТИ.

в ОЦЕНКЕ ВРЕМЕНИ РАБОТЫ ПОКАЗАТЕЛЬ СТЕПЕНИ ПРИ~$n$ МОЖНО УМЕНЬШИТЬ, ЕСЛИ 
ВОСПОЛЬЗОВАТЬСЯ СВОЙСТВОМ "МОНОТОННОСТИ". пУСТЬ $r(i,j)$ ОБОЗНАЧАЕТ 
ЭЛЕМЕНТ ИЗ~$R(i,j)$; НЕТ НУЖДЫ НАХОДИТЬ ВСЕ МНОЖЕСТВО~$R(i,j)$, НАМ 
ДОСТАТОЧНО ОДНОГО ПРЕДСТАВИТЕЛЯ. в СИЛУ РЕЗУЛЬТАТА УПР.~27 ПОСЛЕ 
НАХОЖДЕНИЯ $r(i,j-1)$ И~$r(i+1, j)$ ЭЛЕМЕНТ~$r(i, j)$ МОЖНО ИСКАТЬ В ПРЕДЕЛАХ
$$
r(i, j-1)\le r(i,j) \le r(i+1, j)
\eqno(17)
$$
ПРИ УСЛОВИИ НЕОТРИЦАТЕЛЬНОСТИ ВЕСОВ. тЕПЕРЬ В~(16) ВМЕСТО $i-j$ НУЖНО 
ПРОВЕРЯТЬ ЛИШЬ $r(i+1, j)-r(i, j-1)+1$ ЗНАЧЕНИЙ~$k$.
%%519
пОЛНЫЙ ОБоЕМ РАБОТЫ, ЕСЛИ $j-i=d$, ОЦЕНИВАЕТСЯ СУММОЙ
$$
\sum_{\scriptstyle d\le j\le n\atop\scriptstyle i=j-d}
(r(i+1,j)-r(i, j-1)+1)=
r(n-d+1,n)+r(0, d-1)+n-d+1<2n,
$$
ПОЭТОМУ ВРЕМЯ ВЫПОЛНЕНИЯ УМЕНЬШАЕТСЯ ДО~$O(n^2)$.

пРЕДЛОЖЕННАЯ ПРОЦЕДУРА ПОДРОБНО ОПИСАНА НИЖЕ.

\alg K.(нАХОЖДЕНИЕ ОПТИМАЛЬНЫХ БИНАРНЫХ ДЕРЕВЬЕВ ПОИСКА.)
дАНЫ НЕОТРИЦАТЕЛЬНЫЕ ВЕСА ($p_1$,~\dots, $p_n$; $q_0$, $q_1$,~\dots, 
$q_n$).  аЛГОРИТМ ПОЗВОЛЯЕТ ПОСТРОИТЬ БИНАРНЫЕ ДЕРЕВЬЯ~$t(i,j)$, 
ИМЕЮЩИЕ МИНИМАЛЬНУЮ (В УКАЗАННОМ ВЫШЕ СМЫСЛЕ) ЦЕНУ ДЛЯ ВЕСОВ 
($p_{i+1}$,~\dots, $p_j$; $q_i$,~\dots, $q_j$). вЫЧИСЛЯЮТСЯ ТРИ МАССИВА:
$$
\matrix{
c[i,j]\hbox{---ЦЕНА $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
r[i,j]\hbox{---КОРЕНЬ $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
w[i,j]\hbox{---ПОЛНЫЙ ВЕС $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
}
$$
рЕЗУЛЬТАТЫ АЛГОРИТМА ОПРЕДЕЛЯЮТСЯ МАССИВОМ~$r$: ЕСЛИ $i=j$, ТО
$t(i,j)$ ПУСТО; ЕСЛИ $i\ne j$, ТО ЛЕВЫМ ПОДДЕРЕВОМ ЯВЛЯЕТСЯ
$t(i, r[i,j]-1)$, А ПРАВЫМ---$t(r[i,j], j)$.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] дЛЯ $0\le i \le n$ УСТАНОВИТЬ $c[i, i]\asg0$,
$w[i,i]\asg q_i$  И~$w[i,j]\asg w[i,j-1]+p_j+q_j$ ПРИ~$j=i+1$,~\dots, $n$. 
зАТЕМ ДЛЯ $1\le j \le n$ УСТАНОВИТЬ $c[j-1,j]\asg w[j-1,j]$ И~$r[j-1,
j]\asg j$. (эТИМ ОПРЕДЕЛЯЮТСЯ ВСЕ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ, СОСТОЯЩИЕ ИЗ ОДНОГО УЗЛА.)

\st[цИКЛ ПО $d$.] вЫПОЛНИТЬ ШАГ~\stp{3} ДЛЯ $d=2$, 3,~\dots, $n$; 
ПОСЛЕ ЭТОГО АЛГОРИТМ ЗАВЕРШАЕТ РАБОТУ.

\st[цИКЛ ПО $j$.] (к ЭТОМУ, МОМЕНТУ НАЙДЕНЫ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ С МЕНЕЕ 
ЧЕМ $d$~УЗЛАМИ. шАГ ОПРЕДЕЛЯЕТ ВСЕ ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ С $d$~УЗЛАМИ.) 
вЫПОЛНИТЬ ШАГ~\stp{4} ДЛЯ $j=d$, $d+1$,~\dots, $n$.

\st[нАЙТИ $c[i,j]$, $r[i,j]$.] уСТАНОВИТЬ $i\asg j-d$, ЗАТЕМ УСТАНОВИТЬ
$$
c[i,j]\asg w[i,j]+\min_{r[i,j-1]\le k \le r[i+1, j]} (c[i,k-1]+c[k,j])
$$
И ЗАНЕСТИ В $r[i,j]$ ВЕЛИЧИНУ~$k$, ПРИ КОТОРОЙ ДОСТИГАЕТСЯ МИНИМУМ. (в 
УПР.~22 ДОКАЗЫВАЕТСЯ,  ЧТО $r[i, j-1]\le r[i+1, j]$.)
\algend

кАК ПРИМЕР РАБОТЫ АЛГОРИТМА~K РАССМОТРИМ РИС.~15, СВЯЗАННЫЙ 
СОРАЗРАБОТКОЙ УКАЗАТЕЛЯ KWIC ("key-word-in-context"---"КЛЮЧЕВОЕ СЛОВО В 
КОНТЕКСТЕ"). зАГОЛОВКИ ВСЕХ СТАТЕЙ ПЕРВЫХ ДЕСЯТИ ТОМОВ {\sl ACM Journal\/} 
БЫЛИ ОТСОРТИРОВАНЫ ТАКИМ ОБРАЗОМ, ЧТОБЫ КАЖДОМУ СЛОВУ КАЖДОГО ЗАГОЛОВКА 
СООТВЕТСТВОВАЛА ОДНА СТРОКА. пРАВДА, НЕКОТОРЫЕ СЛОВА ВРОДЕ "|THE|" И~"|EQUATION|"
%%520
\picture{  рИС 15. оПТИМАЛЬНОЕ БИНАРНОЕ ДЕРЕВО ПОИСКА ДЛЯ ПРИМЕНЕНИЯ 
УКАЗАТЕЛЯ KWIC.}
%%521
БЫЛИ ПРИЗНАНЫ НЕИНФОРМАТИВНЫМИ И НЕ ПОПАЛИ В УКАЗАТЕЛЬ. эТИ СПЕЦИАЛЬНЫЕ 
СЛОВА И ЧАСТОТЫ ИХ ПОЯВЛЕНИЙ ПРЕДСТАВЛЕНЫ НА РИС.~15 ВНУТРЕННИМИ УЗЛАМИ. 
зАМЕТИМ, ЧТО ТАКОЕ НАЗВАНИЕ, КАК "On the solution of an equation for a 
certain new problem" ("о РЕШЕНИИ УРАВНЕНИЯ ДЛЯ НЕКОТОРОЙ НОВОЙ ЗАДАЧИ"), 
БЫЛО БЫ НАСТОЛЬКО НЕИНФОРМАТИВНЫМ, ЧТО ВООБЩЕ НЕ ПОПАЛО БЫ В УКАЗАТЕЛЬ! 
иДЕЯ УКАЗАТЕЛЯ~KWIC ПРИНАДЛЕЖИТ г.~п.~лАНУ 
[{\sl Amer. Documentation,\/} {\bf 11} (1960), 288--295]. пОЛНОСТЬЮ 
УКАЗАТЕЛЬ~KWIC ПРИВЕДЕН В РАБОТЕ 
[W.~W.~Youden, {\sl JACM,\/} {\bf 10} (1963), 583--646].

пРИ ПОДГОТОВКЕ УКАЗАТЕЛЯ~KWIC МОЖНО БЫЛО ИСПОЛЬЗОВАТЬ БИНАРНОЕ ДЕРЕВО 
ПОИСКА ДЛЯ ПРОВЕРКИ, НУЖНО ЛИ ВНОСИТЬ ТО ИЛИ ИНОЕ СЛОВО В УКАЗАТЕЛЬ. 
чАСТОТАМ ПОЯВЛЕНИЯ СЛОВ, ВКЛЮЧЕННЫХ В УКАЗАТЕЛЬ, СООТВЕТСТВУЮТ ВНЕШНИЕ 
УЗЛЫ ДЕРЕВА РИС.~15;
ТАК, В ЗАГОЛОВКАХ СТАТЕЙ {\sl JACM\/} ЗА~1954--1963~ГГ. ВСТРЕТИЛИСЬ РОВНО 
277~СЛОВ, РАСПОЛОЖЕННЫХ ПО АЛФАВИТУ МЕЖДУ "|PROBLEMS|" И~"|SOLUTION|".

нА РИС.~15 ИЗОБРАЖЕНО ОПТИМАЛЬНОЕ ДЕРЕВО, ПОЛУЧЕННОЕ С ПОМОЩЬЮ АЛГОРИТМА~K 
ПРИ~$n=35$. зНАЧЕНИЯ~$r[0,j]$, ВЫЧИСЛЕННЫЕ ДЛЯ $j=1$, $2$,~\dots, $35$, 
РАВНЫ (1, 1, 2, 3, 3, 3, 3, 8, 8, 8,  8, 8, 8, 11, 11,~\dots, 11, 21, 21, 
21, 21, 21, 21); ЗНАЧЕНИЯ~$r[i, 35]$ ДЛЯ~$i=0$, 1,~\dots, 34 РАВНЫ (21, 21,
~\dots, 21, 25, 25, 25, 25, 25, 25, 26, 26, 26, 30, 30, 30, 30, 30, 30, 30,
 33, 33, 33, 35, 35).

"пРОМЕЖУТОЧНЫЕ ЧАСТОТЫ"~$q_j$ ЗАМЕТНО ВЛИЯЮТ НА ОПТИМАЛЬНУЮ СТРУКТУРУ 
ДЕРЕВА; НА РИС.~16~(a) ПРИВЕДЕНО ОПТИМАЛЬНОЕ ДЕРЕВО, КОТОРОЕ ПОЛУЧИЛОСЬ БЫ 
ПРИ НУЛЕВЫХ~$q_j$. тАК ЖЕ ВАЖНЫ И ВНУТРЕННИЕ ЧАСТОТЫ~$p_i$; НА РИС.~16~(b) 
ИЗОБРАЖЕНО ОПТИМАЛЬНОЕ ДЕРЕВО ПРИ НУЛЕВЫХ~$p_i$. вЕРНЕМСЯ К ПОЛНОМУ 
НАБОРУ ЧАСТОТ. дЕРЕВО РИС.~15 ТРЕБУЕТ В СРЕДНЕМ ЛИШЬ $4.75$~СРАВНЕНИЯ, А 
ДЕРЕВЬЯ РИС.~16---СООТВЕТСТВЕННО~$5.29$ И~$5.32$. (пРЯМОЙ БИНАРНЫЙ ПОИСК В 
ДАННОМ СЛУЧАЕ БЫЛ БЫ ЛУЧШЕ ДЕРЕВЬЕВ РИС.~16.)

тАК КАК АЛГОРИТМ~K ТРЕБУЕТ $O(n^2)$~ВРЕМЕНИ И ПРОСТРАНСТВА, ЕГО 
ИСПОЛЬЗОВАНИЕ ПРИ БОЛЬШИХ~$n$ СТАНОВИТСЯ НЕРАЦИОНАЛЬНЫМ. кОНЕЧНО, В ЭТОМ 
СЛУЧАЕ МОЖНО БЫ ИСПОЛЬЗОВАТЬ ДРУГИЕ МЕТОДЫ ПОИСКА, И ДАЛЕЕ В ЭТОЙ ГЛАВЕ 
ОНИ БУДУТ ОБСУЖДАТЬСЯ. дАВАЙТЕ ПРЕДПОЛОЖИМ, ЧТО НУЖНО НАЙТИ ОПТИМАЛЬНОЕ 
ИЛИ ПОЧТИ ОПТИМАЛЬНОЕ ДЕРЕВО, ЕСЛИ $n$ ВЕЛИКО.

мЫ ВИДЕЛИ, ЧТО ИДЕЯ ВСТАВКИ КЛЮЧЕЙ В ПОРЯДКЕ УМЕНЬШЕНИЯ ЧАСТОТ В СРЕДНЕМ 
ВЕДЕТ К ДОВОЛЬНО ХОРОШИМ ДЕРЕВЬЯМ; НО ДЕРЕВО МОЖЕТ ПОЛУЧИТЬСЯ И ОЧЕНЬ 
ПЛОХИМ (СМ.~УПР.~20), ТАК КАК НЕ ИСПОЛЬЗУЮТСЯ ВЕСА~$q_j$. дРУГОЙ ПОДХОД 
СОСТОИТ В ВЫБОРЕ КОРНЯ~$k$ ТАКИМ ОБРАЗОМ, ЧТОБЫ МАКСИМАЛЬНЫЙ ВЕС 
ПОЛУЧАЮЩЕГОСЯ ПОДДЕРЕВА $\max(w(0, k-1), w(k, n))$ БЫЛ КАК МОЖНО МЕНЬШЕ. 
эТОТ ПОДХОД ТАКЖЕ НЕУДАЧЕН, ИБО В КАЧЕСТВЕ КОРНЯ МОЖЕТ БЫТЬ ВЫБРАН УЗЕЛ С 
ОЧЕНЬ МАЛЫМ~$p_k$. оДНАКО пОЛ бЭЙЕР ДОКАЗАЛ, ЧТО ПОЛУЧИВШЕЕСЯ ДЕРЕВО 
БУДЕТ ИМЕТЬ ВЗВЕШЕННУЮ ДЛИНУ ПУТИ, БЛИЗКУЮ К ОПТИМАЛЬНОЙ.

%%522

у.~э.~уОЛКЕР И~к.~к.~гОТЛИБ [Graph Theory and Computing (Academic Press, 
1972)] ПРЕДЛОЖИЛИ БОЛЕЕ УДОВЛЕТВОРИТЕЛЬНУЮ ПРОЦЕДУРУ, СОЧЕТАЮЩУЮ ОБА 
РАССМОТРЕННЫХ МЕТОДА: ПОПЫТАЙТЕСЬ УРАВНЯТЬ ЛЕВОСТОРОННИЕ И ПРАВОСТОРОННИЕ 
ВЕСА, НО БУДЬТЕ ГОТОВЫ ПЕРЕДВИНУТЬ КОРЕНЬ НА НЕСКОЛЬКО ШАГОВ ВПРАВО ИЛИ 
ВЛЕВО ДЛЯ НАХОЖДЕНИЯ УЗЛА С ОТНОСИТЕЛЬНО БОЛЬШИМ ВЕСОМ~$p_k$. рИСУНОК~17
\picture{рИС. 16. оПТИМАЛЬНЫЕ БИНАРНЫЕ ДЕРЕВЬЯ ПОИСКА, ОСНОВАННЫЕ НА 
ПОЛОВИНЕ ДАННЫХ РИС.~15, (a) НЕ УЧИТЫВАЮТСЯ ВНЕШНИЕ ЧАСТОТЫ; (b) НЕ 
УЧИТЫВАЮТСЯ ВНУТРЕННИЕ ЧАСТОТЫ.}
ПОКАЗЫВАЕТ, ПОЧЕМУ ЭТОТ МЕТОД РАЗУМЕН: ЕСЛИ МЫ ИЗОБРАЗИМ $c(0, k-1)+c(k, 
n)$ КАК ФУНКЦИЮ ОТ~$k$ ДЛЯ ДАННЫХ KWIC (СМ. РИС.~15), ТО УВИДИМ, ЧТО 
РЕЗУЛЬТАТ ОЧЕНЬ ЧУВСТВИТЕЛЕН К ВЕЛИЧИНЕ~$p_k$.

%%523

тАКОЙ МЕТОД "СВЕРХУ ВНИЗ" МОЖНО ИСПОЛЬЗОВАТЬ ПРИ БОЛЬШИХ~$n$ ДЛЯ ВЫБОРА 
КОРНЯ И ДЛЯ ОБРАБОТКИ ЛЕВЫХ И ПРАВЫХ ПОДДЕРЕВЬЕВ. еСЛИ ПОЛУЧИТСЯ 
ДОСТАТОЧНО МАЛЕНЬКОЕ ПОДДЕРЕВО, МОЖНО ПРИМЕНИТЬ АЛГОРИТМ~K. 
рЕЗУЛЬТИРУЮЩИЙ МЕТОД ДАЕТ ДОВОЛЬНО ХОРОШИЕ ДЕРЕВЬЯ (СОГЛАСНО СООБЩЕНИЯМ),
 НА 2--3\% ХУЖЕ ОПТИМУМА, А ТРЕБУЕТ ЛИШЬ $O (n)$~ЕДИНИЦ ПРОСТРАНСТВА И 
$O(n \log n)$~ЕДИНИЦ
\picture{рИС. 17. пОВЕДЕНИЕ ЦЕНЫ КАК ФУНКЦИИ КОРНЯ~$k$ (СЛЕВА ПО ОСИ  
ОРДИНАТ ОТЛОЖЕН МИНИМУМ СРЕДНЕЙ ЦЕНЫ).
}
ВРЕМЕНИ. нА САМОМ ДЕЛЕ м.~фРЕДМЭН ПОКАЗАЛ, ЧТО ДОСТАТОЧНО $O(n)$~ЕДИНИЦ 
ВРЕМЕНИ, ЕСЛИ ИСПОЛЬЗОВАТЬ ПОДХОДЯЩИЕ СТРУКТУРЫ ДАННЫХ [ACM. Symp. Theory 
of Comp., 7 (1975), 240--244].

\section *аЛГОРИТМ хУ-тАКЕРА. в СПЕЦИАЛЬНОМ СЛУЧАЕ, КОГДА ВСЕ~$p$ РАВНЫ 
НУЛЮ, т.~ч.~хУ И~э.~к.~тАКЕР ОТКРЫЛИ ЗАМЕЧАТЕЛЬНЫЙ СПОСОБ ПОСТРОЕНИЯ 
ОПТИМАЛЬНЫХ ДЕРЕВЬЕВ "СНИЗУ ВВЕРХ"; ПРИ ИСПОЛЬЗОВАНИИ ПОДХОДЯЩИХ 
СТРУКТУР ДАННЫХ ИХ МЕТОД ТРЕБУЕТ $O(n)$~ЕДИНИЦ ПРОСТРАНСТВА И~$O(n\log 
n)$~ЕДИНИЦ ВРЕМЕНИ И СТРОИТ ДЕРЕВО, НЕ БЛИЗКОЕ К ОПТИМАЛЬНОМУ, А 
\emph{ДЕЙСТВИТЕЛЬНО} ОПТИМАЛЬНОЕ. аЛГОРИТМ хУ-тАКЕРА МОЖНО ОПИСАТЬ ТАК.

\noindent $\bullet$~{\bf фаза 1.} кОМБИНАЦИЯ. нАЧНИТЕ С "РАБОЧЕЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ" ВЕСОВ, НАПИСАННЫХ ВНУТРИ \emph{ВНЕШНИХ} УЗЛОВ
\picture{ рИС. СТР. 523}
зАТЕМ РАЗ ЗА РАЗОМ КОМБИНИРУЙТЕ ДВА ВЕСА~$q_i$ И~$q_j$ ДЛЯ~$i<j$, ПОЛУЧАЯ 
ЕДИНСТВЕННЫЙ ВЕС~$q_i+q_j$, ИСКЛЮЧИТЕ $q_j$ ИЗ ПОСЛЕДОВАТЕЛЬНОСТИ И 
ЗАМЕНИТЕ УЗЕЛ, СОДЕРЖАЩИЙ~$q_i$, НА \emph{ВНУТРЕННИЙ} УЗЕЛ
\picture{ рИС. СТР. 523}
%%524
кОМБИНИРОВАТЬ НУЖНО ЕДИНСТВЕННУЮ ПАРУ ВЕСОВ~$(q_i, q_j)$, 
УДОВЛЕТВОРЯЮЩУЮ СЛЕДУЮЩИМ ПРАВИЛАМ:

{\medskip\narrower
\item{i)}~мЕЖДУ $q_i$ И~$q_j$ НЕТ ВНЕШНИХ УЗЛОВ. (эТО НАИБОЛЕЕ ВАЖНОЕ 
ПРАВИЛО, ОТЛИЧАЮЩЕЕ ДАННЫЙ АЛГОРИТМ ОТ МЕТОДА хАФФМЭНА.)

\item{ii)}~сУММА~$q_i+q_j$ МИНИМАЛЬНА СРЕДИ ВСЕХ~$(q_i, q_j)$,  
УДОВЛЕТВОРЯЮЩИХ ПРАВИЛУ~(i).

\item{iii)}~иНДЕКС~$i$ МИНИМАЛЕН СРЕДИ ВСЕХ~$(q_i, q_j)$, УДОВЛЕТВОРЯЮЩИХ 
ПРАВИЛАМ (i), (ii).

\item{iv)}~иНДЕКС~$j$ МИНИМАЛЕН СРЕДИ ВСЕХ~$(q_i, q_j)$, УДОВЛЕТВОРЯЮЩИХ 
ПРАВИЛАМ (i)--(iii).
\medskip}

\noindent $\bullet$~{\bf фаза 2.} пРИСВАИВАНИЕ УРОВНЕЙ. кОГДА ФАЗА~1 
ОКОНЧЕНА, В РАБОЧЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОСТАЕТСЯ ЕДИНСТВЕННЫЙ 
УЗЕЛ. пОМЕТЬТЕ ЕГО НОМЕРОМ УРОВНЯ~0. зАТЕМ ПРОДЕЛАЙТЕ ШАГИ ФАЗЫ~1 В 
ОБРАТНОМ ПОРЯДКЕ, ТАКИМ ОБРАЗОМ ПОМЕЧАЯ УЗЛЫ НОМЕРАМИ УРОВНЕЙ, ЧТО, ЕСЛИ 
(19)~ИМЕЕТ УРОВЕНЬ~$l$, УЗЛЫ~$q_i$ И~$q_j$, ПОРОДИВШИЕ~(19), ПОЛУЧАЮТ 
НОМЕР~$l+1$.

\noindent $\bullet$~{\bf фаза 3.} рЕКОМБИНАЦИЯ. тЕПЕРЬ У НАС ЕСТЬ 
ПОСЛЕДОВАТЕЛЬНОСТЬ ВНЕШНИХ УЗЛОВ И УРОВНЕЙ
\picture{рИС. СТР. 524}
вНУТРЕННИЕ УЗЛЫ, ИСПОЛЬЗОВАННЫЕ В ФАЗАХ~1 И~2, ТЕПЕРЬ ОТБРОСЬТЕ ЗА 
НЕНАДОБНОСТЬЮ---МЫ БУДЕМ СОЗДАВАТЬ НОВЫЕ УЗЛЫ ПУТЕМ КОМБИНАЦИИ ВЕСОВ~$(q_i, 
q_j)$ ПО СЛЕДУЮЩИМ НОВЫМ ПРАВИЛАМ:

{\medskip\narrower
\item{$\hbox{i}'$)}~уЗЛЫ, СОДЕРЖАЩИЕ~$q_i$ И~$q_j$, ДОЛЖНЫ БЫТЬ СОСЕДНИМИ В
РАБОЧЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ.

\item{$\hbox{ii}'$)}~оБА УРОВНЯ~$l_i$ И~$l_j$ ДОЛЖНЫ БЫТЬ МАКСИМАЛЬНЫМИ 
СРЕДИ ВСЕХ ОСТАЮЩИХСЯ.

\item{$\hbox{iii}'$')}~иНДЕКС~$i$ ДОЛЖЕН БЫТЬ МИНИМАЛЬНЫМ СРЕДИ ВСЕХ~$(q_i,
 q_j)$, УДОВЛЕТВОРЯЮЩИХ~($\hbox{i}'$) И~($\hbox{ii}'$).
\medskip}

\noindent нОВОМУ УЗЛУ~(19) ПРИСВАИВАЕТСЯ УРОВЕНЬ~$l_i-1$. бИНАРНОЕ 
ДЕРЕВО, ФОРМИРУЕМОЕ В ЭТОЙ ФАЗЕ, ИМЕЕТ МИНИМАЛЬНУЮ ВЗВЕШЕННУЮ ДЛИНУ ПУТИ 
СРЕДИ ВСЕХ БИНАРНЫХ ДЕРЕВЬЕВ, ВНЕШНИЕ УЗЛЫ КОТОРЫХ ИМЕЮТ ВЕСА (СЛЕВА 
НАПРАВО) $q_0$, $q_1$,~\dots, $q_n$.

рИСУНОК~18 ИЛЛЮСТРИРУЕТ РАБОТУ ЭТОГО АЛГОРИТМА; ВЕСАМИ ЯВЛЯЮТСЯ 
ОТНОСИТЕЛЬНЫЕ ЧАСТОТЫ БУКВ~\], |A|, |B|,~\dots, |Z| В АНГЛИЙСКОМ ТЕКСТЕ. 
в ТЕЧЕНИЕ ФАЗЫ~1 ПЕРВЫМ ФОРМИРУЕТСЯ УЗЕЛ~\node{6}, СОДЕРЖАЩИЙ ЧАСТОТЫ 
БУКВ~|J| И~|K|, ЗАТЕМ УЗЕЛ~\node{16} (КОМБИНИРУЕМ |P| И~|Q|), ЗАТЕМ
\picture{рИС. СТР. 524}
%% 525
\picture{рИС. 18.  аЛГОРИТМ хУ-тАКЕРА, ПРИМЕНЕННЫЙ К ДАННЫМ О ЧАСТОТАХ 
БУКВ; ФАЗЫ~1 И~2.}
%% 526
В ЭТОТ МОМЕНТ МЫ ИМЕЕМ РАБОЧУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ
\picture{рИС. СТР. 526}
пРАВИЛО~(i) ПОЗВОЛЯЕТ КОМБИНИРОВАТЬ НЕСМЕЖНЫЕ ВЕСА, ТОЛЬКО ЕСЛИ ОНИ 
РАЗДЕЛЕНЫ ВНУТРЕННИМИ УЗЛАМИ; ТАК ЧТО МОЖНО СКОМБИНИРОВАТЬ $57+57$, 
ЗАТЕМ $63 +51$, ЗАТЕМ $58+64$ И~Т.~Д.

нОМЕРА УРОВНЕЙ, ПРИСВОЕННЫЕ ВО ВРЕМЯ ФАЗЫ~2, ИЗОБРАЖЕНЫ НА РИС.~18 СПРАВА 
ОТ КАЖДОГО УЗЛА. в РЕЗУЛЬТАТЕ РЕКОМБИНАЦИИ (ФАЗА~3) МЫ ПОЛУЧАЕМ ДЕРЕВО, 
ПОКАЗАННОЕ НА РИС.~19; ЗАМЕТЬТЕ, ЧТО ДЕРЕВЬЯ РИС.~18 И~19 СУЩЕСТВЕННО 
РАЗЛИЧНЫ: РИС.~18 НЕ СОХРАНЯЕТ УПОРЯДОЧЕННОСТИ СЛЕВА НАПРАВО. нО ЦЕНЫ У 
ЭТИХ ДЕРЕВЬЕВ ОДИНАКОВЫ, ТАК КАК ВНЕШНИЕ УЗЛЫ РАСПОЛОЖЕНЫ НА ОДИНАКОВЫХ УРОВНЯХ.

рАССМОТРИМ ПРОСТОЙ ПРИМЕР, ГДЕ ВЕСА РАВНЫ 4, 3, 2, 4; ЛЕГКО ПОКАЗАТЬ, ЧТО 
ЕДИНСТВЕННЫМ ОПТИМАЛЬНЫМ ДЕРЕВОМ ЯВЛЯЕТСЯ
\picture{рИС. СТР. 526}
нА ЭТОМ ПРИМЕРЕ ВИДНО, ЧТО В ОПТИМАЛЬНОМ ДЕРЕВЕ ДВА НАИМЕНЬШИХ ВЕСА~2 
И~3 \emph{НЕ} ВСЕГДА СЛЕДУЕТ КОМБИНИРОВАТЬ В ОДНО ОПТИМАЛЬНОЕ ДЕРЕВО, 
ДАЖЕ ЕСЛИ ОНИ ПРИПИСАНЫ СМЕЖНЫМ УЗЛАМ;
НУЖНА НЕКОТОРАЯ РЕКОМБИНАЦИОННАЯ ФАЗА.

в НАШЕЙ КНИГЕ НЕ ПРИВОДИТСЯ ДОКАЗАТЕЛЬСТВО СПРАВЕДЛИВОСТИ АЛГОРИТМА 
хУ-тАКЕРА; ПРОСТЫЕ ДОКАЗАТЕЛЬСТВА НЕ ИЗВЕСТНЫ, И ОЧЕНЬ ВЕРОЯТНО, ЧТО ОНИ 
НИКОГДА НЕ БУДУТ НАЙДЕНЫ! чТОБЫ ПРОИЛЛЮСТРИРОВАТЬ ВНУТРЕННЕ ПРИСУЩУЮ 
ДАННОЙ СИТУАЦИИ СЛОЖНОСТЬ, ЗАМЕТИМ, ЧТО ФАЗА~3 ДОЛЖНА СКОМБИНИРОВАТЬ ВСЕ 
УЗЛЫ В ОДНО ДЕРЕВО, НО ВОЗМОЖНОСТЬ ЭТОГО НЕ ОЧЕВИДНА. нАПРИМЕР, 
 ПРЕДПОЛОЖИМ, ЧТО ФАЗЫ~1 И~2 ПРИВЕЛИ К ДЕРЕВУ
\picture{рИС. СТР. 526}
%%527
\picture{рИС. 19. аЛГОРИТМ хУ-тАКЕРА, ПРИМЕНЕННЫЙ К ДАННЫМ О ЧАСТОТАХ 
БУКВ; ФАЗА 3.}
%% 528
(Т.~Е. БЫЛИ ПОЛУЧЕНЫ УЗЛЫ \node{$a$}, \node{$b$}, \node{$c$}, \node{$d$}, 
\node{$e$} В УКАЗАННОМ ПОРЯДКЕ); ЭТО СОГЛАСУЕТСЯ С ПРАВИЛОМ~(i). зАТЕМ 
ПОСЛЕ ФОРМИРОВАНИЯ УЗЛОВ
\picture{рИС. СТР. 528}
МЫ НЕ СМОЖЕМ ПРОДОЛЖИТЬ ФАЗУ~3, ТАК КАК УЗЛЫ УРОВНЯ~3 НЕСМЕЖНЫЕ! 
пРАВИЛО~(i) САМО ПО СЕБЕ НЕ ГАРАНТИРУЕТ БЛАГОПОЛУЧНОГО ЗАВЕРШЕНИЯ ФАЗЫ~3,
 И НЕОБХОДИМО ДОКАЗЫВАТЬ, ЧТО КОНФИГУРАЦИЯ, ПОДОБНАЯ~(22), 
\emph{НИКОГДА} НЕ ПОЛУЧАЕТСЯ НА ФАЗЕ~1.

пРИ РЕАЛИЗАЦИИ АЛГОРИТМА хУ-тАКЕРА МОЖНО ХРАНИТЬ ПРИОРИТЕТНЫЕ ОЧЕРЕДИ ДЛЯ 
МНОЖЕСТВА ВЕСОВ В УЗЛАХ, МЕЖДУ КОТОРЫМИ НЕТ ВНЕШНИХ УЗЛОВ. нАПРИМЕР, 
(20) МОЖНО БЫЛО БЫ ПРЕДСТАВИТЬ ПРИОРИТЕТНЫМИ ОЧЕРЕДЯМИ, СОДЕРЖАЩИМИ 
СООТВЕТСТВЕННО 
\picture{рИС. СТР. 528}
И ИНФОРМАЦИЕЙ О ТОМ, КАКИЕ ИЗ УЗЛОВ ВНЕШНИЕ, А ТАКЖЕ УКАЗАНИЕМ НА 
ПОРЯДОК СЛЕВА НАПРАВО (ЭТО НУЖНО ДЛЯ ПРИМЕНЕНИЯ ПРАВИЛ~(iii) И~(iv)). в 
ДРУГОЙ, "УПРАВЛЯЮЩЕЙ" ПРИОРИТЕТНОЙ ОЧЕРЕДИ МОЖНО ЗАПОМИНАТЬ СУММЫ ДВУХ 
НАИМЕНЬШИХ ЭЛЕМЕНТОВ ОЧЕРЕДЕЙ. сОЗДАНИЕ НОВОГО УЗЛА~$57+57$ ВЫЗЫВАЕТ 
СЛИЯНИЕ ТРЕХ ОЧЕРЕДЕЙ. еСЛИ ПРИОРИТЕТНЫЕ ОЧЕРЕДИ ПРЕДСТАВЛЕНЫ 
ЛЕВОСТОРОННИМИ ДЕРЕВЬЯМИ (СМ. П.~5.2.3), ТО КАЖДЫЙ ШАГ ФАЗЫ~1 ТРЕБУЕТ НЕ 
БОЛЕЕ $O(\log n)$~ОПЕРАЦИЙ; ЗНАЧИТ, ПРИ~$n\to\infty$ ДОСТАТОЧНО $O(n \log 
n)$~ОПЕРАЦИЙ. кОНЕЧНО, ПРИ НЕБОЛЬШИХ~$n$ БОЛЕЕ ЭФФЕКТИВНЫМ БУДЕТ 
ОТНОСИТЕЛЬНО БОЛЕЕ ПРЯМОЛИНЕЙНЫЙ $O(n^2)\hbox{-СПОСОБ}$ РЕАЛИЗАЦИИ.

оПТИМАЛЬНОЕ БИНАРНОЕ ДЕРЕВО РИС.~19 ПОЛЕЗНО НЕ ТОЛЬКО ДЛЯ ПОИСКА, НО И ДЛЯ 
ТЕОРИИ КОДИРОВАНИЯ: ИСПОЛЬЗУЯ 0 ДЛЯ ОБОЗНАЧЕНИЯ ЛЕВОЙ ВЕТВИ ДЕРЕВА И~1 ДЛЯ 
ПРАВОЙ, ПОЛУЧАЕМ СЛЕДУЮЩИЕ КОДЫ РАЗЛИЧНОЙ ДЛИНЫ:
$$
\vcenter{
\halign{
|#| \bskip & $#$\hfill \bskip\bskip\bskip &&|#| \bskip & $#$\hfill \bskip\bskip\bskip\cr
\] & 000    & I & 1000    & R & 11001 \cr
A  & 0010   & J & 1001000 & S & 1101 \cr
в  & 001100 & K & 1001001 & T &  1110 \cr
C  & 001101 & L & 100101  & U & 111100\cr
D  & 00111  & M & 10011   & V &  111101 \cr
E  & 010    & N & 1010    & W & 111110 \cr
F  & 01100  & O & 1011    & X & 11111100\cr
G  & 01101  & P & 110000  & Y & 11111101\cr
H  & 0111   & Q & 110001  & Z & 1111111\cr
}
}
\eqno(24)
$$
%%529
тАКИМ ОБРАЗОМ, СООБЩЕНИЕ ВРОДЕ "|RIGHT ON|" МОЖНО ЗАКОДИРОВАТЬ ЦЕПОЧКОЙ
$$
|110011000011010111111000010111010|.
$$
зАМЕТИМ, ЧТО ПЕРЕМЕННАЯ ДЛИНА КОДОВ НЕ ЗАТРУДНЯЕТ РАСШИФРОВКУ СЛЕВА 
НАПРАВО, ТАК КАК СТРУКТУРА ДЕРЕВА ПОДСКАЗЫВАЕТ, КОГДА КОНЧАЕТСЯ КОД ОДНОЙ 
БУКВЫ И НАЧИНАЕТСЯ ДРУГОЙ. тАКОЙ МЕТОД КОДИРОВАНИЯ СОХРАНЯЕТ АЛФАВИТНЫЙ 
ПОРЯДОК И ИСПОЛЬЗУЕТ ДЛЯ КОДИРОВАНИЯ ОДНОЙ БУКВЫ В СРЕДНЕМ ОКОЛО 4.2~БИТОВ.
 эТОТ КОД МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ УПЛОТНЕНИЯ ФАЙЛОВ ДАННЫХ БЕЗ НАРУШЕНИЯ 
ЛЕКСИКОГРАФИЧЕСКОГО ПОРЯДКА БУКВЕННОЙ ИНФОРМАЦИИ. (чИСЛО~$4.2$ 
МИНИМАЛЬНО ДЛЯ КОДИРОВАНИЯ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ, ХОТЯ ЕГО МОЖНО 
УМЕНЬШИТЬ ДО $4.1$~БИТОВ НА БУКВУ, ЕСЛИ ОТКАЗАТЬСЯ ОТ СОХРАНЕНИЯ 
АЛФАВИТНОГО ПОРЯДКА. уМЕНЬШЕНИЕ С СОХРАНЕНИЕМ АЛФАВИТНОГО ПОРЯДКА 
ДОСТИГАЕТСЯ КОДИРОВАНИЕМ НЕ ОТДЕЛЬНЫХ БУКВ, А ПАР БУКВ.)

иНТЕРЕСНАЯ АСИМПТОТИЧЕСКАЯ ОЦЕНКА МИНИМАЛЬНОЙ ВЗВЕШЕННОЙ ДЛИНЫ ПУТИ 
ДЕРЕВЬЕВ ПОИСКА ВЫВЕДЕНА э.~н.~гИЛБЕРТОМ И~э.~ф.~мУРОМ:

\proclaim тЕОРЕМА G. еСЛИ $p_1=p_2=\cdots=p_n=0$, ТО ВЗВЕШЕННАЯ ДЛИНА ПУТИ 
ОПТИМАЛЬНОГО БИНАРНОГО ДЕРЕВА ПОИСКА ЗАКЛЮЧЕНА МЕЖДУ
$$
\sum_{0\le i \le n} q_i \log_2 (Q/q_i) \hbox{\sl И\/} 
2Q+\sum_{0\le i \le n} q_i \log_2 (Q/q_i),
$$
ГДЕ $Q= 2\sum_{0\le i\le n} q_i$.

\proof дЛЯ ПОЛУЧЕНИЯ НИЖНЕЙ ОЦЕНКИ ИСПОЛЬЗУЕМ ИНДУКЦИЮ ПО~$n$. пРИ $n>0$ 
ВЗВЕШЕННАЯ ДЛИНА ВНЕШНЕГО ПУТИ НЕ МЕНЬШЕ
$$
Q+\sum_{0\le i <k} q_i\log_2(Q_1/q_i)
+\sum_{k\le i\le n} q_i\log_2((Q-Q_1)/q_i)\ge
\sum_{0\le i\le n} q_i \log_2 (Q/q_i)+f(Q_1)
$$
ДЛЯ НЕКОТОРОГО $k$, ГДЕ
$$
Q_1=\sum_{0\le i<k} q_i
$$
 И
$$
f(Q_1)=Q+Q_1\log_2Q_1+(Q-Q_1)\log_2(Q-Q_1)-Q\log_2Q.
$$
фУНКЦИЯ~$f(Q_1)$ НЕОТРИЦАТЕЛЬНА И ПРИНИМАЕТ НАИМЕНЬШЕЕ ЗНАЧЕНИЕ~0 
ПРИ~$Q_1={1\over 2}Q$.

дЛЯ ПОЛУЧЕНИЯ ВЕРХНЕЙ ГРАНИЦЫ МОЖЕМ СЧИТАТЬ, ЧТО $Q=1$. пУСТЬ $e_0$,~\dots,
 $e_n$---ЦЕЛЫЕ ЧИСЛА, ТАКИЕ, ЧТО $2^{-e_i}\le q_i < 2^{1-e_i}$,
%% 530
$0\le i\le n$. пОСТРОИМ КОДЫ $C_i$ ИЗ НУЛЕЙ И ЕДИНИЦ, ИСПОЛЬЗУЯ $e_i+1$ 
СТАРШИХ ЗНАЧАЩИХ ЦИФР 
ДРОБИ~$\sum_{0\le k<i} q_k+{1\over2}q_i$, ВЫРАЖЕННОЙ В ДВОИЧНОЙ СИСТЕМЕ. в 
УПР.~35 ДОКАЗЫВАЕТСЯ, ЧТО $C_i$ НЕ ЯВЛЯЕТСЯ НАЧАЛЬНОЙ ПОДЦЕПОЧКОЙ~$C_j$ 
ПРИ $i\ne j$; ОТСЮДА СЛЕДУЕТ, ЧТО МЫ МОЖЕМ ПОСТРОИТЬ БИНАРНОЕ ДЕРЕВО 
ПОИСКА, СООТВЕТСТВУЮЩЕЕ ЭТИМ КОДАМ. вОЗВРАЩАЯСЬ К ПРИМЕРУ РИС.~19, МОЖНО 
ПОКАЗАТЬ, ЧТО $C_0=0001$, $C_1=00110$, $C_2=01000001$, $C_3=0100011$ И 
Т.~Д.; ДЕРЕВО НАЧИНАЕТСЯ С
\picture{рИС. СТР. 530}
(иЗБЫТОЧНЫЕ БИТЫ В КОНЦЕ КОДОВ ЧАСТО МОЖНО ОТБРОСИТЬ.) вЗВЕШЕННАЯ ДЛИНА 
ПУТИ БИНАРНОГО ДЕРЕВА, ПОСТРОЕННОГО ТАКОЙ ПРОЦЕДУРОЙ, БУДЕТ
$$
\le \sum_{0\le i\le n} (e_i+1)q_i
<\sum_{0\le i\le n}q_i(2+\log_2(1/q_i)).\endmark
$$

мЕТОДОМ, ИСПОЛЬЗОВАННЫМ В ПЕРВОЙ ЧАСТИ ДОКАЗАТЕЛЬСТВА, ЛЕГКО УСТАНОВИТЬ, 
ЧТО ВЗВЕШЕННАЯ ДЛИНА ПУТИ \emph{ЛЮБОГО} БИНАРНОГО
ДЕРЕВА НЕ МЕНЬШЕ, ЧЕМ  $\sum_{0\le i\le n} q_i\log_2 (Q/q_i)$, НЕЗАВИСИМО 
ОТ ПОРЯДКА ВЕСОВ СЛЕВА НАПРАВО. (эТОТ ФУНДАМЕНТАЛЬНЫЙ 
РЕЗУЛЬТАТ ПРИНАДЛЕЖИТ кЛОДУ шЕННОНУ.) тАКИМ ОБРАЗОМ, СОХРАНЕНИЕ ПОРЯДКА 
ВЕСОВ СЛЕВА НАПРАВО УВЕЛИЧИВАЕТ ЦЕНУ ОПТИМАЛЬНОГО ДЕРЕВА НЕ БОЛЬШЕ, ЧЕМ НА 
ЦЕНУ ДВУХ ДОПОЛНИТЕЛЬНЫХ УРОВНЕЙ, Т.~Е. НА УДВОЕННУЮ СУММУ ВЕСОВ.

\section иСТОРИЯ И БИБЛИОГРАФИЯ. рАССМОТРЕННЫЕ МЕТОДЫ ПОИСКА ПО ДЕРЕВУ 
БЫЛИ ОТКРЫТЫ НЕЗАВИСИМО НЕСКОЛЬКИМИ ИССЛЕДОВАТЕЛЯМИ В НАЧАЛЕ 50-Х ГОДОВ. в 
НЕОПУБЛИКОВАННОМ ДОКУМЕНТЕ, ДАТИРОВАННОМ АВГУСТОМ 1952~Г., а.~и.~дУМИ 
ОПИСАЛ ВСТАВКИ В ДЕРЕВО В ПРОСТЕЙШЕМ ВИДЕ:

%%531
\noindent
"пУСТЬ ИМЕЕТСЯ БАРАБАН, НА КОТОРОМ ЗАПИСАНО $2^n$~ЭЛЕМЕНТОВ, И КАЖДЫЙ ИЗ 
НИХ ИМЕЕТ БИНАРНЫЙ АДРЕС. пРИДЕРЖИВАЙТЕСЬ ТАКОЙ ПРОГРАММЫ:
\enumerate
\li пРОЧИТАЙТЕ ПЕРВЫЙ ЭЛЕМЕНТ И ПОМЕСТИТЕ ЕГО ПО АДРЕСУ $2^{n-1}$, Т.~Е. В 
СЕРЕДИНУ МАССИВА ПАМЯТИ.

\li пРОЧИТАЙТЕ СЛЕДУЮЩИЙ ЭЛЕМЕНТ. сРАВНИТЕ ЕГО С ПЕРВЫМ.

\li еСЛИ ОН БОЛЬШЕ, ПОМЕСТИТЕ ЕГО ПО АДРЕСУ~$2^{n-1}+2^{n-2}$.\goodbreak
еСЛИ ЖЕ ОН МЕНЬШЕ, ПОМЕСТИТЕ ПО АДРЕСУ~$2^{n-2}$.~\dots"
\enumend

дРУГАЯ РАННЯЯ ФОРМА ВСТАВКИ В ДЕРЕВО БЫЛА ВВЕДЕНА д.~дЖ.~уИЛЕРОМ; ОН, В 
СУЩНОСТИ, ДОПУСКАЛ МНОГОПУТЕВЫЕ РАЗВЕТВЛЕНИЯ, ПОДОБНЫЕ ТЕМ, КОТОРЫЕ 
БУДУТ ОБСУЖДАТЬСЯ В П. 6.2.4;
МЕТОД ВСТАВКИ В БИНАРНОЕ ДЕРЕВО БЫЛ ТАКЖЕ НЕЗАВИСИМО ПРИДУМАН 
к.~м.~бЕРНЕСОМ-лИ [{\sl Comp. J.,\/} {\bf 2} (1959), 5].

пЕРВЫЕ ОПУБЛИКОВАННЫЕ ОПИСАНИЯ ВСТАВКИ В ДЕРЕВО ПРИНАДЛЕЖАТ п.~ф.~уИНДЛИ 
[{\sl Comp. J.,\/} {\bf 3} (1960), 84--88], э.~д.~бУТУ И~э.~кОЛИНУ [{\sl 
Information and Control,\/} {\bf 3} (1960), 327--334] И~т.~н.~хИББАРДУ 
[{\sl JACM,\/} {\bf 9} (1962), 13--28]. вЕРОЯТНО, ВСЕ АВТОРЫ РАЗВИВАЛИ 
ЭТОТ МЕТОД НЕЗАВИСИМО, И ИХ ДОКАЗАТЕЛЬСТВА ФОРМУЛЫ~(6) СРЕДНЕГО ЧИСЛА 
СРАВНЕНИЙ НЕСКОЛЬКО ОТЛИЧАЮТСЯ ДРУГ ОТ ДРУГА. в ПОСЛЕДУЮЩИХ РАБОТАХ ОНИ 
ПРОДОЛЖАЛИ ИССЛЕДОВАТЬ РАЗЛИЧНЫЕ АСПЕКТЫ ЭТОГО АЛГОРИТМА: уИНДЛИ ПОДРОБНО 
РАЗОБРАЛ СОРТИРОВКУ ВСТАВКОЙ В ДЕРЕВО, бУТ И~кОЛИН ОБСУЖДАЛИ 
ЭФФЕКТ ПРЕДВАРИТЕЛЬНОГО ПОСТРОЕНИЯ ИЗ ПЕРВЫХ $2^n-1$~ЭЛЕМЕНТОВ ИДЕАЛЬНО 
СБАЛАНСИРОВАННОГО ДЕРЕВА (СМ. УПР.~4), хИББАРД ПРЕДЛОЖИЛ ИДЕЮ УДАЛЕНИЯ И 
ВЫЯВИЛ СВЯЗЬ МЕЖДУ АНАЛИЗОМ ВСТАВКИ В ДЕРЕВО И АНАЛИЗОМ БЫСТРОЙ СОРТИРОВКИ.

иДЕЯ \emph{ОПТИМАЛЬНЫХ} БИНАРНЫХ ДЕРЕВЬЕВ ПОИСКА БЫЛА ВПЕРВЫЕ РАЗВИТА ДЛЯ 
ЧАСТНОГО СЛУЧАЯ $p_1=\cdots=p_n=0$ В СВЯЗИ С БИНАРНЫМ КОДИРОВАНИЕМ БУКВ. 
в ОЧЕНЬ ИНТЕРЕСНОЙ СТАТЬЕ э.~гИЛБЕРТА И~э.~мУРА 
[{\sl Bell System Tech.~J.,\/} {\bf 38} (1959), 933--968] 
ОБСУЖДАЛАСЬ ЭТА ПРОБЛЕМА И ЕЕ СВЯЗЬ С 
ДРУГИМИ ЗАДАЧАМИ КОДИРОВАНИЯ. гИЛБЕРТ И~мУР ОТМЕТИЛИ, ЧТО ОПТИМАЛЬНОЕ 
ДЕРЕВО МОЖНО ПОСТРОИТЬ ЗА $O(n^3)$~ШАГОВ, ИСПОЛЬЗУЯ МЕТОД, ПОДОБНЫЙ 
АЛГОРИТМУ~K, НО БЕЗ СООТНОШЕНИЯ~(17). к.~э.~аЙВЕРСОН [A Programming 
Language (Wiley, 1962), 142--144] НЕЗАВИСИМО РАССМОТРЕЛ 
\emph{ДРУГОЙ} СЛУЧАЙ, КОГДА ВСЕ~$q$ РАВНЫ~0. оН ПРЕДПОЛОЖИЛ, ЧТО ДЕРЕВО 
БУДЕТ ОПТИМАЛЬНЫМ, ЕСЛИ КОРЕНЬ ВЫБРАТЬ ТАК, ЧТОБЫ КАК МОЖНО ЛУЧШЕ УРАВНЯТЬ 
ВЕРОЯТНОСТИ ЛЕВОГО И ПРАВОГО ПОДДЕРЕВЬЕВ; МЫ ВИДЕЛИ, ЧТО, К СОЖАЛЕНИЮ, ЭТА 
ИДЕЯ НЕ РАБОТАЕТ. д.~э.~кНУТ [{\sl Acta Informatica,\/} {\bf 1} (1971), 
14--25, 270] ВПОСЛЕДСТВИИ РАССМОТРЕЛ СЛУЧАЙ ЛЮБЫХ ВЕСОВ $p$ И~$q$ И 
ДОКАЗАЛ, ЧТО АЛГОРИТМ МОЖЕТ БЫТЬ СВЕДЕН К $O(n^2)$~ШАГАМ; ОН ТАКЖЕ ПРИВЕЛ 
ПРИМЕР ПРИМЕНЕНИЯ РАССМОТРЕННЫХ МЕТОДОВ К КОМПИЛЯТОРУ, ГДЕ КЛЮЧАМИ В 
ДЕРЕВЕ ЯВЛЯЮТСЯ "РЕЗЕРВИРОВАННЫЕ СЛОВА" АЛГОЛОПОДОБНОГО ЯЗЫКА. 
т.~ч.~хУ НЕСКОЛЬКО ЛЕТ ЗАНИМАЛСЯ СВОИМ СОБСТВЕННЫМ АЛГОРИТМОМ ДЛЯ
%%532
СЛУЧАЯ~$p=0$; ИЗ-ЗА СЛОЖНОСТИ ЗАДАЧИ БЫЛО ТРУДНО НАЙТИ 
СТРОГОЕ ДОКАЗАТЕЛЬСТВО СПРАВЕДЛИВОСТИ ЭТОГО АЛГОРИТМА, НО В КОНЦЕ КОНЦОВ В 
1969~Г. т.~ч.~хУ И~э.~к.~тАКЕР СПРАВИЛИСЬ С ЭТИМ. 
[{\sl SIAM J.  Applied Math.,\/} {\bf 21} (1971), 514--532.]

\excercises
\ex[15] аЛГОРИТМ~T БЫЛ СФОРМУЛИРОВАН ЛИШЬ ДЛЯ НЕПУСТЫХ ДЕРЕВЬЕВ. кАКИЕ 
НУЖНО ВНЕСТИ ИЗМЕНЕНИЯ, ЧТОБЫ ОН ОБРАБАТЫВАЛ И ПУСТЫЕ ДЕРЕВЬЯ?

\ex[20] иЗМЕНИТЕ АЛГОРИТМ~T ТАК, ЧТОБЫ ОН РАБОТАЛ С \emph{ПРАВОПРОШИТЫМИ} 
ДЕРЕВЬЯМИ (СР.~С П.~2.3.1; ПО ТАКИМ ДЕРЕВЬЯМ ПРОЩЕ СОВЕРШАТЬ СИММЕТРИЧНЫЙ ОБХОД).

\rex[20] в \S~6.1 МЫ ВИДЕЛИ, ЧТО НЕБОЛЬШОЕ ИЗМЕНЕНИЕ АЛГОРИТМА 
ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА~6.1S ДЕЛАЕТ ЕГО БЫСТРЕЕ (АЛГОРИТМ~6.1Q). мОЖНО ЛИ 
ПОДОБНУЮ ХИТРОСТЬ ИСПОЛЬЗОВАТЬ ДЛЯ УСКОРЕНИЯ РАБОТЫ АЛГОРИТМА~T?

\ex[м24] (э.~д.~бУТ И~э.~кОЛИН.) дАНЫ $N$~КЛЮЧЕЙ В СЛУЧАЙНОМ ПОРЯДКЕ;
ПРЕДПОЛОЖИМ, ЧТО МЫ ИСПОЛЬЗУЕМ ПЕРВЫЕ~$2^n-1$ ДЛЯ ПОСТРОЕНИЯ 
ИДЕАЛЬНО СБАЛАНСИРОВАННОГО ДЕРЕВА, ПОМЕЩАЯ $2^k$~КЛЮЧЕЙ НА УРОВЕНЬ~$k$, 
$0\le k<n$. зАТЕМ МЫ ПРИМЕНЯЕМ АЛГОРИТМ~T ДЛЯ ВСТАВКИ ОСТАВШИХСЯ КЛЮЧЕЙ. 
нАЙДИТЕ СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ ПРИ УДАЧНОМ ПОИСКЕ. [\emph{уКАЗАНИЕ:} 
ВИДОИЗМЕНИТЬ~(2).]
 
\rex[м25] нАЗВАНИЯ |CAPRICORN|, |AQUARIUS| И~Т.~Д. МОЖНО 
УПОРЯДОЧИТЬ $11!=39916800$~СПОСОБАМИ ДЛЯ ВСТАВКИ В БИНАРНОЕ ДЕРЕВО ПОИСКА. 
(a) сКОЛЬКО ТАКИХ ПЕРЕСТАНОВОК ПРИВЕДУТ К РИС.~10? (b)~сКОЛЬКО 
ПЕРЕСТАНОВОК ПРИВЕДУТ К ВЫРОЖДЕННОМУ ДЕРЕВУ, Т.~Е. ВО ВСЕХ УЗЛАХ |LLINK| 
ИЛИ~|RLINK| БУДУТ РАВНЯТЬСЯ~$\NULL$?

\ex[м26] оБОЗНАЧИМ ЧЕРЕЗ $P_{nk}$ КОЛИЧЕСТВО ПЕРЕСТАНОВОК $a_1$ 
$a_2$~\dots $a_n$ МНОЖЕСТВА $\{\, 1, 2,~\dots, n\,\}$, ТАКИХ, ЧТО, ЕСЛИ 
АЛГОРИТМ~T ИСПОЛЬЗУЕТСЯ ДЛЯ ПОСЛЕДОВАТЕЛЬНОЙ ВСТАВКИ $a_1$, $a_2$,~\dots, 
$a_n$ В ПЕРВОНАЧАЛЬНО ПУСТОЕ ДЕРЕВО, РОВНО $k$~СРАВНЕНИЙ ПРОИЗВОДИТСЯ ПРИ 
ВСТАВКЕ~$a_n$. [в ЭТОЙ ЗАДАЧЕ МЫ ПРЕНЕБРЕЖЕМ СРАВНЕНИЯМИ, ПРОИЗВОДИМЫМИ 
ПРИ ВСТАВКЕ $a_1$,~\dots, $a_{n-1}$. в ПРИНЯТЫХ В ТЕКСТЕ ОБОЗНАЧЕНИЯХ 
$C'_{n-1}=\left(\sum kP_{nk}\right)/n!$, ТАК КАК ЭТО ЕСТЬ СРЕДНЕЕ ЧИСЛО 
СРАВНЕНИЙ, КОТОРЫЕ ПРОИЗВОДЯТСЯ ПРИ НЕУДАЧНОМ ПОИСКЕ ПО ДЕРЕВУ ИЗ 
$n-1$~ЭЛЕМЕНТОВ.]

{\medskip\narrower
\item{a)}~дОКАЖИТЕ, ЧТО $P_{n+1,k}=2P_{n,k-1}+(n-1)P_{n,k}$. 
[\emph{уКАЗАНИЕ:} ПОСМОТРИТЕ, ОКАЗЫВАЕТСЯ ЛИ $a_{n+1}$ НИЖЕ~$a_n$.]

\item{b)}~нАЙДИТЕ ПРОСТУЮ ФОРМУЛУ ДЛЯ ПРОИЗВОДЯЩЕЙ 
ФУНКЦИИ~$G_n(z)=\sum_k P_{nk}z^k$ И ИСПОЛЬЗУЙТЕ ЕЕ ДЛЯ ВЫРАЖЕНИЯ $P_{nk}$ 
ЧЕРЕЗ ЧИСЛА сТИРЛИНГА.

\item{c)}~чЕМУ РАВНА \emph{ДИСПЕРСИЯ}~$C'_{n-1}$?

\medskip}

\ex[M30] (с.~р.~аРОРА И~у.~т.~дЭНТ.) кАКОЕ СРЕДНЕЕ ЧИСЛО 
СРАВНЕНИИ ПОТРЕБУЕТСЯ ДЛЯ ОТЫСКАНИЯ $m\hbox{-ГО}$ ПО ВЕЛИЧИНЕ ЭЛЕМЕНТА 
ПОСЛЕ ВСТАВКИ В ПЕРВОНАЧАЛЬНО ПУСТОЕ ДЕРЕВО $n$~ЭЛЕМЕНТОВ В СЛУЧАЙНОМ ПОРЯДКЕ?

\ex[м38] пУСТЬ $p(n, k)$ ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО ПОЛНАЯ ДЛИНА 
ВНУТРЕННЕГО ПУТИ ДЕРЕВА, ПОСТРОЕННОГО АЛГОРИТМОМ~T ИЗ $n$ СЛУЧАЙНО 
УПОРЯДОЧЕННЫХ КЛЮЧЕЙ, РАВНА~$k$ (ДЛИНА ВНУТРЕННЕГО ПУТИ ДЕРЕВА РАВНА ЧИСЛУ 
СРАВНЕНИЙ, ПРОИЗВОДИМЫХ ПРИ СОРТИРОВКЕ ВСТАВКОЙ В ДЕРЕВО ПО МЕРЕ ЕГО ПОСТРОЕНИЯ).
(А)~нАЙДИТЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ, ОПРЕДЕЛЯЮЩЕЕ СООТВЕТСТВУЮЩУЮ 
ПРОИЗВОДЯЩУЮ ФУНКЦИЮ. (b)~вЫЧИСЛИТЕ ДИСПЕРСИЮ ЭТОГО РАСПРЕДЕЛЕНИЯ. 
[зДЕСЬ МОГУТ БЫТЬ ПОЛЕЗНЫ НЕКОТОРЫЕ УПРАЖНЕНИЯ П.~1.2.7!]

\ex[41] мЫ ДОКАЗАЛИ, ЧТО ПОИСК С ВСТАВКОЙ ПО ДЕРЕВУ ТРЕБУЕТ ЛИШЬ ОКОЛО 
$2\ln N$~СРАВНЕНИЙ, ЕСЛИ КЛЮЧИ ВСТАВЛЯЮТСЯ В СЛУЧАЙНОМ ПОРЯДКЕ; НО В 
ДЕЙСТВИТЕЛЬНОСТИ ПОРЯДОК МОЖЕТ НЕ БЫТЬ СЛУЧАЙНЫМ. иССЛЕДУЙТЕ ЭМПИРИЧЕСКИ,
НАСКОЛЬКО ХОРОШО ВСТАВКА В ДЕРЕВО ОБСЛУЖИВАЕТ ТАБЛИЦЫ 
СИМВОЛОВ КОМПИЛЯТОРА И/ИЛИ ЗАГРУЗЧИКА. дАДУТ ЛИ ИДЕНТИФИКАТОРЫ ТИПИЧНОЙ 
БОЛЬШОЙ ПРОГРАММЫ ДОСТАТОЧНО ХОРОШО СБАЛАНСИРОВАННОЕ БИНАРНОЕ ДЕРЕВО ПОИСКА?

%%533

\rex[22] пРЕДПОЛОЖИМ, ЧТО ПРОГРАММИСТА НЕ ИНТЕРЕСУЕТ ПОРЯДОК КЛЮЧЕЙ В 
БИНАРНОМ ДЕРЕВЕ ПОИСКА, НО МОЖНО ОЖИДАТЬ, ЧТО ВВОД БУДЕТ ПРОИЗВОДИТЬСЯ НЕ 
В СЛУЧАЙНОМ ПОРЯДКЕ. оБСУДИТЕ МЕТОДЫ, ПОЗВОЛЯЮЩИЕ ТЕМ НЕ МЕНЕЕ 
ИСПОЛЬЗОВАТЬ ПОИСК ПО ДЕРЕВУ, ИМИТИРУЯ СЛУЧАЙНЫЙ ПОРЯДОК ВВОДА.

\ex[20] нАЙДИТЕ МАКСИМАЛЬНОЕ КОЛИЧЕСТВО ПРИСВАИВАНИИ $|S|\asg 
|LLINK|(|R|)$ (В ШАГЕ~D3) ПРИ УДАЛЕНИИ УЗЛА ИЗ ДЕРЕВА РАЗМЕРА~$N$.

\ex[м22] кАК ЧАСТО (В СРЕДНЕМ) В ШАГЕ~D1 ПРОИСХОДИТ ПЕРЕДАЧА УПРАВЛЕНИЯ 
НА~D4, ЕСЛИ УДАЛЯЕТСЯ СЛУЧАЙНЫЙ УЗЕЛ ИЗ СЛУЧАЙНОГО ДЕРЕВА РАЗМЕРА~$N$? 
(сМ. ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~H.)

\rex[м23] бУДЕТ ЛИ СЛУЧАЙНЫМ ДЕРЕВО, ПОЛУЧЕННОЕ В РЕЗУЛЬТАТЕ 
УДАЛЕНИЯ КОРНЯ СЛУЧАЙНОГО ДЕРЕВА ПОСРЕДСТВОМ АЛГОРИТМА~D?

\rex[22] дОКАЖИТЕ, ЧТО ДЛИНА ПУТИ ДЕРЕВА, ПОРОЖДЕННОГО АЛГОРИТМОМ D
С ДОПОЛНИТЕЛЬНЫМ ШАГОМ D$1{1\over2}$, НЕ БОЛЬШЕ, ЧЕМ ДЛИНА ПУТИ ДЕРЕВА, 
ПОРОЖДЕННОГО НЕМОДИФИЦИРОВАННЫМ АЛГОРИТМОМ. нАЙДИТЕ СЛУЧАЙ, КОГДА 
ШАГ~D$1{1\over2}$ ДЕЙСТВИТЕЛЬНО УМЕНЬШАЕТ ДЛИНУ ПУТИ.

\ex[м47] нАЙДИТЕ ТОЧНОЕ ИЗМЕНЕНИЕ СРЕДНЕГО ВРЕМЕНИ РАБОТЫ АЛГОРИТМА~т 
ПОСЛЕ ДЛИННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ВСТАВОК И УДАЛЕНИЙ, ЕСЛИ К АЛГОРИТМУ~D  
ДОБАВЛЯЕТСЯ НОВЫЙ ШАГ~D$1{1\over2}$.

\rex[25] яВЛЯЕТСЯ ЛИ ОПЕРАЦИЯ УДАЛЕНИЯ \emph{КОММУТАТИВНОЙ}? тО ЕСТЬ 
ПОЛУЧИТСЯ ЛИ ОДНО И ТО ЖЕ ДЕРЕВО, ЕСЛИ С ПОМОЩЬЮ АЛГОРИТМА~D УДАЛИТЬ 
УЗЛЫ $X$ И~$Y$; ЕСЛИ УДАЛИТЬ $Y$ И~$X$?

\ex[25] пОКАЖИТЕ, ЧТО ЕСЛИ В АЛГОРИТМЕ~D ПОЛНОСТЬЮ ЗАМЕНИТЬ ПРАВОЕ НА 
ЛЕВОЕ И ОБРАТНО, ТО ЕГО ЛЕГКО ПРИСПОСОБИТЬ ДЛЯ УДАЛЕНИЯ ДАННОГО УЗЛА ИЗ 
\emph{ПРАВОПРОШИТОГО} ДЕРЕВА С СОХРАНЕНИЕМ НЕОБХОДИМЫХ НИТЕЙ. (сР.~С~УПР.~2.)

\ex[M21]. пОКАЖИТЕ, ЧТО ЗАКОН зИПФА ПРИВОДИТ К~(12).

\ex[м23] нАЙДИТЕ ПРИБЛИЖЕННО СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ~(11), 
ЕСЛИ ВЕРОЯТНОСТИ~$p_k$ УДОВЛЕТВОРЯЮТ ЗАКОНУ "80-20", ОПРЕДЕЛЯЕМОМУ 
ФОРМУЛАМИ (6.1-11) И~(6.1-12).

\ex[м20] пУСТЬ МЫ ВСТАВЛЯЕМ В ДЕРЕВО КЛЮЧИ В ПОРЯДКЕ УМЕНЬШЕНИЯ ЧАСТОТ 
$p_1\ge p_2\ge\ldots\ge p_N$. мОЖЕТ ЛИ ЭТО ДЕРЕВО БЫТЬ СУЩЕСТВЕННО 
ХУЖЕ ОПТИМАЛЬНОГО ДЕРЕВА ПОИСКА?

\ex[м20] пУСТЬ $p$, $q$ И~$r$---СЛУЧАЙНО ВЫБРАННЫЕ ВЕРОЯТНОСТИ, 
ПОДЧИНЯЮЩИЕСЯ УСЛОВИЮ~$p+q+r=1$. чЕМУ РАВНЫ ВЕРОЯТНОСТИ ТОГО, ЧТО 
ДЕРЕВЬЯ I, II, III, IV ИЛИ~V (СМ.~(13)) ЯВЛЯЮТСЯ ОПТИМАЛЬНЫМИ? 
(рАССМОТРИТЕ ОТНОШЕНИЯ ПЛОЩАДЕЙ СООТВЕТСТВУЮЩИХ ОБЛАСТЕЙ НА РИС.~14.)

\ex[м20] дОКАЖИТЕ, ЧТО ПРИ ВЫПОЛНЕНИИ ШАГА~K4 АЛГОРИТМА~K 
$r[i,j-1]\le r[i+1,j]$.

\rex[M23] нАЙДИТЕ (НЕ ПРИБЕГАЯ К ПОМОЩИ эвм) ОПТИМАЛЬНОЕ БИНАРНОЕ ДЕРЕВО 
ПОИСКА, ЕСЛИ $n=40$, $p_1=5$, $p_2=p_3=\cdots=p_{40}=1$, 
$q_0=q_1=\cdots=q_{40}=0$.

\ex[м25] пУСТЬ $p_n=q_n=0$, А ВСЕ ОСТАЛЬНЫЕ ВЕСА НЕОТРИЦАТЕЛЬНЫ. дОКАЖИТЕ, 
ЧТО ОПТИМАЛЬНОЕ ДЕРЕВО ДЛЯ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) 
МОЖНО ПОЛУЧИТЬ ЗАМЕНОЙ
\picture{рИС. СТР. 533}
В ЛЮБОМ ОПТИМАЛЬНОМ ДЛЯ ($p_1$,~\dots, $p_{n-1}$; $q_0$,~\dots, $q_{n-1}$) 
ДЕРЕВЕ.

\ex[м20] пУСТЬ $A$ И~$B$---НЕПУСТЫЕ МНОЖЕСТВА ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ. пО 
ОПРЕДЕЛЕНИЮ $A\le B$, ЕСЛИ ВЫПОЛНЯЕТСЯ СЛЕДУЮЩЕЕ СВОЙСТВО: ($a\in A$, 
$b\in B$, $b<a$) ВЛЕЧЕТ ($a\in B$ И~$b\in A$). (a)~дОКАЖИТЕ, ЧТО ЭТО 
ОТНОШЕНИЕ НЕПУСТЫХ МНОЖЕСТВ ТРАНЗИТИВНО. (b)~дОКАЖИТЕ ИЛИ ОПРОВЕРГНИТЕ, 
ЧТО $A\le B$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА $A\le A \cup B \le B$.

%%534

\ex[м22] пУСТЬ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$)---НЕОТРИЦАТЕЛЬНЫЕ 
ВЕСА И~$p_n+q_n=x$. дОКАЖИТЕ, ЧТО ПРИ $x$, ИЗМЕНЯЮЩЕМСЯ ОТ 0 ДО~$\infty$, 
И ПРИ ПОСТОЯННЫХ ($p_1$,~\dots, $p_{n-1}$; $q_0$,~\dots, $q_{n-1}$) 
ЦЕНА~$c (0, n)$ ОПТИМАЛЬНОГО БИНАРНОГО ДЕРЕВА ПОИСКА ЯВЛЯЕТСЯ "ВЫПУКЛОЙ 
НЕПРЕРЫВНОЙ КУСОЧНО ЛИНЕЙНОЙ" ФУНКЦИЕЙ~$x$ С ЦЕЛЫМИ УГЛОВЫМИ 
КОЭФФИЦИЕНТАМИ. дРУГИМИ СЛОВАМИ, ДОКАЖИТЕ, ЧТО СУЩЕСТВУЮТ ПОЛОЖИТЕЛЬНЫЕ 
ЦЕЛЫЕ ЧИСЛА $l_0>l_1>\ldots>l_m$ И ДЕЙСТВИТЕЛЬНЫЕ 
ПОСТОЯННЫЕ$0=x_0<x_1<\ldots<x_m<x_{m+1}=\infty$ И~$y_0<y_1<\ldots<y_m$, 
ТАКИЕ, ЧТО $c (0, n)=y_h+l_hx$ ПРИ $x_h\le x\le x_{h+1}$, $0\le h\le m$.   

\ex[M33] цЕЛЬЮ ДАННОГО УПРАЖНЕНИЯ ЯВЛЯЕТСЯ ДОКАЗАТЕЛЬСТВО ТОГО ФАКТА, ЧТО 
МНОЖЕСТВА КОРНЕЙ~$R(i,j)$ ОПТИМАЛЬНЫХ БИНАРНЫХ ДЕРЕВЬЕВ ПОИСКА 
УДОВЛЕТВОРЯЮТ ПРИ $j-i\ge2$ СООТНОШЕНИЮ
$$
R(i, j-1)\le R(i,j)\le R(i+1, j),
$$
ВВЕДЕННОМУ В УПР.~25 (ВЕСА ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) 
ПРЕДПОЛАГАЮТСЯ НЕОТРИЦАТЕЛЬНЫМИ). дОКАЗАТЕЛЬСТВО ПРОВОДИТСЯ ИНДУКЦИЕЙ 
ПО~$j-i$; НАША ЗАДАЧА---ДОКАЗАТЬ, ЧТО 
$R(0, n-1)\le R(0,n)$ ПРИ $n\ge2$, В ПРЕДПОЛОЖЕНИИ СПРАВЕДЛИВОСТИ 
СООТНОШЕНИЯ ПРИ $j-i<n$. 
[в СИЛУ СИММЕТРИИ ОТСЮДА СЛЕДУЕТ, ЧТО $R(0, n)\le R(1, n)$.]

\medskip
\item{a)}~дОКАЖИТЕ, ЧТО $R(0, n-1)\le R(0, n)$, ЕСЛИ $p_n=q_n=0$. (сМ.~УПР.~24.)

\item{b)}~пУСТЬ $p_n+q_n=x$. чЕРЕЗ $R_h$ ОБОЗНАЧИМ МНОЖЕСТВО~$R(0, n)$ 
ОПТИМАЛЬНЫХ КОРНЕЙ, ЕСЛИ $x_h<x<x_{h+1}$, А ЧЕРЕЗ $R'_h$---МНОЖЕСТВО 
ОПТИМАЛЬНЫХ КОРНЕЙ ПРИ $x_h=x$  (СМ.~ОБОЗНАЧЕНИЯ УПР.~26). дОКАЖИТЕ, ЧТО
$$
R'_0\le R_0\le R'_1\le R_1\le\ldots\le R'_m\le R_m.
$$
оТСЮДА, ИЗ ЧАСТИ~(a) И УПР.~25 СЛЕДУЕТ, ЧТО $R(0, n-1)\le R(0, n)$ ДЛЯ ВСЕХ~$x$.
\medskip

[\emph{уКАЗАНИЕ.} рАССМОТРИТЕ СЛУЧАЙ~$x=x_h$ И ПРЕДПОЛОЖИТЕ, ЧТО ОБА ЭТИ ДЕРЕВА
\picture{рИС. СТР. 534}
ОПТИМАЛЬНЫ; $s<r$ И~$l\ge l'$. иСПОЛЬЗУЙТЕ ПРЕДПОЛОЖЕНИЕ ИНДУКЦИИ ДЛЯ 
ДОКАЗАТЕЛЬСТВА ТОГО, ЧТО СУЩЕСТВУЕТ ОПТИМАЛЬНОЕ ДЕРЕВО С КОРНЕМ~\node{r} 
И УЗЛОМ~\leaf{n} НА УРОВНЕ~$l'$, А ТАКЖЕ ОПТИМАЛЬНОЕ ДЕРЕВО С 
КОРНЕМ~\node{s} И УЗЛОМ~\leaf{n} НА УРОВНЕ~$l$.]

\ex[24] иСПОЛЬЗУЙТЕ НЕКОТОРЫЙ МАКРОЯЗЫК ДЛЯ НАПИСАНИЯ МАКРООПРЕДЕЛЕНИЯ 
"ОПТИМАЛЬНЫЙ БИНАРНЫЙ ПОИСК", ПАРАМЕТРОМ КОТОРОГО ЯВЛЯЕТСЯ ВЛОЖЕННАЯ 
СПЕЦИФИКАЦИЯ ОПТИМАЛЬНОГО БИНАРНОГО ДЕРЕВА.

\ex[40] кАКОВО \emph{НАИХУДШЕЕ} ВОЗМОЖНОЕ БИНАРНОЕ ДЕРЕВО ПОИСКА ДЛЯ 
31~НАИБОЛЕЕ УПОТРЕБИТЕЛЬНОГО АНГЛИЙСКОГО СЛОВА? (чАСТОТЫ СЛОВ ДАНЫ НА РИС.~12.)

\ex[M41] дОКАЖИТЕ ИЛИ ОПРОВЕРГНИТЕ, ЧТО ЦЕНА ОПТИМАЛЬНЫХ БИНАРНЫХ ДЕРЕВЬЕВ 
ПОИСКА УДОВЛЕТВОРЯЕТ СООТНОШЕНИЮ~$c(i,j)+c(i+1, j-1)\ge c(i, j-1)+c(i+1, j)$.

\ex[м20] (a)~еСЛИ ВЕСА ($q_0$,~\dots, $q_5$) В~(22) РАВНЫ (2, 3, 1, 1, 3, 
2) СООТВЕТСТВЕННО, ТО КАКОВА ВЗВЕШЕННАЯ ДЛИНА ПУТИ ДЕРЕВА? (b)~чЕМУ 
РАВНА ВЗВЕШЕННАЯ ДЛИНА ПУТИ ОПТИМАЛЬНОГО БИНАРНОГО ДЕРЕВА ПОИСКА, 
ИМЕЮЩЕГО ТУ ЖЕ ПОСЛЕДОВАТЕЛЬНОСТЬ ВЕСОВ?

\rex[м22] (T.~ч.~хУ И~э.~к.~тАКЕР.) дОКАЖИТЕ, ЧТО ВЕСА~$q_i+q_j$ 
НОВЫХ УЗЛОВ, ПОЛУЧАЕМЫЕ НА ФАЗЕ~1 АЛГОРИТМА хУ-тАКЕРА, СОЗДАЮТСЯ В 
НЕУБЫВАЮЩЕМ ПОРЯДКЕ.

\ex[м41] чТОБЫ НАЙТИ БИНАРНОЕ ДЕРЕВО ПОИСКА, МИНИМИЗИРУЮЩЕЕ ВРЕМЯ РАБОТЫ 
ПРОГРАММЫ~T, НУЖНО МИНИМИЗИРОВАТЬ НЕ ПРОСТО ЧИСЛО СРАВНЕНИЙ~$C$, А 
ВЕЛИЧИНУ~$7C+C1$. пРИДУМАЙТЕ АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ ОПТИМАЛЬНЫХ БИНАРНЫХ
%%535
ДЕРЕВЬЕВ ПОИСКА, ЕСЛИ ЛЕВЫЕ И ПРАВЫЕ ВЕТВИ ДЕРЕВА ИМЕЮТ 
РАЗЛИЧНЫЕ ЦЕНЫ. [кСТАТИ, КОГДА ЦЕНА ПРАВОЙ ВЕТВИ В ДВА РАЗА БОЛЬШЕ ЦЕНЫ 
ЛЕВОЙ ВЕТВИ, А ЧАСТОТЫ ВСЕХ УЗЛОВ РАВНЫ, ОПТИМАЛЬНЫМИ ОКАЗЫВАЮТСЯ 
ФИБОНАЧЧИЕВЫ ДЕРЕВЬЯ. сР.~С~L.~е.~Stanfel, 
{\sl JACM,\/} {\bf 17} (1970),  508--517.]

\ex[41] нАПИШИТЕ ПРОГРАММУ ДЛЯ АЛГОРИТМА хУ-тАКЕРА, 
ТРЕБУЮЩУЮ $O(n)$~ЕДИНИЦ ПАМЯТИ И~$O(n\log n)$~ЕДИНИЦ ВРЕМЕНИ.

\ex[м23] пОКАЖИТЕ, ЧТО КОДЫ, ПОСТРОЕННЫЕ В ДОКАЗАТЕЛЬСТВЕ ТЕОРЕМЫ~G,
 ОБЛАДАЮТ ТЕМ СВОЙСТВОМ, ЧТО $C_i$ НИКОГДА НЕ НАЧИНАЕТСЯ С~$C_j$ ПРИ~$i\ne j$.

\ex[м40] (п.~дЖ.~бЭЙЕР.) оБОБЩИВ ВЕРХНЮЮ ОЦЕНКУ В ТЕОРЕМЕ~G, ДОКАЖИТЕ, 
ЧТО ЦЕНА ЛЮБОГО ОПТИМАЛЬНОГО БИНАРНОГО ДЕРЕВА ПОИСКА С НЕОТРИЦАТЕЛЬНЫМИ 
ВЕСАМИ НЕ ПРЕВОСХОДИТ ПОЛНОГО 
ВЕСА~$S=\sum_{1le i\le n} p_i+\sum_{0\le i\le n} q_i$, УМНОЖЕННОГО НА~$H+2$,
 ГДЕ
$$
H=\sum_{1\le i\le n} (p_i/S)\log_2 (S/p_i)+\sum_{0\le i\le n} (q_i/S)\log_2(S/q_i);
$$
НА САМОМ ДЕЛЕ ПРОЦЕДУРА ВЫБОРА КОРНЕЙ, МИНИМИЗИРУЮЩАЯ МАКСИМАЛЬНЫЙ 
ВЕС ПОДДЕРЕВА, ПОЗВОЛЯЕТ ПОСТРОИТЬ ДЕРЕВО БИНАРНОГО ПОИСКА, 
УДОВЛЕТВОРЯЮЩЕЕ ЭТОЙ ОЦЕНКЕ. пОКАЖИТЕ ДАЛЕЕ, ЧТО ЦЕНА ОПТИМАЛЬНОГО 
БИНАРНОГО ДЕРЕВА ПОИСКА НЕ ПРЕВЫШАЕТ~$S$, УМНОЖЕННОГО НА~$H-\log_2(2H/e)$.

\rex[м25] (т.~ч.~хУ И~к.~ч.~тАНЬ.) пУСТЬ $n+1=2^m+k$, ГДЕ~$0\le k\le 2^m$.
сУЩЕСТВУЕТ $\perm{2^m}{k}$ БИНАРНЫХ ДЕРЕВЬЕВ, В КОТОРЫХ ВСЕ ВНЕШНИЕ УЗЛЫ 
РАСПОЛОЖЕНЫ НА УРОВНЯХ $m$ И~$m+1$. пОКАЖИТЕ, ЧТО СРЕДИ ВСЕХ ЭТИХ 
ДЕРЕВЬЕВ МЫ НАЙДЕМ ОДНО С МИНИМАЛЬНОЙ ВЗВЕШЕННОЙ ДЛИНОЙ ПУТИ ДЛЯ 
ПОСЛЕДОВАТЕЛЬНОСТИ ВЕСОВ ($q_0$,~\dots, $q_n$), ЕСЛИ ПРИМЕНИМ АЛГОРИТМ 
хУ-тАКЕРА К ПОСЛЕДОВАТЕЛЬНОСТИ ($M+q_0$,~\dots, $M+q_n$) ДЛЯ ДОСТАТОЧНО 
БОЛЬШОГО~$M$.

\ex[м35] (к.~ч.~тАНЬ.) дОКАЖИТЕ, ЧТО СРЕДИ ВСЕХ МНОЖЕСТВ 
ВЕРОЯТНОСТЕЙ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$), 
$p_1+\cdots+p_n+q_0+\cdots+q_n=1$ ДЕРЕВО С МИНИМАЛЬНОЙ ЦЕНОЙ НАИБОЛЕЕ 
ДОРОГО, ЕСЛИ $p_i=0$ ДЛЯ ВСЕХ~$i$, $q_j=0$ ДЛЯ ЧЕТНЫХ~$j$ 
И~$q_j=1/\floor{n/2}$ ДЛЯ НЕЧЕТНЫХ~$j$. [\emph{уКАЗАНИЕ.} дЛЯ ПРОИЗВОЛЬНЫХ 
ВЕРОЯТНОСТЕЙ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) ПОЛОЖИМ $c_0=q_0$, 
$c_i=p_i+q_i$ ПРИ~$1\le i\le n$  И~$S(0)=\emptyset$, А ДЛЯ~$1\le r\le 
\ceil{n/2}$ ПОЛОЖИМ $S(r)=S(r-1)\cup\{\,i,j\,\}$, ГДЕ 
$c_i+c_j$~МИНИМАЛЬНО ПО ВСЕМ~$i<j$, ТАКИМ, ЧТО $i, j\notin S(r-1)$ И~$k\in 
S(r-1)$ ПРИ ВСЕХ~$i<k<j$. пОСТРОИМ БИНАРНОЕ ДЕРЕВО~$T$ С ВНЕШНИМИ УЗЛАМИ 
ИЗ $S(n+1-2^q)$ НА УРОВНЕ~$q+1$ И С ОСТАЛЬНЫМИ ВНЕШНИМИ УЗЛАМИ НА 
УРОВНЕ~$q$, ГДЕ $q=\floor{\log_2 n}$. дОКАЖИТЕ, ЧТО ЦЕНА ЭТОГО 
ДЕРЕВА~$\le f(n)$, ГДЕ~$f(n)$---ЦЕНА ОПТИМАЛЬНОГО ДЕРЕВА ПОИСКА ДЛЯ УКАЗАННЫХ 
"НАИХУДШИХ" ВЕРОЯТНОСТЕЙ.]

\ex[м30] (ч.~к.~уОН И~шИ-кУО~чАН.) рАССМОТРИМ СХЕМУ ПОСТРОЕНИЯ БИНАРНОГО 
ДЕРЕВА ПОИСКА С ПОМОЩЬЮ АЛГОРИТМА~T, НО С ОДНИМ ОТЛИЧИЕМ:
КОГДА ЧИСЛО УЗЛОВ ПРИНИМАЕТ ВИД~$2^n-1$, ДЕРЕВО ПРИВОДИТСЯ К ИДЕАЛЬНО 
СБАЛАНСИРОВАНЯОМУ ОДНОРОДНОМУ ВИДУ С $2^k$~УЗЛАМИ НА УРОВНЕ~$k$, $0\le 
k<n$. дОКАЖИТЕ, ЧТО ЧИСЛО СРАВНЕНИЙ, ПРОИЗВОДИМЫХ ВО ВРЕМЯ ПОСТРОЕНИЯ 
ТАКОГО ДЕРЕВА, В СРЕДНЕМ СОСТАВЛЯЕТ~$M\log_2 N+O(N)$. (нЕТРУДНО ПОКАЗАТЬ, 
ЧТО НА ТАКИЕ РЕОРГАНИЗАЦИИ ДЕРЕВА ТРЕБУЕТСЯ  $O(N)$~ЕДИНИЦ ВРЕМЕНИ.)

\ex[M50] мОЖНО ЛИ ОБОБЩИТЬ АЛГОРИТМ хУ-тАКЕРА ДЛЯ НАХОЖДЕНИЯ ОПТВКАЛЬНЫХ 
ДЕРЕВЬЕВ, ЕСЛИ КАЖДЫЙ УЗЕЛ ИМЕЕТ СТЕПЕНЬ НЕ ВЫШЕ~$t$? нАПРИМЕР, ПРИ 
$t=3$ ДЕРЕВО, ОПТИМАЛЬНОЕ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ ВЕСОВ (1, 1, 100, 1, 1),  
ВЫГЛЯДИТ ТАК:
\picture{рИС. СТР. 535}

%%536

\bye