\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