\input style
\chapno=6\subchno=2\subsubchno=3\chapnotrue
%%545

т ПЕРВУЮ ОЧЕРЕДЬ НАС МОЖЕТ ИНТЕРЕСОВАТЬ ЧИСЛО~$B_{nh}$ СБАЛАНСИРОВАННЫХ 
БИНАРНЫХ ДЕРЕВЬЕВ С $n$~ВНУТРЕННИМИ УЗЛАМИ И ВЫСОТОЙ~$h$. фЛЯ 
НЕБОЛЬШИХ~$h$ ИЗ СООТНОШЕНИЙ
$$
B_0(z)=1,\quad B_1(z)=z,\quad B_{h+1}(z)=zB_h(z)(B_h(z)+2B_{h-1}(z))
\eqno(5)
$$
НЕТРУДНО ВЫЧИСЛИТЬ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$B_h(z)=\sum_{n\ge0}B_{nh}z^n$ 
(СМ. УПР.~6). ЄАКИМ ОБРАЗОМ,
$$
\matrix{
B_2(z)=& 2z^2+z^3,&\cr
B_3(z)=&& 4z^4+6z^5+4z^6&+z_7\cr
B_4(z)=&&&16z^7&+32z^8+44z^9+\cdots+8z^{14}+z^{15},\cr
}
$$
И ВООБЩЕ $B_h(z)$ ПРИ $h\ge3$ ИМЕЕТ ВИД
$$
2^{F_{h+1}-1}z^{F_{h+2}-1}+2^{F_{h+1}-2}L_{h-1}z^{F_{h+2}}
+\hbox{СЛОЖНЫЕ ЧЛЕНЫ}+2^{h-1}z^{2^h-2}+z^{2^h-1},
\eqno(6)
$$
ГДЕ $L_k=F_{k+1}+F_{k-1}$. (¤ТА ФОРМУЛА ОБОБЩАЕТ ТЕОРЕМУ~A.) ўИСЛО ВСЕХ 
СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ ВЫСОТЫ~$h$ РАВНО $B_h=B_h(1)$ И УДОВЛЕТВОРЯЕТ 
РЕКУРРЕНТНОМУ СООТНОШЕНИЮ
$$
B_0=B_1=1,\quad B_{h+1}=B^2_h+2B_hB_{h-1},
\eqno(7)
$$
ТАК ЧТО $B_2=3$, $B_3=3\cdot5$, $B_4=3^2\cdot5\cdot7$, 
$B_5=3^3\cdot5^2\cdot7\cdot23$; В ОБЩЕМ СЛУЧАЕ
$$
B_h=A_0^{F_h}\cdot A_1^{F_h-1}\ldots A_{h-1}^{F_1}\cdot A_h^{F_0},
\eqno(8)
$$
ГДЕ $A_0=1$, $A_1=3$, $A_2=5$, $A_3=7$, $A_4=23$, $A_5=347$, \dots, 
$A_h=A_{h-1}B_{h-2}+2$. яОСЛЕДОВАТЕЛЬНОСТИ $A_h$ И $B_h$ РАСТУТ 
ОЧЕНЬ БЫСТРО, КАК "ЭКСПОНЕНТА ЭКСПОНЕНТЫ"; ИЗ УПР.~7 СЛЕДУЕТ, 
ЧТО СУЩЕСТВУЕТ ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО $\theta\approx1.43684$, ТАКОЕ, ЧТО
$$
B_h=\floor{\theta^{2^h}}-\floor{\theta^{2^h-1}}+\floor{\theta^{2^h-2}}
-\cdots+(-1)^h\floor{\theta^{2^0}}.
\eqno(9)
$$
хСЛИ СЧИТАТЬ, ЧТО ВСЕ $B_h$~ДЕРЕВЬЕВ РАВНОВЕРОЯТНЫ, ТО, КАК ПОКАЗЫВАЕТ 
УПР.~8, СРЕДНЕЕ ЧИСЛО УЗЛОВ В ДЕРЕВЕ ВЫСОТЫ~$h$ РАВНО
$$
B'_h(1)/B_h(1)\approx (0.70118)\cdot 2^h.
\eqno(10)
$$
¤ТО ОЗНАЧАЕТ, ЧТО ВЫСОТА СБАЛАНСИРОВАННОГО ДЕРЕВА С $n$~УЗЛАМИ ОБЫЧНО 
ГОРАЗДО БЛИЖЕ К~$\log_2 n$, ЧЕМ К~$\log_\phi n$.

ъ СОЖАЛЕНИЮ, ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ НЕ ИМЕЮТ ОТНОШЕНИЯ К АЛГОРИТМУ~A, ТАК 
КАК МЕХАНИЗМ ЭТОГО АЛГОРИТМА ДЕЛАЕТ НЕКОТОРЫЕ ДЕРЕВЬЯ ГОРАЗДО БОЛЕЕ 
ВЕРОЯТНЫМИ, ЧЕМ ДРУГИЕ. ЁАССМОТРИМ, НАПРИМЕР, СЛУЧАЙ~$N=7$, КОГДА 
СУЩЕСТВУЕТ 17~СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ. ъЛЮЧИ МОЖНО ВСТАВЛЯТЬ $7!=5040$ 
РАЗЛИЧНЫМИ СПОСОБАМИ, ПРИ ЭТОМ ИДЕАЛЬНО СБАЛАНСИРОВАННОЕ "СОВЕРШЕННОЕ"
%%546
ДЕРЕВО
\picture{РИС. НА СТР. 546}
ПОЛУЧАЕТСЯ 2160~РАЗ. т ПРОТИВОПОЛОЖНОСТЬ ЭТОМУ ФИБОНАЧЧИЕВО ДЕРЕВО
\picture{РИС. НА СТР. 546}
ВСТРЕЧАЕТСЯ ЛИШЬ 144~РАЗА, А ПОХОЖЕЕ ДЕРЕВО
\picture{РИС. НА СТР. 546}
ВСТРЕЧАЕТСЯ 216~РАЗ. [чАМЕНИВ ЛЕВЫЕ ПОДДЕРЕВЬЯ В~(12) И~(13) ПРОИЗВОЛЬНЫМИ 
СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ С ЧЕТЫРЬМЯ УЗЛАМИ И ЗАТЕМ ЗЕРКАЛЬНО ОТРАЗИВ 
ОТНОСИТЕЛЬНО ВЕРТИКАЛЬНОЙ ОСИ, ПОЛУЧИМ 16~РАЗЛИЧНЫХ ДЕРЕВЬЕВ; ВОСЕМЬ 
ДЕРЕВЬЕВ, ПОЛУЧЕННЫХ ИЗ~(12), ВСТРЕЧАЮТСЯ ПО 144~РАЗА, А ПОЛУЧЕННЫЕ 
ИЗ~(13)---ПО 216~РАЗ. фОВОЛЬНО СТРАННО, ЧТО (13) ВСТРЕЧАЕТСЯ ЧАЩЕ, ЧЕМ (12).]

ЄОТ ФАКТ, ЧТО ИДЕАЛЬНО СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ ПОЛУЧАЮТСЯ С ТАКОЙ 
ВЫСОКОЙ ВЕРОЯТНОСТЬЮ---СОВМЕСТНО С ФОРМУЛОЙ~(10), СООТВЕТСТВУЮЩЕЙ СЛУЧАЮ 
РАВНЫХ ВЕРОЯТНОСТЕЙ,---ДЕЛАЕТ ЧРЕЗВЫЧАЙНО ПРАВДОПОДОБНЫМ СООТНОШЕНИЕ: 
(СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ ПРИ ПОИСКЕ ПО СБАЛАНСИРОВАННОМУ ДЕРЕВУ)%
$\approx\log_2 N+c$, ГДЕ $c$---МАЛАЯ КОНСТАНТА. фЕЙСТВИТЕЛЬНО, ЭМПИРИЧЕСКИЕ 
ПРОВЕРКИ ПОКАЗЫВАЮТ, ЧТО СРЕДНЕЕ ЧИСЛО СРАВНЕНИЙ, ТРЕБУЕМЫХ ДЛЯ 
ВСТАВКИ $N\hbox{-ГО}$ ЭЛЕМЕНТА, ПРИ НЕ СЛИШКОМ МАЛЫХ~$N$ ПРИМЕРНО 
РАВНО~$1.01\log_2 N+0.1$

ўТОБЫ ИЗУЧИТЬ ПОВЕДЕНИЕ АЛГОРИТМА~A НА ФАЗАХ ВСТАВКИ И БАЛАНСИРОВКИ, МОЖНО 
КЛАССИФИЦИРОВАТЬ ВНЕШНИЕ УЗЛЫ СБАЛАНСИРОВАННОГО ДЕРЕВА, КАК ПОКАЗАНО НА 
РИС.~23. яУТЬ, ВЕДУЩИЙ ИЗ ВНЕШНЕГО УЗЛА ВВЕРХ, ОПИСЫВАЕТСЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬЮ ПЛЮСОВ И МИНУСОВ ("|+|" ДЛЯ ПРАВОЙ ССЫЛКИ, "|-|" ДЛЯ 
ЛЕВОЙ); МЫ ВЫПИСЫВАЕМ ЕЕ, ПОКА НЕ ДОСТИГНЕМ ПЕРВОГО УЗЛА С НЕНУЛЕВЫМ
%% 547
ПОКАЗАТЕЛЕМ СБАЛАНСИРОВАННОСТИ ИЛИ (ЕСЛИ ТАКИХ УЗЛОВ НЕТ) ПОКА НЕ 
ДОСТИГНЕМ КОРНЯ. чАТЕМ МЫ ПИШЕМ |A| ИЛИ~|B| В СООТВЕТСТВИИ С ТЕМ, БУДЕТ 
ЛИ НОВОЕ ДЕРЕВО, ПОЛУЧЕННОЕ ПОСЛЕ ВСТАВКИ НА ДАННОЕ МЕСТО ВНУТРЕННЕГО УЗЛА,
 СБАЛАНСИРОВАННЫМ ИЛИ НЕТ. ЄАК/ПУТЬ ИЗ (3) ВВЕРХ КОДИРУЕТСЯ |++-B|, ЧТО 
ОЗНАЧАЕТ "ПРАВАЯ ССЫЛКА, ПРАВАЯ ССЫЛКА, ЛЕВАЯ ССЫЛКА, 
НЕСБАЛАНСИРОВАНО". хСЛИ КОД ОКАНЧИВАЕТСЯ НА~|A|, ПОСЛЕ ВСТАВКИ НОВОГО УЗЛА НЕ
\picture{
ЁИС. 23.ъОДЫ КЛАССИФИКАЦИИ, ОПРЕДЕЛЯЮЩИЕ ПОВЕДЕНИЕ АЛГОРИТМА A ПОСЛЕ ВСТАВКИ.
}
ТРЕБУЕТСЯ БАЛАНСИРОВКИ; КОД, ОКАНЧИВАЮЩИЙСЯ НА~|++B| ИЛИ~|--B|, 
ТРЕБУЕТ ОДНОКРАТНОГО ПОВОРОТА, А КОД, ОКАНЧИВАЮЩИЙСЯ НА~|+-B| ИЛИ~|-+B|, 
ТРЕБУЕТ ДВУКРАТНОГО ПОВОРОТА. хСЛИ ПУТЬ СОСТОИТ ИЗ $k$~ЗВЕНЬЕВ, В ШАГЕ~A6 
КОРРЕКТИРУЕТСЯ РОВНО $k-1$~ПОКАЗАТЕЛЕЙ СБАЛАНСИРОВАННОСТИ. ЄАКИМ ОБРАЗОМ, 
ОПИСАННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ ДАЮТ НЕОБХОДИМУЮ ИНФОРМАЦИЮ О ВРЕМЕНИ РАБОТЫ 
ШАГОВ~A6--A10.

¤МПИРИЧЕСКИЕ ПРОВЕРКИ СО СЛУЧАЙНЫМИ ЧИСЛАМИ В ДИАПАЗОНЕ $100\le N\le2000$ 
ДАЛИ ПРИБЛИЖЕННЫЕ ВЕРОЯТНОСТИ ДЛЯ ПУТЕЙ РАЗЛИЧНЫХ ВИДОВ (ТАБЛ.~1); 
ОЧЕВИДНО, ЭТИ ВЕРОЯТНОСТИ БЫСТРО ПРИБЛИЖАЮТСЯ К ПРЕДЕЛЬНЫМ ЗНАЧЕНИЯМ 
ПРИ~$N\to\infty$. т ТАБЛ.~2 ДАНЫ СООТВЕТСТВУЮЩИЕ ТОЧНЫЕ ВЕРОЯТНОСТИ 
($N=10$; ВСЕ $10!$~ПЕРЕСТАНОВОК СЧИТАЛИСЬ РАВНОВЕРОЯТНЫМИ.)

шЗ ТАБЛ.~1 МЫ ВИДИМ, ЧТО ВЕРОЯТНОСТЬ СОБЫТИЯ~$k\le 2$ 
РАВНА $0.144+0.153+0.144+0.144=0.585$; ТАКИМ ОБРАЗОМ, ПОЧТИ В 60\%~СЛУЧАЕВ 
ШАГ~A6 ТРИВИАЛЕН. ёРЕДНЕЕ ЧИСЛО ИЗМЕНЕНИЙ КОЭФФИЦИЕНТОВ 
СБАЛАНСИРОВАННОСТИ НА ЭТОМ ШАГЕ (0 ЗАМЕНЯЕТСЯ НА~$\pm1$) ПРИМЕРНО 
РАВНО~$1.8$. ёРЕДНЕЕ ЧИСЛО ИЗМЕНЕНИЙ КОЭФФИЦИЕНТОВ СБАЛАНСИРОВАННОСТИ 
ОТ~$\pm1$ ДО~$0$ В ШАГАХ~A7--A10 РАВНО $0.535+2(0.233+0.232)\approx1.5$,  
Т.~Е.~ВСТАВКА ОДНОГО  НОВОГО УЗЛА ДОБАВЛЯЕТ В СРЕДНЕМ 
$0.3$~НЕСБАЛАНСИРОВАННОГО УЗЛА. ¤ТО СОГЛАСУЕТСЯ С ТЕМ ФАКТОМ, ЧТО ОКОЛО 
68\% ВСЕХ УЗЛОВ В СЛУЧАЙНЫХ ДЕРЕВЬЯХ, ПОЛУЧЕННЫХ С ПОМОЩЬЮ АЛГОРИТМА~A, ОКАЗАЛИСЬ 
СБАЛАНСИРОВАННЫМИ.

%%548
{
\def\!#1{\overline{\mathstrut #1}}
\htable{ЄАБЛИЦА 1}{яРИБЛИЖЕННЫЕ ВЕРОЯТНОСТИ ПРИ ВСТАВКЕ $N\hbox{-ГО}$ ЭЛЕМЕНТА}%
{#&\hfill$#$&&\bskip\hfill$#$\hfill\cr
 & \hbox{фЛИНА ПУТИ} &  \hbox{ эЕТ БАЛАНСИРОВКИ} &  \hbox{ юДНОКРАТНЫЙ ПОВОРОТ} & \hbox{фВУКРАТНЫЙ ПОВОРОТ}\cr
\noalign{\hrule}
\mathstrut&1 & .144  &  .000  & .000  \cr
    &      2 & .153  &  .144  & .144  \cr
    &      3 & .093  &  .048  & .048  \cr
    &      4 & .058  &  .023  & .023  \cr
    &      5 & .036  &  .010  & .010  \cr
     &    >5 & .051  &  .008  & .007  \cr
ave&\!{2.78}&\!{.535}&\!{.233}&\!{.232}\cr
\noalign{\hrule}
}

\htable{ЄАБЛИЦА 2}{ЄОЧНЫЕ ВЕРОЯТНОСТИ ПРИ ВСТАВКЕ $10\hbox{-ГО}$ ЭЛЕМЕНТА}%
{#&\hfill$#$\hfill&&\bskip\hfill$#$\hfill\cr
 &\hbox{фЛИНА ПУТИ} &  \hbox{ эЕТ БАЛАНСИРОВКИ} &  \hbox{ юДНОКРАТНЫЙ ПОВОРОТ} & \hbox{фВУКРАТНЫЙ ПОВОРОТ}\cr
\noalign{\hrule}
\mathstrut& 1  & 1/7      &  0       & 0     \cr
   &        2  & 6/35     &  1/7     & 1/7   \cr
   &        3  & 4/21     &  2/35    & 2/35  \cr
   &        4  &  0       &  1/21    & 1/21  \cr
ave&\!{247/105}&\!{53/105}&\!{26/105}&\!{26/105}\cr
\noalign{\hrule}
}
}

яРИБЛИЖЕННАЯ МОДЕЛЬ ПОВЕДЕНИЯ АЛГОРИТМА~A БЫЛА ПРЕДЛОЖЕНА ъ.~ъ.~ЇОСТЕРОМ 
[Proc. ACM Nat. Conf., {\bf 20}, (1965), 192--205]. ьОДЕЛЬ ЭТА НЕ ВПОЛНЕ 
КОРРЕКТНА, НО ДОСТАТОЧНО БЛИЗКА К ИСТИНЕ, ЧТОБЫ ОТРАЗИТЬ СУЩЕСТВО ДЕЛА. 
яРЕДПОЛОЖИМ, ЧТО В БОЛЬШОМ ДЕРЕВЕ, ПОСТРОЕННОМ С ПОМОЩЬЮ АЛГОРИТМА~A, 
ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ ДАННОГО УЗЛА С ВЕРОЯТНОСТЬЮ~$p$ РАВЕН~0; 
ТОГДА ЭТОТ ПОКАЗАТЕЛЬ РАВЕН~$+1$ С ВЕРОЯТНОСТЬЮ~${1\over2}(1-p)$ И
С ТОЙ ЖЕ ВЕРОЯТНОСТЬЮ РАВЕН~$-1$. яРЕДПОЛОЖИМ ДАЛЕЕ (БЕЗ ВСЯКИХ 
ОБОСНОВАНИЙ), ЧТО ПОКАЗАТЕЛИ СБАЛАНСИРОВАННОСТИ ВСЕХ УЗЛОВ НЕЗАВИСИМЫ. 
ЄОГДА ВЕРОЯТНОСТЬ ТОГО, ЧТО ШАГ~A6 ДЕЛАЕТ НЕНУЛЕВЫМИ РОВНО 
$(k-1)$~ПОКАЗАТЕЛЕЙ, РАВНА~$p^{k-1}(1-p)$, ПОЭТОМУ СРЕДНЕЕ ЗНАЧЕНИЕ~$k$ 
ЕСТЬ~$1/(1-p)$. тЕРОЯТНОСТЬ ТОГО, ЧТО
НУЖНО ПОВЕРНУТЬ ЧАСТЬ ДЕРЕВА, РАВНА~${1\over2}$. т СРЕДНЕМ ВСТАВКА НОВОГО 
УЗЛА ДОЛЖНА УВЕЛИЧИТЬ ЧИСЛО СБАЛАНСИРОВАННЫХ УЗЛОВ ВА~$p$; ЭТО ЧИСЛО В 
ДЕЙСТВИТЕЛЬНОСТИ УВЕЛИЧИВАЕТСЯ НА~1 В ШАГЕ~A5, НА $-p1(1-Р)$ В ШАГЕ~A6, 
НА~${1\over2}$ В ШАГЕ~A7 И НА~${1\over2}\cdot2$ В ШАГЕ~A8 ИЛИ A9, ТАК ЧТО 
МЫ ПОЛУЧАЕМ
$$
p=1-p/(1-p)+{1\over2}+1.
$$
%%549
ЁЕШЕНИЕ ЭТОГО УРАВНЕНИЯ ОТНОСИТЕЛЬНО~$p$ ДАЕТ НЕПЛОХОЕ СОГЛАСИЕ С ТАБЛ.~1:
$$
p={9-\sqrt{41}\over 4}\approx 0.649;\quad 1/(1-p)\approx 2.851.
\eqno(14)
$$

тРЕМЯ РАБОТЫ ФАЗЫ ПОИСКА ПРОГРАММЫ~A (СТРОКИ 01--19) РАВНО
$$
10C+C1+2D+2-3S,
\eqno(15)
$$
ГДЕ $C$, $C1$, $S$---ТЕ ЖЕ САМЫЕ, ЧТО И В ПРЕДЫДУЩИХ АЛГОРИТМАХ ЭТОЙ ГЛАВЫ,
 a $D$---ЧИСЛО НЕСБАЛАНСИРОВАННЫХ УЗЛОВ, ПРОХОДИМЫХ ПРИ ПОИСКЕ. 
¤МПИРИЧЕСКИЕ ПРОВЕРКИ ПОКАЗЫВАЮТ, ЧТО МОЖНО
ПОЛОЖИТЬ $D\approx{1\over3}C$, $C1\approx{1\over2}(C+S)$,
$C+S\approx1.01\log_2N+0.1$, ТАК
ЧТО СРЕДНЕЕ ВРЕМЯ ПОИСКА ПРИМЕРНО РАВНО $11.3\log_2N+3-13.7S$~ЕДИНИЦ. 
(хСЛИ ПОИСК ПРОИЗВОДИТСЯ ГОРАЗДО ЧАЩЕ ВСТАВКИ, МЫ МОГЛИ БЫ, РАЗУМЕЕТСЯ, 
ИСПОЛЬЗОВАТЬ ОТДЕЛЬНУЮ, БОЛЕЕ БЫСТРУЮ ПРОГРАММУ ПОИСКА, ТАК КАК НЕ БЫЛО БЫ 
НЕОБХОДИМОСТИ СЛЕДИТЬ ЗА КОЭФФИЦИЕНТАМИ СБАЛАНСИРОВАННОСТИ; В ЭТОМ СЛУЧАЕ 
СРЕДНЕЕ ВРЕМЯ ПОИСКА СОСТАВИЛО БЫ ЛИШЬ $(6.6\log_2N+3)u$, А В НАИХУДШЕМ 
СЛУЧАЕ ВРЕМЯ РАБОТЫ БУДЕТ ВСЕ ЖЕ МЕНЬШЕ, ЧЕМ СРЕДНЕЕ ВРЕМЯ РАБОТЫ 
ПРОГРАММЫ 6.2.2Є.)

хСЛИ ПОИСК НЕУДАЧЕН, ВРЕМЯ РАБОТЫ ФАЗЫ ВСТАВКИ В ПРОГРАММЕ~р (СТРОКИ 
20--45) РАВНО $8F+26+(0, 1\hbox{ ИЛИ }2)$~ЕДИНИЦ. фАННЫЕ ТАБЛ.~1 
ПОКАЗЫВАЮТ, ЧТО В СРЕДНЕМ $F\approx1.8$. ЇАЗА БАЛАНСИРОВКИ (СТРОКИ 
46--101) ТРЕБУЕТ $16.5$, $8$, $27.5$ ИЛИ $45.5(\pm0.5)$~ЕДИНИЦ В 
ЗАВИСИМОСТИ ОТ ТОГО, УВЕЛИЧИВАЕМ ЛИ МЫ ПОЛНУЮ ВЫСОТУ, ПРОСТО ЛИ ВЫХОДИМ 
БЕЗ БАЛАНСИРОВКИ ИЛИ ЖЕ ПРОИЗВОДИМ ОДНОКРАТНЫЙ ИЛИ ДВУКРАТНЫЙ ПОВОРОТ. 
яЕРВЫЙ СЛУЧАЙ ПОЧТИ НЕ ВСТРЕЧАЕТСЯ, А ДРУГИЕ ВСТРЕЧАЮТСЯ С 
ПРИБЛИЖЕННЫМИ ВЕРОЯТНОСТЯМИ $0.535$, $0.233$, $0.232$, ПОЭТОМУ СРЕДНЕЕ 
ВРЕМЯ ВЫПОЛНЕНИЯ КОМБИНИРОВАННОЙ ВСТАВОЧНО-БАЛАНСИРОВОЧНОЙ 
ЧАСТИ ПРОГРАММЫ~A СОСТАВЛЯЕТ ПРИМЕРНО $63u$.

¤ТИ ЧИСЛА ПОКАЗЫВАЮТ, ЧТО ОПЕРАЦИИ НАД СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ 
ДОВОЛЬНО БЫСТРЫ, ХОТЯ ПРОГРАММА И ЗАНИМАЕТ МНОГО МЕСТА В ПАМЯТИ. хСЛИ 
ИСХОДНЫЕ ДАННЫЕ ЯВЛЯЮТСЯ СЛУЧАЙНЫМИ, ТО ПРОСТОЙ АЛГОРИТМ ВСТАВКИ В 
ДЕРЕВО (П.~6.2.2) ПРОИЗВОДИТ ОДНУ ВСТАВКУ ПРИМЕРНО НА $50u$~БЫСТРЕЕ, НО 
ИСПОЛЬЗОВАНИЕ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ ГАРАНТИРУЕТ ХОРОШИЕ РЕЗУЛЬТАТЫ 
ДАЖЕ ПРИ НЕСЛУЧАЙНЫХ ИСХОДНЫХ ДАННЫХ.

юДИН ИЗ СПОСОБОВ СРАВНЕНИЯ ПРОГРАММЫ~A С ПРОГРАММОЙ 6.2.2Є СОСТОИТ В 
РАССМОТРЕНИИ НАИХУДШЕГО ДЛЯ ПОСЛЕДНЕЙ ПРОГРАММЫ СЛУЧАЯ. хСЛИ МЫ 
ЗАИНТЕРЕСУЕМСЯ КОЛИЧЕСТВОМ ВРЕМЕНИ, НЕОБХОДИМЫМ ДЛЯ ВСТАВКИ В ВОЗРАСТАЮЩЕМ 
ПОРЯДКЕ $N$~КЛЮЧЕЙ В ПЕРВОНАЧАЛЬНО ПУСТОЕ ДЕРЕВО, ТО ОКАЖЕТСЯ, ЧТО 
ПРОГРАММА~A МЕДЛЕННЕЕ ПРИ $N\le 26$ И БЫСТРЕЕ ПРИ $N\ge 27$.

%%550
\picture{ЁИС. 24. яОЛЯ RANK, ИСПОЛЬЗУЕМЫЕ ПРИ ПОИСКЕ ПО ПОЗИЦИИ.}

%% 551
\section яРЕДСТАВЛЕНИЕ ЛИНЕЙНОГО СПИСКА. тЕРНЕМСЯ ТЕПЕРЬ К ЗАМЕЧАНИЮ, 
СДЕЛАННОМУ В НАЧАЛЕ ЭТОГО ПУНКТА, О ТОМ, ЧТО СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ 
МОГУТ ИСПОЛЬЗОВАТЬСЯ ДЛЯ ПРЕДСТАВЛЕНИЯ ЛИНЕЙНЫХ СПИСКОВ ТАКИМ ОБРАЗОМ, ЧТО 
МОЖНО БУДЕТ БЫСТРО ВСТАВЛЯТЬ ЭЛЕМЕНТЫ (ПРЕОДОЛЕВАЯ ТРУДНОСТЬ 
ПОСЛЕДОВАТЕЛЬНОГО РАСПОЛОЖЕНИЯ), СОХРАНЯЯ ПРИ ЭТОМ СЛУЧАЙНЫМ ДОСТУП К 
ЭЛЕМЕНТАМ СПИСКА (Т. Е. ПРЕОДОЛЕВАЯ ТРУДНОСТЬ СВЯЗАННОГО РАСПОЛОЖЕНИЯ).

шДЕЯ СОСТОИТ В ТОМ, ЧТОБЫ В КАЖДОМ УЗЛЕ ВВЕСТИ НОВОЕ ПОЛЕ С ИМЕНЕМ |RANK|. 
¤ТО ПОЛЕ ПОКАЗЫВАЕТ ОТНОСИТЕЛЬНОЕ ПОЛОЖЕНИЕ УЗЛА В СВОЕМ ПОДДЕРЕВЕ, Т.~Е. 
ОНО РАВНО ЕДИНИЦЕ ПЛЮС ЧИСЛО УЗЛОВ В ЛЕВОМ ПОДДЕРЕВЕ. эА РИС.~24 
ИЗОБРАЖЕНЫ ЗНАЧЕНИЯ~|RANK| ДЛЯ БИНАРНОГО ДЕРЕВА НА РИС.~23. ьЫ МОЖЕМ 
ПОЛНОСТЬЮ ИСКЛЮЧИТЬ ПОЛЕ~|KEY|, ИЛИ ПРИ ЖЕЛАНИИ МОЖНО ИМЕТЬ ОБА ПОЛЯ, 
ЧТО ПОЗВОЛЯЕТ НАХОДИТЬ ЭЛЕМЕНТЫ КАК ПО ЗНАЧЕНИЮ КЛЮЧА, ТАК И ПО 
ОТНОСИТЕЛЬНОМУ ПОЛОЖЕНИЮ В СПИСКЕ.

шСПОЛЬЗОВАНИЕ ПОЛЯ~|RANK| ПОЗВОЛЯЕТ СВЕСТИ ПОИСК ПО ПОЗИЦИИ К ИЗУЧЕННЫМ 
АЛГОРИТМАМ.

\alg т.(яОИСК ПО ПОЗИЦИИ В ДЕРЕВЕ.) шМЕЕТСЯ ЛИНЕЙНЫЙ СПИСОК, 
ПРЕДСТАВЛЕННЫЙ В ВИДЕ БИНАРНОГО ДЕРЕВА. рЛГОРИТМ ПОЗВОЛЯЕТ ПО ДАННОМУ~$k$ 
НАЙТИ $k\hbox{-Й}$~ЭЛЕМЕНТ СПИСКА ($k\hbox{-Й}$~УЗЕЛ ДЕРЕВА В СИММЕТРИЧНОМ 
ПОРЯДКЕ). яРЕДПОЛАГАЕТСЯ, ЧТО, КАК И В АЛГОРИТМЕ~A, ИМЕЕТСЯ ГОЛОВНОЙ УЗЕЛ, 
В КАЖДОМ УЗЛЕ ЕСТЬ ПОЛЯ~|LLINK| И~|RL1NK| И, КРОМЕ ТОГО, ПОЛЕ~|RANK|, 
ОПИСАННОЕ ВЫШЕ.

\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ $|M|\asg k$, $|P|\asg |RLINK|(|HEAD|)$.

\st[ёРАВНЕНИЕ.] хСЛИ $|P|=\NULL$, АЛГОРИТМ КОНЧАЕТСЯ НЕУДАЧНО. (¤ТО МОЖЕТ 
СЛУЧИТЬСЯ, ЛИШЬ ЕСЛИ $k$ БОЛЬШЕ ЧИСЛА УЗЛОВ В ДЕРЕВЕ ИЛИ $k\le 0$.) т 
ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ $|M|<|RANK|(|P|)$, ПЕРЕЙТИ НА \stp{3}; ЕСЛИ 
$|M|>|RANK|(|P|)$, ПЕРЕЙТИ НА \stp{4}; А ЕСЛИ $|M|=|RANK|(|P|)$, АЛГОРИТМ 
КОНЧАЕТСЯ УДАЧНО (|P| УКАЗЫВАЕТ НА $k\hbox{-Й}$~УЗЕЛ).

\st[°АГ ВЛЕВО.] єСТАНОВИТЬ $|P|\asg|LLINK|(|P|)$ И ВЕРНУТЬСЯ НА~\stp{2}.

\st[°АГ   ВПРАВО.] єСТАНОВИТЬ   $|M|\asg|M|-|RANK|(|P|)$,  
$|P|\asg|RLINK|(|P|)$ И ВЕРНУТЬСЯ НА~\stp{2}. 
\algend

т ДАННОМ АЛГОРИТМЕ ИНТЕРЕС ПРЕДСТАВЛЯЕТ ЛИШЬ 
ОПЕРАЦИЯ~$|M|\asg |M|-|RANK|(|P|)$ В ШАГЕ т4. ьОЖНО АНАЛОГИЧНЫМ ОБРАЗОМ 
МОДИФИЦИРОВАТЬ ПРОЦЕДУРУ ВСТАВКИ, ХОТЯ ЕСТЬ СВОИ ТОНКОСТИ.

\alg C.(тСТАВКА В СБАЛАНСИРОВАННОЕ ДЕРЕВО ПО ПОЗИЦИИ.) шМЕЕТСЯ ЛИНЕЙНЫЙ 
СПИСОК, ПРЕДСТАВЛЕННЫЙ В ВИДЕ СБАЛАНСИРОВАННОГО БИНАРНОГО ДЕРЕВА. 
рЛГОРИТМ ПОЗВОЛЯЕТ ПРИ ДАННОМ~$k$ ВСТАВИТЬ НОВЫЙ УЗЕЛ (|Q|---УКАЗАТЕЛЬ НА 
НЕГО) ПЕРЕД $k\hbox{-М}$~ЭЛЕМЕНТОМ СПИСКА. хСЛИ $k=N+1$, НОВЫЙ УЗЕЛ 
ПОМЕЩАЕТСЯ В КОНЕЦ СПИСКА.

%%552

ъРОМЕ ТОГО, ЧТО ВЫПОЛНЕНЫ УСЛОВИЯ АЛГОРИТМА~A, ПРЕДПОЛАГАЕТСЯ, ЧТО 
КАЖДЫЙ УЗЕЛ СОДЕРЖИТ ПОЛЕ~|RANK|. ¤ТОТ АЛГОРИТМ ОЧЕНЬ ПОХОЖ НА 
АЛГОРИТМ~A С ТЕМ ЛИШЬ ОТЛИЧИЕМ, ЧТО ВМЕСТО ПОЛЯ~|KEY| ИСПОЛЬЗУЕТСЯ ПОЛЕ~|RANK|.

\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ $|T|\asg|HEAD|$, 
$|S|\asg|P|\asg|RLINK|(|HEAD|)$,  $|U|\asg|M|\asg k$.

\st[ёРАВНЕНИЕ.] хСЛИ $|M|\le |RANK|(|P|)$, ПЕРЕЙТИ НА~\stp{3}; В 
ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ НА~\stp{4}.

\st[°АГ ВЛЕВО.] єСТАНОВИТЬ $|RANK|(|P|)\asg|RANK|(|P|)+1$ (МЫ БУДЕМ 
ВСТАВЛЯТЬ НОВЫЙ УЗЕЛ СЛЕВА ОТ~$|P|$). єСТАНОВИТЬ $|R|\asg|LLINK|(|P|)$. 
хСЛИ  $|R|=\NULL$, УСТАНОВИТЬ $|LLINK|(|P|)\asg|Q|$ И ПЕРЕЙТИ НА~\stp{5}. 
т ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ $|B|(|R|)\ne0$, УСТАНОВИТЬ $|T|\asg|P|$, 
$|S|\asg|R|$ И~$|U|\asg|M|$.  єСТАНОВИТЬ $|P|\asg|R|$ И ВЕРНУТЬСЯ НА~\stp{2}.

\st[°АГ ВПРАВО.] єСТАНОВИТЬ $|M|\asg|M|-|RANK|(|P|)$ 
И~$|R|\asg|RLINK|(|P|)$.  хСЛИ $|R|=\NULL$, УСТАНОВИТЬ 
$|RLINK|(|P|)\asg|Q|$ И
ПЕРЕЙТИ НА~\stp{5}. т ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ $|B|(|R|)\ne0$, УСТАНОВИТЬ 
$|T|\asg|P|$, $|S|\asg|R|$, $|U|\asg|M|$. эАКОНЕЦ, УСТАНОВИТЬ $|P|\asg|R|$ 
И ВЕРНУТЬСЯ НА \stp{2}.

\st[тСТАВКА.]   єСТАНОВИТЬ   $|RANK|(|Q|)+1$,   
$|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$, $|B|(|Q|)\asg0$.

\st[ъОРРЕКТИРОВКА ПОКАЗАТЕЛЕЙ СБАЛАНСИРОВАННОСТИ.] 
єСТАНОВИТЬ~$|M|\asg|U|$. (ЄЕМ САМЫМ ВОССТАНАВЛИВАЕТСЯ 
ПРЕДЫДУЩЕЕ ЗНАЧЕНИЕ |M|, КОГДА |P| БЫЛО РАВНО~|S|; ВСЕ ПОЛЯ~|RANK| 
ПОДХОДЯЩИМ ОБРАЗОМ УСТАНОВЛЕНЫ.) хСЛИ $|M|<|RANK|(|S|)$, 
УСТАНОВИТЬ~$|R|\asg|P|\asg|LLINK|(|S|)$; В ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ 
$|R|\asg|P|\asg|RLINK|(|S|)$ И~$|M|\asg|M|-|RANK|(|S|)$. чАТЕМ, ПОКА~|Ё| 
НЕ СТАНЕТ РАВНЫМ~|Q|, НУЖНО ПОВТОРЯТЬ СЛЕДУЮЩУЮ ОПЕРАЦИЮ: ЕСЛИ 
$|M|<|RANK|(|P|)$, УСТАНОВИТЬ $|B|(|P|)\asg-1$ И $|P|\asg|LLINK|(|P|)$; 
ЕСЛИ $|M|>|RANK|(|P|)$, УСТАНОВИТЬ $|B|(|P|)\asg+1$, 
$|M|\asg|M|-|RANK|(|P|)$ И~$|P|\asg|RLINK|(|P|)$. (хСЛИ $|M|=|RANK|(|P|)$,
 ТО~$|P|=|Q|$, И МОЖНО ПЕРЕЙТИ К СЛЕДУЮЩЕМУ ШАГУ.)

\st[яРОВЕРКА СБАЛАНСИРОВАННОСТИ.] хСЛИ $|U|<|RANK|(|S|)$, УСТАНОВИТЬ 
$a\asg-1$; В ПРОТИВНОМ СЛУЧАЕ $a\asg+1$. ЄЕПЕРЬ ВОЗМОЖНО НЕСКОЛЬКО СЛУЧАЕВ:
\itemitem{i)} хСЛИ $|B|(|S|)=0$, УСТАНОВИТЬ $|B|(|S|)\asg a$, 
$|LLINK|(|HEAD|)\asg|LLINK|(|HEAD|)+1$; АЛГОРИТМ ЗАВЕРШЕН.
\itemitem{ii)} хСЛИ $|B|(|S|)=-a$, УСТАНОВИТЬ $|B|(|S|)\asg0$; АЛГОРИТМ ЗАВЕРШЕН.
\itemitem{iii)} хСЛИ $|B|(|S|)=a$, ТО ПРИ $|B|(|R|)=a$ НУЖНО ИДТИ НА~\stp{8}, А
ПРИ $|B|(|R|)=-a$---НА~\stp{9}.

\st[юДНОКРАТНЫЙ ПОВОРОТ.] єСТАНОВИТЬ $|P|\asg|R|$, 
$|LINK|(a, |S|)\asg|LINK|(-a, |R|)$, $|LINK|(-a, |R|)\asg|S|$,   
$|B|(|S|)\asg|B|(|R|)\asg0$. хСЛИ $a= +1$, УСТАНОВИТЬ 
$|RANK|(|R|)\asg|RANK|(|R|)+|RANK|(|S|)$;
%%553
ЕСЛИ $a=-1$, УСТАНОВИТЬ $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|R|).$ яЕРЕЙТИ НА~\stp{10}.

\st[фВУКРАТНЫЙ ПОВОРОТ.] яРОДЕЛАТЬ ВСЕ ОПЕРАЦИИ ШАГА~A9 (АЛГОРИТМА ~A).  
чАТЕМ,  ЕСЛИ  $a=+1$,   
УСТАНОВИТЬ $|RANK|(|R|)\asg|RANK|(|R|)-|RANK|(|P|)$, 
$|RANK|(|P|)\asg|RANK|(|P|) +|RANK|(|S|)$, ЕСЛИ $a=-1$, УСТАНОВИТЬ 
$|RANK|(|P|)\asg|RANK|(|P|)+|RANK|(|R|)$, ЗАТЕМ $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|P|)$.

\st [яОСЛЕДНИЙ ШТРИХ.] хСЛИ $|S|=|RLINK|(|T|)$, ТО 
УСТАНОВИТЬ $|RLINK|(|T|)\asg|P|$; В ПРОТИВНОМ СЛУЧАЕ $|LLINK|(|T|)\asg|P|$.
\algend

\section {*єДАЛЕНИЕ, КОНКАТЕНАЦИЯ И Т. Д}. тООБЩЕ ГОВОРЯ, СУЩЕСТВУЕТ МНОГО 
ДРУГИХ ОПЕРАЦИЙ, КОТОРЫЕ НЕ НАРУШАЮТ СБАЛАНСИРОВАННОСТИ ДЕРЕВЬЕВ, НО 
СООТВЕТСТВУЮЩИЕ АЛГОРИТМЫ ДОСТАТОЧНО ДЛИННЫ, ТАК ЧТО МЫ НЕ БУДЕМ 
РАССМАТРИВАТЬ ИХ ПОДРОБНО. юБСУДИМ ЛИШЬ ОСНОВНЫЕ ИДЕИ, А ИНТЕРЕСУЮЩИЙСЯ 
ЧИТАТЕЛЬ СМОЖЕТ БЕЗ БОЛЬШОГО ТРУДА ВОССТАНОВИТЬ НЕОБХОДИМЫЕ ДЕТАЛИ.

чАДАЧА УДАЛЕНИЯ, ЕСЛИ ПОСТАВИТЬ ЕЕ КОРРЕКТНО, РЕШАЕТСЯ ЗА $O(\log N)$~ШАГОВ 
[ё.~ё.~Foster, A Study of AVL Trees, Goodyear Aerospace Corp. 
report GER-12158 (April 1965)]. яРЕЖДЕ ВСЕГО УДАЛЕНИЕ ПРОИЗВОЛЬНОГО УЗЛА 
МОЖНО СВЕСТИ К ПРОСТОМУ УДАЛЕНИЮ УЗЛА~|P|, В КОТОРОМ $|LLINK|(|P|)$ 
ИЛИ~$|RLINK|(|P|)$ РАВНЫ~$\NULL$, КАК В АЛГОРИТМЕ~6.2.2D. ¤ТОТ АЛГОРИТМ 
СЛЕДУЕТ МОДИФИЦИРОВАТЬ ТАКИМ ОБРАЗОМ, ЧТОБЫ ОН СТРОИЛ СПИСОК УКАЗАТЕЛЕЙ, 
ОПРЕДЕЛЯЮЩИХ ПУТЬ К УЗЛУ~|P|:
$$
(P_0, a_0), (P_1, a_1), \ldots, (P_l, a_l),
\eqno(16)
$$
ГДЕ   $P_0=|HEAD|$,   $a_0=+1$;  $|LINK| (a_i, P_i)=P_{i+1}$, $0\le i<l$;
$P_l=|P|$, $|LINK|(a_l, P_l)=\NULL$. ¤ЛЕМЕНТЫ ЭТОГО СПИСКА В 
ПРОЦЕССЕ СПУСКА ПО ДЕРЕВУ МОЖНО ЗАНОСИТЬ ВО ВСПОМОГАТЕЛЬНЫЙ СТЕК. яРОЦЕСС 
УДАЛЕНИЯ УЗЛА~|P| 
УСТАНАВЛИВАЕТ~$|LINK|(a_{l-1}, P_{l-1})\asg|LINK|(-a_l, P_l)$, И НУЖНО 
ОТКОРРЕКТИРОВАТЬ ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ УЗЛА~$P_{l-1}$. яРЕДПОЛОЖИМ,
 ЧТО МЫ ДОЛЖНЫ ОТКОРРЕКТИРОВАТЬ ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ УЗЛА~$P_k$, 
ПОТОМУ ЧТО УМЕНЬШИЛАСЬ ВЫСОТА ПОДДЕРЕВА~$a_k$; МОЖНО ИСПОЛЬЗОВАТЬ 
СЛЕДУЮЩУЮ ПРОЦЕДУРУ КОРРЕКТИРОВКИ: ЕСЛИ~$k=0$, ПРИСВОИТЬ 
$|LLINK|(|HEAD|)\asg|LLINK|(|HEAD|)-1$; АЛГОРИТМ ЗАВЕРШЕН, ТАК КАК 
УМЕНЬШИЛАСЬ ВЫСОТА ВСЕГО ДЕРЕВА. т ПРОТИВНОМ СЛУЧАЕ НУЖНО РАССМОТРЕТЬ 
ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ~$|B|(P_k)$, ВОЗМОЖНЫ ТРИ ВАРИАНТА:

\item{i)} $|B|(P_k)=a_k$. єСТАНОВИТЬ $|B|(P_k)\asg0$, УМЕНЬШИТЬ $k$ НА 1 И
ПОВТОРИТЬ КОРРЕКТИРОВКУ ДЛЯ НОВОГО ЗНАЧЕНИЯ~$k$.

\item{ii)} $|B|(P_k) = 0$. єСТАНОВИТЬ $|B|(P_k)\asg-a_k$; АЛГОРИТМ ЗАВЕРШЕН.

\item{iii)} $|B|(P_k)=-a_k$. ЄРЕБУЕТСЯ БАЛАНСИРОВКА!

сАЛАНСИРОВКА ТРЕБУЕТСЯ В ОБЩЕМ В ТЕХ ЖЕ СЛУЧАЯХ, ЧТО И В АЛГОРИТМЕ 
ВСТАВКИ; ПОЛЕЗНО СНОВА ВЕРНУТЬСЯ К (1), ГДЕ В РОЛИ
%%554
$A$ ВЫСТУПАЕТ~$P_k$, А В РОЛИ~$B$---УЗЕЛ~$|LINK|(-a_k, P_k)$, 
ПРИНАДЛЕЖАЩИЙ 
ВЕТВИ, \emph{ПРОТИВОПОЛОЖНОЙ} ТОЙ, ИЗ КОТОРОЙ ПРОИЗВОДИТСЯ УДАЛЕНИЕ. хСТЬ 
ТОЛЬКО ОДНО ОТЛИЧИЕ: УЗЕЛ~$B$ МОЖЕТ БЫТЬ СБАЛАНСИРОВАННЫМ, И ТОГДА ПОЛУЧИМ 
НОВЫЙ СЛУЧАЙ~3, АНАЛОГИЧНЫЙ СЛУЧАЮ~1, НО $\beta$~БУДЕТ ИМЕТ ВЫСОТУ~$h+1$. 
т СЛУЧАЯХ~1 И~2 БАЛАНСИРОВКА, ПОДОБНО~(2), ОЗНАЧАЕТ, ЧТО МЫ УМЕНЬШАЕМ 
ВЫСОТУ, УСТАНАВЛИВАЯ В КАЧЕСТВЕ КОРНЯ~(2) УЗЕЛ~$|LINK|(a_{k-1}, P_{k-1})$, 
УМЕНЬШАЯ~$k$ НА~1 И ВОЗОБНОВЛЯЯ ПРОЦЕДУРУ КОРРЕКТИРОВКИ ДЛЯ НОВОГО 
ЗНАЧЕНИЯ~$k$. т СЛУЧАЕ~3 МЫ ПРОИЗВОДИМ ОДНОКРАТНЫЙ ПОВОРОТ, ЧТО НЕ 
ИЗМЕНЯЕТ ОБЩЕЙ ВЫСОТЫ, НО ДЕЛАЕТ ПОКАЗАТЕЛИ СБАЛАНСИРОВАННОСТИ КАК~$A$, 
ТАК И~$B$ НЕНУЛЕВЫМИ; ПОЭТОМУ ПОСЛЕ ЗАНЕСЕНИЯ В~$|LINK|(a_{k-1}, P_{k-1})$ 
АДРЕСА УЗЛА~$B$ АЛГОРИТМ ЗАВЕРШАЕТСЯ.

тАЖНАЯ ОТЛИЧИТЕЛЬНАЯ ЧЕРТА УДАЛЕНИЯ СОСТОИТ В ТОМ, ЧТО ОНО МОЖЕТ 
ПОТРЕБОВАТЬ ДО $\log N$~ПОВОРОТОВ, В ТО ВРЕМЯ КАК ДЛЯ ВСТАВКИ ВСЕГДА 
ХВАТАЕТ ОДНОГО. яРИЧИНА ЭТОГО СТАНЕТ ЯСНА, ЕСЛИ ПОПЫТАТЬСЯ УДАЛИТЬ САМЫЙ 
ПРАВЫЙ УЗЕЛ ДЕРЕВА ЇИБОНАЧЧИ (СМ.~РИС.~8, П~6.2.1).

шСПОЛЬЗОВАНИЕ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ ДЛЯ ПРЕДСТАВЛЕНИЯ ЛИНЕЙНЫХ СПИСКОВ 
ДЕЛАЕТ НЕОБХОДИМЫМ АЛГОРИТМ \emph{КОНКАТЕНАЦИИ}, КОГДА ЦЕЛОЕ ДЕРЕВО~$L_2$ 
ВСТАВЛЯЕТСЯ СПРАВА ОТ ДЕРЕВА~$L_1$ БЕЗ НАРУШЕНИЯ БАЛАНСА. ъЛАРК ¤. ъРЭЙН 
ПРИДУМАЛ ОРИГИНАЛЬНОЕ РЕШЕНИЕ ЭТОЙ ЗАДАЧИ. яРЕДПОЛОЖИМ, ЧТО 
"$\mathop{\rm ВЫСОТА}\nolimits(L_1)\ge \mathop{\rm ВЫСОТЫ}\nolimits(L_2)$"; 
ДРУГОЙ СЛУЧАЙ ОБРАБАТЫВАЕТСЯ АНАЛОГИЧНЫМ ОБРАЗОМ. 
єДАЛИМ ИЗ~$L_2$ ПЕРВЫЙ УЗЕЛ, НАЗВАВ ЕГО СТЫКОВОЧНЫМ УЗЛОМ~$J$, А 
ЧЕРЕЗ~$L'_2$ ОБОЗНАЧИМ НОВОЕ ДЕРЕВО ДЛЯ $L_2\backslash\{J\}$. яОСЛЕ ЭТОГО 
СПУСКАЕМСЯ ПО ПРАВЫМ ВЕТВЯМ ДЕРЕВА~$L_1$, ПОКА НЕ ДОСТИГНЕМ УЗЛА~$P$, 
ТАКОГО, ЧТО
$$
\mathop{\rm ВЫСОТА}\nolimits(P)-\mathop{\rm ВЫСОТА}\nolimits(L'_2)=0
\hbox{ ИЛИ } 1;
$$
ЭТО ВСЕГДА ВОЗМОЖНО, ТАК КАК ПРИ ПЕРЕХОДЕ НА БОЛЕЕ НИЗКИЙ УРОВЕНЬ ВЫСОТА 
ИЗМЕНЯЕТСЯ НА~1 ИЛИ~2. ЄЕПЕРЬ ЗАМЕНЯЕМ
\picture{РИС. СТР. 554}
И ПРИСТУПАЕМ К КОРРЕКТИРОВКЕ~$L_1$, КАК ЕСЛИ БЫ НОВЫЙ УЗЕЛ~$J$ БЫЛ 
ВСТАВЛЕН ПОСРЕДСТВОМ АЛГОРИТМА~A.

ъРЭЙН РЕШИЛ ТАКЖЕ БОЛЕЕ ТРУДНУЮ ОБРАТНУЮ ЗАДАЧУ: \emph{РАСЩЕПИТЬ} СПИСОК 
НА ДВЕ ЧАСТИ, КОНКАТЕНАЦИЯ КОТОРЫХ ДАЛА БЫ ПЕРВОНАЧАЛЬНЫЙ СПИСОК. 
ЁАССМОТРИМ, НАПРИМЕР, ЗАДАЧУ РАСЩЕПЛЕНИЯ СПИСКА РИС.~20 ДЛЯ ПОЛУЧЕНИЯ ДВУХ 
СПИСКОВ, СОСТОЯЩИХ ИЗ ЭЛЕМЕНТОВ $\{\, |A|, \ldots, |I|\,\}$ И 
$\{\, |J|, \ldots, |Q|\,\}$ СООТВЕТСТВЕННО: ТРЕБУЕТСЯ СУЩЕСТВЕННАЯ 
ПЕРЕКОМПОНОВКА ПОДДЕРЕВЬЕВ. т ОБЩЕМ СЛУЧАЕ,
%% 555 
КОГДА МЫ ХОТИМ РАСЩЕПИТЬ ДЕРЕВО В ДАННОМ УЗЛЕ~$P$, ПУТЬ К~$P$ БУДЕТ ПОХОЖ 
НА ПУТЬ РИС.~25. ьЫ ХОТЕЛИ БЫ ПОСТРОИТЬ ЛЕВОЕ ДЕРЕВО, СОДЕРЖАЩЕЕ 
$\alpha_1$, $P_1$, $\alpha_4$, $P_4$, $\alpha_6$, $P_6$, $\alpha_7$, $P_7$,
 $\alpha$, $P$ В СИММЕТРИЧНОМ ПОРЯДКЕ, И ПРАВОЕ ДЕРЕВО, СОДЕРЖАЩЕЕ 
$\beta$, $P_8$, $\beta_8$, $P_5$, $\beta_5$, $P_3$, $\beta_3$, $P_2$, 
$\beta_2$. ¤ТО МОЖНО СДЕЛАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬЮ КОНКАТЕНАЦИЙ: СНАЧАЛА 
ВСТАВЛЯЕМ~$P$ СПРАВА ОТ~$\alpha$, ЗАТЕМ КОНКАТЕНИРУЕМ~$\beta$ С 
$\beta_8$, ИСПОЛЬЗУЯ~$P_8$ В КАЧЕСТВЕ СТЫКОВОЧНОГО УЗЛА,
\picture{ЁИС. 25.  чАДАЧА РАСЩЕПЛЕНИЯ СПИСКА.}
КОНКАТЕНИРУЕМ $\alpha_7$ С $\alpha P$ (УЗЕЛ~$P_7$ СТЫКОВОЧНЫЙ), $\alpha_6$ 
С $\alpha_7P_7\alpha P$ (ИСПОЛЬЗУЯ~$P_6$), $\beta P_8\beta_8$ С~$\beta_5$ 
(ИСПОЛЬЗУЯ~$P_5$) И~Т.~Д.; УЗЛЫ $P_8$, $P_7$,~\dots{}, $P_1$, ЛЕЖАЩИЕ НА 
ПУТИ К~$P$, ИСПОЛЬЗУЮТСЯ КАК СТЫКОВОЧНЫЕ. ъРЭЙН ДОКАЗАЛ, ЧТО, ЕСЛИ 
ИСХОДНОЕ ДЕРЕВО СОДЕРЖИТ $N$~УЗЛОВ, ЭТОТ АЛГОРИТМ РАСЩЕПЛЕНИЯ ТРЕБУЕТ ЛИШЬ 
$O(\log N)$~ЕДИНИЦ ВРЕМЕНИ. фЕЛО В ТОМ, ЧТО КОНКАТЕНАЦИЯ С 
ИСПОЛЬЗОВАНИЕМ ДАННОГО УЗЛА В КАЧЕСТВЕ СТЫКОВОЧНОГО ЗАНИМАЕТ 
$O(k)$~ШАГОВ, ГДЕ $k$---РАЗНОСТЬ ВЫСОТ КОНКАТЕНИРУЕМЫХ ДЕРЕВЬЕВ, 
А ЗНАЧЕНИЯ~$k$, В СУЩНОСТИ, ОБРАЗУЮТ ГЕОМЕТРИЧЕСКУЮ ПРОГРЕССИЮ.

тСЕ ЭТИ АЛГОРИТМЫ МОГУТ РАБОТАТЬ КАК С ПОЛЯМИ~|KEY|, ТАК И С ПОЛЯМИ~|RANK| 
(ИЛИ С ОБОИМИ ВМЕСТЕ), ПРАВДА, В СЛУЧАЕ КОНКАТЕНАЦИИ ВСЕ КЛЮЧИ 
ДЕРЕВА~$L_2$ ДОЛЖНЫ БЫТЬ БОЛЬШЕ КЛЮЧЕЙ~$L_1$. фЛЯ ОБЩИХ ЦЕЛЕЙ ЧАСТО 
ПРЕДПОЧТИТЕЛЬНЕЕ ИСПОЛЬЗОВАТЬ ДЕРЕВЬЯ С \emph{ТРЕМЯ СВЯЗЯМИ}, В КОТОРЫХ 
НАРЯДУ С ПОЛЯМИ~|LLINK| И~|RLINK| ИСПОЛЬЗУЕТСЯ ПОЛЕ~|UP|, УКАЗЫВАЮЩЕЕ НА 
ОТЦА, И ОДНОБИТОВЫЙ ПРИЗНАК ТОГО, ЯВЛЯЕТСЯ ЛИ ДАННЫЙ УЗЕЛ "ЛЕВЫМ" ИЛИ 
"ПРАВЫМ" СЫНОМ. яРЕДСТАВЛЕНИЕ В ВИДЕ ДЕРЕВЬЕВ С ТРЕМЯ СВЯЗЯМИ НЕМНОГО
%%556
УПРОЩАЕТ АЛГОРИТМЫ И ДЕЛАЕТ ВОЗМОЖНОЙ СПЕЦИФИКАЦИЮ УЗЛА БЕЗ ЯВНОГО 
УКАЗАНИЯ ПУТИ К НЕМУ ОТ КОРНЯ; МЫ МОЖЕМ НАПИСАТЬ ПОДПРОГРАММУ УДАЛЕНИЯ ПО 
ДАННОМУ~|P| УЗЛА~$|NODE|(|P|)$ ИЛИ УЗЛА, СЛЕДУЮЩЕГО ЗА~$|NODE|(|P|)$ В 
СИММЕТРИЧНОМ ПОРЯДКЕ (Т.~Е.~УЗЛА~$|NODE|(|P|\$))$, ИЛИ ПОДПРОГРАММУ 
НАХОЖДЕНИЯ СПИСКА, СОДЕРЖАЩЕГО~$|NODE|(|P|)$ И~Т.~Д. т АЛГОРИТМЕ УДАЛЕНИЯ 
ДЛЯ ДЕРЕВЬЕВ С ТРЕМЯ СВЯЗЯМИ НЕ НУЖНО СТРОИТЬ СПИСОК~(16), ТАК КАК 
ССЫЛКИ~|UP| ДАЮТ НЕОБХОДИМУЮ ИНФОРМАЦИЮ. ЁАЗУМЕЕТСЯ, В ЭТОМ СЛУЧАЕ 
ПРИ ВСТАВКЕ, УДАЛЕНИИ ИЛИ ПОВОРОТЕ ПРИДЕТСЯ МЕНЯТЬ НЕСКОЛЬКО БОЛЬШЕ ССЫЛОК.
 шСПОЛЬЗОВАНИЕ ДЕРЕВА С ТРЕМЯ СВЯЗЯМИ ВМЕСТО ДВУХ АНАЛОГИЧНО ИСПОЛЬЗОВАНИЮ 
ДВУХСВЯЗЕВОГО СПИСКА ВМЕСТО ОДНОСВЯЗЕВОГО: ОТПРАВЛЯЯСЬ ИЗ ЛЮБОГО МЕСТА, МЫ 
МОЖЕМ ИДТИ КАК ВПЕРЕД, ТАК И НАЗАД. яОЛНОЕ ОПИСАНИЕ АЛГОРИТМОВ РАБОТЫ 
СО СПИСКАМИ, ОСНОВАННЫХ НА ИСПОЛЬЗОВАНИИ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ С 
ТРЕМЯ СВЯЗЯМИ, МОЖНО НАЙТИ В ДОКТОРСКОЙ ДИССЕРТАЦИИ ъЛАРКА ¤. ъРЭЙНА 
(ёТЭНФОРДСКИЙ УНИВЕРСИТЕТ, 1972).

\section ъОНКУРЕНТЫ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ. эЕДАВНО БЫЛО ПРЕДЛОЖЕНО 
НЕСКОЛЬКО ДРУГИХ СПОСОБОВ ОРГАНИЗАЦИИ БИНАРНЫХ ДЕРЕВЬЕВ, ГАРАНТИРУЮЩИХ 
НЕ БОЛЕЕ ЧЕМ ЛОГАРИФМИЧЕСКИЙ РОСТ ВРЕМЕНИ ПОИСКА ПРИ УВЕЛИЧЕНИИ ЧИСЛА 
УЗЛОВ. ъ НАСТОЯЩЕМУ ВРЕМЕНИ ОНИ ИЗУЧЕНЫ НЕ ПОЛНОСТЬЮ; ВОЗМОЖНО, ЧТО ДЛЯ 
НЕКОТОРЫХ ¤ть ЭТИ СПОСОБЫ ОКАЖУТСЯ ПРЕДПОЧТИТЕЛЬНЕЕ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ.

шНТЕРЕСНОЕ ПОНЯТИЕ ДЕРЕВА СО \emph{СБАЛАНСИРОВАННЫМ ВЕСОМ} ИЗУЧЕНО 
■.~эИВЕРГЕЛЬТОМ, ¤.~ЁЕЙНГОЛЬДОМ И ў.~ъ.~єОНОМ. тМЕСТО ВЫСОТЫ 
РАССМАТРИВАЕТСЯ ВЕС ДЕРЕВА---ПО ОПРЕДЕЛЕНИЮ РАВНЫЙ ЧИСЛУ ЕГО ВНЕШНИХ УЗЛОВ---И 
НА ВСЕ УЗЛЫ НАЛАГАЕТСЯ УСЛОВИЕ
$$
\sqrt{2}-1<{\hbox{тЕС ЛЕВОГО ПОДДЕРЕВА}
\over\hbox{тЕС ПРАВОГО ПОДДЕРЕВА}}<\sqrt{2}+1.
\eqno(17)
$$
ьОЖНО ПОКАЗАТЬ, ЧТО БАЛАНС ВЕСА СОХРАНЯЕТСЯ ПОСЛЕ ВСТАВКИ, ЕСЛИ, ПОДОБНО 
АЛГОРИТМУ~A, ИСПОЛЬЗОВАТЬ ДЛЯ БАЛАНСИРОВКИ ОДНОКРАТНЫЕ И ДВУКРАТНЫЕ 
ПОВОРОТЫ (СМ.~УПР.~25). юДНАКО ВО ВРЕМЯ ОДНОЙ ВСТАВКИ МОЖЕТ ПОТРЕБОВАТЬСЯ 
МНОГО ПОВОРОТОВ. хСЛИ ОСЛАБИТЬ УСЛОВИЕ~(17), ТО БАЛАНСИРОВКА СТАНЕТ 
БОЛЕЕ БЫСТРОЙ, ПРАВДА, ЗА СЧЕТ УВЕЛИЧЕНИЯ ВРЕМЕНИ ПОИСКА.

эА ПЕРВЫЙ ВЗГЛЯД МОЖЕТ ПОКАЗАТЬСЯ, ЧТО ДЕРЕВЬЯ СО СБАЛАНСИРОВАННЫМ ВЕСОМ 
ТРЕБУЮТ БОЛЬШЕ ПАМЯТИ, ЧЕМ ОБЫЧНЫЕ СБАЛАНСИРОВАННЫЕ, НО НА САМОМ ДЕЛЕ 
ИНОГДА ОНИ ТРЕБУЮТ НЕСКОЛЬКО МЕНЬШЕ! хСЛИ В КАЖДОМ УЗЛЕ УЖЕ ЕСТЬ 
ПОЛЕ~|RANK| ДЛЯ ПРЕДСТАВЛЕНИЯ ЛИНЕЙНОГО СПИСКА, ТО ЭТО В ТОЧНОСТИ ВЕС 
ЛЕВОГО ПОДДЕРЕВА, А СООТВЕТСТВУЮЩИЕ ПРАВЫЕ ВЕСА МОЖНО ЗАПОМИНАТЬ 
ПРИ ДВИЖЕНИИ ВНИЗ ПО ДЕРЕВУ. ъАЖЕТСЯ, ОДНАКО, ЧТО НАКЛАДНЫЕ РАСХОДЫ, 
ТРЕБУЮЩИЕСЯ ДЛЯ СОХРАНЕНИЯ ВЕСОВОГО БАЛАНСА, ЗАНИМАЮТ БОЛЬШЕ ВРЕМЕНИ, 
ЧЕМ АЛГОРИТМ~A, И ЭКОНОМИЯ ДВУХ БИТОВ НА УЗЕЛ, ВЕРОЯТНО, НЕ ЯВЛЯЕТСЯ 
ДОСТАТОЧНОЙ КОМПЕНСАЦИЕЙ.

%%557

фРУГОЙ ИНТЕРЕСНЫЙ ПОДХОД К СБАЛАНСИРОВАННЫМ ДЕРЕВЬЯМ, НАЗВАННЫЙ 
"(3-2)-ДЕРЕВЬЯ", БЫЛ ПРЕДЛОЖЕН В 1970~Г. фЖОНОМ їОПКРОФТОМ [СМ. Aho, 
Hopcroft, Ullman, The Design and Analysis of Computer Algorithms 
(Reading, Mass.; Addison-Wesley, 1974), ch.~4]. шДЕЯ СОСТОИТ В ТОМ, ЧТО ИЗ 
КАЖДОГО УЗЛА МОГУТ ВЫХОДИТЬ ЛИБО ДВЕ, ЛИБО ТРИ ВЕТВИ, НО ВЗАМЕН ТРЕБУЕТСЯ, 
ЧТОБЫ ВСЕ ВНЕШНИЕ УЗЛЫ РАСПОЛАГАЛИСЬ НА ОДНОМ УРОВНЕ. ъАЖДЫЙ ВНУТРЕННИЙ 
УЗЕЛ СОДЕРЖИТ ЛИБО ОДИН, ЛИБО ДВА КЛЮЧА, КАК ПОКАЗАНО НА РИС.~26.

тСТАВКУ В (3-2)-ДЕРЕВО ОБоЯСНИТЬ НЕСКОЛЬКО ЛЕГЧЕ, ЧЕМ ВСТАВКУ В 
СБАЛАНСИРОВАННОЕ ДЕРЕВО. хСЛИ МЫ ХОТИМ ПОМЕСТИТЬ
\picture{ЁИС. 26.  (3-2)-ДЕРЕВО.}
НОВЫЙ КЛЮЧ В УЗЕЛ, СОДЕРЖАЩИЙ РОВНО ОДИН КЛЮЧ, МЫ ПРОСТО ВСТАВЛЯЕМ ЕГО В 
КАЧЕСТВЕ ВТОРОГО КЛЮЧА. ё ДРУГОЙ СТОРОНЫ, ЕСЛИ УЗЕЛ УЖЕ СОДЕРЖАЛ ДВА КЛЮЧА,
 МЫ ДЕЛИМ ЕГО НА ДВА ОДНОКЛЮЧЕВЫХ УЗЛА И ВСТАВЛЯЕМ ТРЕТИЙ КЛЮЧ В 
УЗЕЛ-ОТЕЦ. ¤ТО В СВОЮ ОЧЕРЕДЬ МОЖЕТ ВЫЗВАТЬ ДЕЛЕНИЕ ОТЦА. эА РИС.~27 
ПОКАЗАН ПРОЦЕСС ВСТАВКИ НОВОГО КЛЮЧА В (3-2)-ДЕРЕВО РИС.~26.

їОПКРОФТ ЗАМЕТИЛ, ЧТО ОПЕРАЦИИ УДАЛЕНИЯ, КОНКАТЕНАЦИИ И РАСЩЕПЛЕНИЯ 
ПРОВОДЯТСЯ НАД (3-2)-ДЕРЕВЬЯМИ ДОСТАТОЧНО ПРОСТО И ВЕСЬМА ПОХОЖИ НА 
СООТВЕТСТВУЮЩИЕ ОПЕРАЦИИ СО СБАЛАНСИРОВАННЫМИ ДЕРЕВЬЯМИ.

Ё.~сЭЙЕР [{\sl Proc. ACM-SIGFIDET Workshop\/} (1971), 219--235] ПРЕДЛОЖИЛ 
ИНТЕРЕСНОЕ ПРЕДСТАВЛЕНИЕ (3-2)-ДЕРЕВЬЕВ С ПОМОЩЬЮ БИНАРНЫХ ДЕРЕВЬЕВ. эА 
РИС.~28 ПОКАЗАНО ТАКОЕ ПРЕДСТАВЛЕНИЕ (3-2)-ДЕРЕВА РИС.~26; ОДИН БИТ В 
КАЖДОМ УЗЛЕ ИСПОЛЬЗУЕТСЯ, ЧТОБЫ ОТЛИЧИТЬ "ГОРИЗОНТАЛЬНЫЕ" ПРАВЫЕ ССЫЛКИ ОТ 
"ВЕРТИКАЛЬНЫХ". чАМЕТИМ, ЧТО, КАК И В ЛЮБОМ БИНАРНОМ ДЕРЕВЕ ПОИСКА, 
КЛЮЧИ РАСПОЛОЖЕНЫ СЛЕВА НАПРАВО В СИММЕТРИЧНОМ ПОРЯДКЕ. юКАЗЫВАЕТСЯ, ЧТО 
ПРИ ВСТАВКЕ НОВОГО КЛЮЧА В ТАКИЕ ДЕРЕВЬЯ НУЖНО ПРОДЕЛЫВАТЬ ТЕ ЖЕ ОПЕРАЦИИ, 
ЧТО И В СЛУЧАЕ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ, А ИМЕННО ОДНОКРАТНЫЕ И 
ДВУКРАТНЫЕ ПОВОРОТЫ, ПРАВДА, НУЖНА ЛИШЬ ОДНА ВЕРСИЯ КАЖДОГО ПОВОРОТА 
(НЕТ ОТРАЖЕНИЙ ОТНОСИТЕЛЬНО ВЕРТИКАЛЬНОЙ ОСИ, ИМЕВШИХСЯ В АЛГОРИТМАХ~р И~ё).

%%558

\picture{ЁИС. 27.тСТАВКА НОВОГО КЛЮЧА "|M|" В (3-2)-ДЕРЕВО РИС. 26.}

%%559

\picture{ЁИС. 28.  (3-2)-ДЕРЕВО РИС.~26, ПРЕДСТАВЛЕННОЕ КАК БИНАРНОЕ 
ДЕРЕВО ПОИСКА.}

\excercises
\ex[01] яОЧЕМУ В (1), СЛУЧАЙ 2, ДЛЯ ВОССТАНОВЛЕНИЯ БАЛАНСА НЕЛЬЗЯ ПРОСТО 
ПОМЕНЯТЬ МЕСТАМИ ЛЕВЫЕ ПОДДЕРЕВЬЯ УЗЛОВ~$A$ И~$B$?

\ex[16] юБоЯСНИТЬ, ПОЧЕМУ ДЕРЕВО СТАЛО НА ОДИН УРОВЕНЬ ВЫШЕ, ЕСЛИ 
МЫ ДОСТИГЛИ ШАГА~р7 С~$|B|(|S|) = 0$.

\rex[ь25] фОКАЖИТЕ, ЧТО СБАЛАНСИРОВАННОЕ ДЕРЕВО, ИМЕЮЩЕЕ 
$N$~ВНУТРЕННИХ УЗЛОВ, НЕ МОЖЕТ ИМЕТЬ БОЛЕЕ $(\phi-1)N=0.61803N$~УЗЛОВ С 
НЕНУЛЕВЫМИ ПОКАЗАТЕЛЯМИ СБАЛАНСИРОВАННОСТИ.

\ex[ь22] фОКАЖИТЕ ИЛИ ОПРОВЕРГНИТЕ СЛЕДУЮЩЕЕ: СРЕДИ ВСЕХ 
СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ С $F_{n+1}-1$~ВНУТРЕННИМИ УЗЛАМИ ДЕРЕВО 
ЇИБОНАЧЧИ ПОРЯДКА~$n$ ИМЕЕТ НАИБОЛЬШУЮ ДЛИНУ ВНУТРЕННЕГО ПУТИ.

\rex[ь25] фОКАЖИТЕ ИЛИ ОПРОВЕРГНИТЕ СЛЕДУЮЩЕЕ: ЕСЛИ АЛГОРИТМ~A 
ИСПОЛЬЗУЕТСЯ ДЛЯ ВСТАВКИ $N$~КЛЮЧЕЙ В ПЕРВОНАЧАЛЬНО ПУСТОЕ ДЕРЕВО И ЕСЛИ 
ЭТИ КЛЮЧИ ПОСТУПАЮТ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ, ТО ПОЛУЧЕННОЕ ДЕРЕВО 
ОПТИМАЛЬНО (Т.~Е. ОНО ИМЕЕТ МИНИМАЛЬНУЮ ДЛИНУ ВНУТРЕННЕГО ПУТИ СРЕДИ ВСЕХ 
БИНАРНЫХ ДЕРЕВЬЕВ С $N$~УЗЛАМИ).

\ex[ь21] фОКАЖИТЕ, ЧТО (5) ОПРЕДЕЛЯЕТ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ ДЛЯ 
СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ ВЫСОТЫ~$h$.

\ex[ь27] (э.~фЖ.~р~ёЛОАН И~р.~т.~рХО.) фОКАЖИТЕ ЗАМЕЧАТЕЛЬНУЮ 
ФОРМУЛУ~(9) ДЛЯ ЧИСЛА СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ ВЫСОТЫ~$h$. 
[\emph{єКАЗАНИЕ:} ПОЛОЖИТЬ $C_n=B_n+B_{n-1}$ И ИСПОЛЬЗОВАТЬ ТОТ ФАКТ, 
ЧТО $\log(C_{n+1}/C_n^2)$ ВЕСЬМА МАЛ ПРИ БОЛЬШИХ~$n$.]

\ex[ь24] (ы.~р.~їИЗДЕР.) яОКАЖИТЕ, ЧТО СУЩЕСТВУЕТ КОНСТАНТА~$\beta$, ТАКАЯ,
 ЧТО $B'_h(l)/B_h(1)-2^h\beta\to1$ ПРИ~$h\to\infty$.

\ex[ь47] ъАКОВО АСИМПТОТИЧЕСКОЕ ЧИСЛО СБАЛАНСИРОВАННЫХ БИНАРНЫХ ДЕРЕВЬЕВ 
С $n$~ВНУТРЕННИМИ УЗЛАМИ $\sum_{h>0}B_{nh}$? ъАКОВА АСИМПТОТИЧЕСКАЯ СРЕДНЯЯ
ВЫСОТА~$\sum_{h\ge0}hB_{nh}/\sum_{h\ge0}B_{nh}$?

\ex[ь48] тЕРНО ЛИ, ЧТО ПРИ ВСТАВКЕ $N\hbox{-ГО}$ ЭЛЕМЕНТА АЛГОРИТМ~A 
СОВЕРШАЕТ В СРЕДНЕМ $\sim\log_2N+c$~СРАВНЕНИЙ ($c$---НЕКОТОРАЯ КОНСТАНТА)?

\ex[22] тЕЛИЧИНА~$0.144$ ТРИЖДЫ ПОЯВЛЯЕТСЯ В ТАБЛ.~1: ОДИН РАЗ ПРИ~$k=l$ И 
ДВАЖДЫ ПРИ~$k=2$. тЕЛИЧИНА~$1/7$ ВСТРЕЧАЕТСЯ В ТЕХ ЖЕ ТРЕХ МЕСТАХ ТАБЛ.~2. 
▀ВЛЯЕТСЯ ЛИ СОВПАДЕНИЕМ, ЧТО ВО ВСЕХ ТРЕХ МЕСТАХ СТОЯТ ОДИНАКОВЫЕ ВЕЛИЧИНЫ,
 ИЛИ НА ТО ЕСТЬ ПРИЧИНЫ?

\ex[24] ўЕМУ РАВНО МАКСИМАЛЬНОЕ ВРЕМЯ РАБОТЫ ПРОГРАММЫ~A ПРИ ВСТАВКЕ 
ВОСЬМОГО УЗЛА В СБАЛАНСИРОВАННОЕ ДЕРЕВО? ъАКОВО МИНИМАЛЬНО ВОЗМОЖНОЕ 
ВРЕМЯ ТАКОЙ ВСТАВКИ?

\ex[10] яОЧЕМУ ПОЛЕ~|RANK| ЛУЧШЕ ИСПОЛЬЗОВАТЬ ТАК, КАК В ТЕКСТЕ, А 
НЕ ЗАПОМИНАТЬ В КАЧЕСТВЕ КЛЮЧА НОМЕР УЗЛА ("1" В ПЕРВОМ УЗЛЕ, "2" ВО ВТОРОМ 
И~Т.~Д)?

%%560

\ex[11] рЛГОРИТМЫ СБАЛАНСИРОВАННОГО ДЕРЕВА С ПОМОЩЬЮ ПОЛЯ~|RANK| БЫЛИ 
ПРИСПОСОБЛЕНЫ ДЛЯ РАБОТЫ С ЛИНЕЙНЫМИ СПИСКАМИ. ьОЖНО ЛИ ТАКИМ ЖЕ ОБРАЗОМ 
ПРИСПОСОБИТЬ АЛГОРИТМЫ 6.2.2Є И 6.2.2D?

\ex[18] (ъ.~¤.~ъРЭЙН.) яРЕДПОЛОЖИМ, ЧТО УПОРЯДОЧЕННЫЙ ЛИНЕЙНЫЙ СПИСОК 
ПРЕДСТАВЛЕН В ВИДЕ БИНАРНОГО ДЕРЕВА С ПОЛЯМИ~|KEY| И~|RANK| В КАЖДОМ УЗЛЕ. 
яРИДУМАЙТЕ АЛГОРИТМ, КОТОРЫЙ РАЗЫСКИВАЕТ В ДЕРЕВЕ ДАННЫЙ КЛЮЧ~$K$ 
И ОПРЕДЕЛЯЕТ ПОЛОЖЕНИЕ~$K$ В СПИСКЕ, Т.~Е. НАХОДИТ ЧИСЛО~$M$, ТАКОЕ, ЧТО 
МЕНЬШЕ~$K$ ЛИШЬ $M-1$~КЛЮЧЕЙ.

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

\rex[21] эАРИСУЙТЕ СБАЛАНСИРОВАННОЕ ДЕРЕВО, КОТОРОЕ ПОЛУЧИЛОСЬ БЫ 
ПОСЛЕ КОНКАТЕНАЦИИ ДЕРЕВА ЇИБОНАЧЧИ (12): (a) СПРАВА И (b) СЛЕВА ОТ 
ДЕРЕВА РИС.~20, ЕСЛИ ИСПОЛЬЗОВАТЬ АЛГОРИТМ КОНКАТЕНАЦИИ, ПРЕДЛОЖЕННЫЙ В ТЕКСТЕ.

\ex[21] эАРИСУЙТЕ СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ, КОТОРЫЕ ПОЛУЧИЛИСЬ БЫ ПОСЛЕ 
РАСЩЕПЛЕНИЯ ДЕРЕВА РИС.~20 НА ДВЕ ЧАСТИ: $\{\, |A|, \ldots, |I|\,\}$ 
И~$\{\, |J|, \ldots, |Q|\,\}$---С ПОМОЩЬЮ ПРЕДЛОЖЕННОГО В ТЕКСТЕ АЛГОРИТМА 
РАСЩЕПЛЕНИЯ.

\rex[26] эАЙДИТЕ СПОСОБ ТАК ПРЕОБРАЗОВАТЬ ДАННОЕ СБАЛАНСИРОВАННОЕ ДЕРЕВО,
 ЧТОБЫ ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ КОРНЯ СТАЛ ОТЛИЧЕН ОТ~$-1$. 
тАШЕ ПРЕОБРАЗОВАНИЕ ДОЛЖНО СОХРАНЯТЬ СИММЕТРИЧНЫЙ ПОРЯДОК УЗЛОВ; ОНО 
ДОЛЖНО ПОРОЖДАТЬ ИСКОМОЕ СБАЛАНСИРОВАННОЕ ДЕРЕВО ЗА $O(1)$~ЕДИНИЦ ВРЕМЕНИ 
НЕЗАВИСИМО ОТ ЧИСЛА ЕГО УЗЛОВ.

\ex[40] ЁАССМОТРИТЕ ИДЕЮ ИСПОЛЬЗОВАНИЯ ОГРАНИЧЕННОГО КЛАССА 
СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ, ВСЕ УЗЛЫ КОТОРЫХ ИМЕЮТ ПОКАЗАТЕЛИ 
СБАЛАНСИРОВАННОСТИ~$0$ ИЛИ~$+1$. (ЄОГДА ПОЛЕ~|B| МОЖНО СВЕСТИ К ОДНОМУ 
БИТУ.) ёУЩЕСТВУЕТ ЛИ ДЛЯ ТАКИХ ДЕРЕВЬЕВ ПРОЦЕДУРА ВСТАВКИ С РАЗУМНОЙ 
ЭФФЕКТИВНОСТЬЮ?

\rex[30] яРИДУМАЙТЕ АЛГОРИТМ, КОТОРЫЙ СТРОИЛ БЫ ОПТИМАЛЬНЫЕ (В СМЫСЛЕ 
УПР. 5) $N\hbox{-УЗЛОВЫЕ}$ БИНАРНЫЕ ДЕРЕВЬЯ ЗА $O(N)$~ШАГОВ. тАШ АЛГОРИТМ 
ДОЛЖЕН БЫТЬ "ДИАЛОГОВЫМ" В ТОМ СМЫСЛЕ, ЧТО ОН ПОЛУЧАЕТ УЗЛЫ ПО ОДНОМУ В 
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ И СТРОИТ ЧАСТИЧНЫЕ ДЕРЕВЬЯ, НЕ ЗНАЯ ЗАРАНЕЕ 
ОКОНЧАТЕЛЬНОГО ЗНАЧЕНИЯ~$N$. (ЄАКОЙ АЛГОРИТМ МОЖНО БЫЛО БЫ ИСПОЛЬЗОВАТЬ 
ПРИ ПЕРЕСТРОЙКЕ ПЛОХО СБАЛАНСИРОВАННОГО ДЕРЕВА ИЛИ ПРИ СЛИЯНИИ КЛЮЧЕЙ ИЗ 
ДВУХ ДЕРЕВЬЕВ В ОДНО ДЕРЕВО.)

\ex[ь20] ъАКОВ АНАЛОГ ТЕОРЕМЫ~A ДЛЯ ДЕРЕВЬЕВ СО СБАЛАНСИРОВАННЫМ ВЕСОМ?

\ex[ь20] (¤.~ЁЕЙНГОЛЬД.) (a)~фОКАЖИТЕ, ЧТО СУЩЕСТВУЮТ СБАЛАНСИРОВАННЫЕ 
ДЕРЕВЬЯ С ПРОИЗВОЛЬНО МАЛЫМ ВЕСОВЫМ ОТНОШЕНИЕМ 
"(ВЕС ЛЕВОГО ПОДДЕРЕВА)/(ВЕС ПРАВОГО ПОДДЕРЕВА)". 
(b)~фОКАЖИТЕ, ЧТО СУЩЕСТВУЮТ ДЕРЕВЬЯ СО СБАЛАНСИРОВАННЫМ ВЕСОМ, ИМЕЮЩИЕ 
СКОЛЬ УГОДНО БОЛЬШУЮ РАЗНОСТЬ МЕЖДУ ВЫСОТАМИ ЛЕВОГО И ПРАВОГО ПОДДЕРЕВЬЕВ.

\ex[ь22] (¤.~ЁЕЙНГОЛЬД.) фОКАЖИТЕ, ЧТО ЕДИНСТВЕННЫМИ БИНАРНЫМИ ДЕРЕВЬЯМИ,
 УДОВЛЕТВОРЯЮЩИМИ УСИЛЕННОМУ УСЛОВИЮ (17)
$$
{1\over2}<{\hbox{тЕС ЛЕВОГО ПОДДЕРЕВА}\over\hbox{тЕС ПРАВОГО ПОДДЕРЕВА}}<2,
$$
ЯВЛЯЮТСЯ ИДЕАЛЬНО СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ С $2^n-1$~ВНУТРЕННИМИ 
УЗЛАМИ. (т ТАКИХ ДЕРЕВЬЯХ ЛЕВЫЕ И ПРАВЫЕ ВЕСА В КАЖДОМ УЗЛЕ РАВНЫ МЕЖДУ СОБОЙ.)

\ex[27] (■.~эИВЕРГЕЛЬТ, ¤.~ЁЕЙНГОЛЬД, ў.~єОН.) яОКАЖИТЕ, ЧТО 
МОЖНО ПРИДУМАТЬ АЛГОРИТМ ВСТАВКИ ДЛЯ ДЕРЕВЬЕВ СО СБАЛАНСИРОВАННЫМ ВЕСОМ, 
СОХРАНЯЮЩИЙ УСЛОВИЕ~(17) И ПРОИЗВОДЯЩИЙ НЕ БОЛЕЕ $O(\log N)$ ПОВОРОТОВ 
НА ВСТАВКУ.

\ex[40] шССЛЕДУЙТЕ СВОЙСТВА СБАЛАНСИРОВАННЫХ $t\hbox{-АРНЫХ}$ ДЕРЕВЬЕВ 
ДЛЯ~$t>2$.

\rex[M23] юЦЕНИТЕ МАКСИМАЛЬНОЕ ЧИСЛО СРАВНЕНИЙ, НЕОБХОДИМЫХ ДЛЯ ПОИСКА В 
(3-2)-ДЕРЕВЕ С $N$~ВНУТРЕННИМИ УЗЛАМИ.

\ex[41] фАЙТЕ ЭФФЕКТИВНУЮ РЕАЛИЗАЦИЮ АЛГОРИТМОВ (3-2)-ДЕРЕВА.

\ex[ь47] яРОАНАЛИЗИРУЙТЕ ПОВЕДЕНИЕ (3-2)-ДЕРЕВЬЕВ В СРЕДНЕМ ПРИ 
СЛУЧАЙНЫХ ВСТАВКАХ.

%% 561

\ex[26] (¤.~ьАК-ъРЭЙТ.) т \S~2.5 ОБСУЖДАЛИСЬ РАЗЛИЧНЫЕ СТРАТЕГИИ 
ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИ, ВКЛЮЧАЯ "НАИБОЛЕЕ ПОДХОДЯЩИЙ" 
(ВЫБОР ОБЛАСТИ НАИМЕНЬШЕГО РАЗМЕРА, УДОВЛЕТВОРЯЮЩЕЙ ЗАПРОСУ) И "ПЕРВЫЙ 
ПОДХОДЯЩИЙ" (ВЫБОР ОБЛАСТИ С НАИМЕНЬШИМ АДРЕСОМ, УДОВЛЕТВОРЯЮЩЕЙ 
ЗАПРОСУ). яОКАЖИТЕ, ЧТО ЕСЛИ СВОБОДНОЕ ПРОСТРАНСТВО СВЯЗАНО В БИНАРНОЕ 
ДЕРЕВО, В НЕКОТОРОМ СМЫСЛЕ, СБАЛАНСИРОВАННОЕ, ТО МОЖНО НАЙТИ (a)~"НАИБОЛЕЕ 
ПОДХОДЯЩУЮ" И (b)~"ПЕРВУЮ ПОДХОДЯЩУЮ" ОБЛАСТИ В $O(\log n)$~ЕДИНИЦ 
ВРЕМЕНИ, ГДЕ $n$~ЕСТЬ ЧИСЛО СВОБОДНЫХ ОБЛАСТЕЙ ПАМЯТИ. 
(рЛГОРИТМЫ~\S~2.5 СОВЕРШАЮТ ПОРЯДКА $n$~ШАГОВ.)

\ex[34] (ь.~ЇРЕДМЭН.) яРИДУМАЙТЕ ПРЕДСТАВЛЕНИЕ ЛИНЕЙНЫХ СПИСКОВ,
 ОБЛАДАЮЩЕЕ ТЕМ СВОЙСТВОМ, ЧТО ВСТАВКА НОВОГО ЭЛЕМЕНТА МЕЖДУ 
ПОЗИЦИЯМИ $m-1$ И~$m$ ПРИ ДАННОМ~$m$ ТРЕБУЕТ $O(\log m)$~ЕДИНИЦ ВРЕМЕНИ.

\subsubchap{ёИЛЬНО ВЕТВЯЩИЕСЯ ДЕРЕВЬЯ } %6.2.4.
шЗУЧЕННЫЕ НАМИ МЕТОДЫ ПОИСКА ПО ДЕРЕВУ БЫЛИ РАЗВИТЫ В ОСНОВНОМ ДЛЯ 
ВНУТРЕННЕГО ПОИСКА, Т.~Е.~КОГДА ИССЛЕДУЕМАЯ ТАБЛИЦА ЦЕЛИКОМ СОДЕРЖИТСЯ В 
БЫСТРОЙ ВНУТРЕННЕЙ ПАМЯТИ ¤ть. ЄЕПЕРЬ ЖЕ РАССМОТРИМ ЗАДАЧУ ВНЕШНЕГО ПОИСКА,
 КОГДА НУЖНО ВЫБРАТЬ ИНФОРМАЦИЮ ИЗ ОЧЕНЬ БОЛЬШОГО ФАЙЛА, РАСПОЛОЖЕННОГО 
НА ВНЕШНИХ ЗАПОМИНАЮЩИХ УСТРОЙСТВАХ С ПРЯМЫМ ДОСТУПОМ, ТАКИХ, КАК 
МАГНИТНЫЕ ДИСКИ ИЛИ БАРАБАНЫ. (ю ДИСКАХ И БАРАБАНАХ МОЖНО ПРОЧИТАТЬ В П.~5.4.9.)

\picture{
ЁИС. 29. сОЛЬШОЕ БИНАРНОЕ ДЕРЕВО ПОИСКА МОЖНО РАЗДЕЛИТЬ  НА "СТРАНИЦЫ".
}

фРЕВОВИДНЫЕ СТРУКТУРЫ ДОВОЛЬНО УДОБНЫ ДЛЯ ВНЕШНЕГО ПОИСКА (РАЗУМЕЕТСЯ, 
ЕСЛИ ОНИ ПРЕДСТАВЛЕНЫ ПОДХОДЯЩИМ ОБРАЗОМ). ЁАССМОТРИМ БОЛЬШОЕ БИНАРНОЕ 
ДЕРЕВО ПОИСКА (РИС.~29) И ПРЕДПОЛОЖИМ, ЧТО ОНО ХРАНИТСЯ В ДИСКОВОМ ФАЙЛЕ.
 (яОЛЯ |LLINK| И~|RLINK| СОДЕРЖАТ ТЕПЕРЬ АДРЕСА НА ДИСКЕ, А НЕ АДРЕСА 
ВНУТРЕННЕЙ ПАМЯТИ.) хСЛИ МЫ ПРОЯВИМ ПРОСТОДУШИЕ И БУДЕМ 
БУКВАЛЬНО СЛЕДОВАТЬ ИЗУЧЕННЫМ АЛГОРИТМАМ ПОИСКА ПО ДЕРЕВУ, НАМ 
ПОНАДОБИТСЯ ОКОЛО $\log_2 N$~ОБРАЩЕНИЙ К ДИСКУ. яРИ $N$, РАВНОМ МИЛЛИОНУ,
%%562
ИХ БУДЕТ ПРИМЕРНО 20. эО ЕСЛИ РАЗДЕЛИТЬ ДЕРЕВО НА "СТРАНИЦЫ" ПО 7 
УЗЛОВ В КАЖДОЙ, КАК ПОКАЗАНО ПУНКТИРОМ НА РИС.~29, И ЕСЛИ В КАЖДЫЙ МОМЕНТ 
ВРЕМЕНИ ДОСТУПНА ЛИШЬ ОДНА СТРАНИЦА, ТО ПОТРЕБУЕТСЯ ПРИМЕРНО В ТРИ РАЗА 
МЕНЬШЕ ОБРАЩЕНИЙ, Т. Е. ПОИСК УСКОРИТСЯ В ТРИ РАЗА!

уРУППИРОВКА УЗЛОВ В СТРАНИЦЫ, ПО СУЩЕСТВУ, ПРЕОБРАЗУЕТ БИНАРНЫЕ ДЕРЕВЬЯ В 
ОКТАРНЫЕ, РАЗВЕТВЛЯЮЩИЕСЯ В КАЖДОЙ СТРАНИЦЕ-УЗЛЕ НА 8 ПУТЕЙ. хСЛИ 
ДОПУСТИМЫ СТРАНИЦЫ БОЛЬШИХ РАЗМЕРОВ, РАЗВЕТВЛЯЮЩИЕСЯ НА 128 ПУТЕЙ ПОСЛЕ 
КАЖДОГО ОБРАЩЕНИЯ К ДИСКУ, ТО МОЖНО НАХОДИТЬ ТРЕБУЕМЫЙ КЛЮЧ В ТАБЛИЦЕ 
ИЗ МИЛЛИОНА ЭЛЕМЕНТОВ, ПРОСМОТРЕВ ЛИШЬ ТРИ СТРАНИЦЫ. ьОЖНО ПОСТОЯННО 
ХРАНИТЬ КОРНЕВУЮ СТРАНИЦУ ВО ВНУТРЕННЕЙ ПАМЯТИ;
ТОГДА ПОТРЕБУЮТСЯ ЛИШЬ ДВА ОБРАЩЕНИЯ К ДИСКУ, ХОТЯ В ЛЮБОЙ МОМЕНТ 
ВРЕМЕНИ ВО ВНУТРЕННЕЙ ПАМЯТИ БУДЕТ НЕ БОЛЕЕ 254 КЛЮЧЕЙ.

ЁАЗУМЕЕТСЯ, НЕ СЛЕДУЕТ ДЕЛАТЬ СТРАНИЦЫ ОЧЕНЬ БОЛЬШИМИ, ТАК КАК РАЗМЕРЫ 
ВНУТРЕННЕЙ ПАМЯТИ ОГРАНИЧЕНЫ И ЧТЕНИЕ БОЛЬШЕЙ СТРАНИЦЫ ЗАНИМАЕТ БОЛЬШЕ 
ВРЕМЕНИ. яРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО ЧТЕНИЕ СТРАНИЦЫ, ДОПУСКАЮЩЕЙ 
РАЗВЕТВЛЕНИЕ НА $m$ ПУТЕЙ, ЗАНИМАЕТ $72.5+0.05m$ МС. тРЕМЯ НА ВНУТРЕННЮЮ 
ОБРАБОТКУ КАЖДОЙ СТРАНИЦЫ СОСТАВИТ ОКОЛО $a+b\log m$ МС, ГДЕ $a$ МАЛО ПО 
СРАВНЕНИЮ С $72.5$, ТАК ЧТО ПОЛНОЕ ВРЕМЯ, ТРЕБУЮЩЕЕСЯ НА ПОИСК В БОЛЬШОЙ 
ТАБЛИЦЕ, ПРИМЕРНО ПРОПОРЦИОНАЛЬНО $\log N$, УМНОЖЕННОМУ НА
$$
(72.5 + 0.05m)/\log m +b.
$$
¤ТА ВЕЛИЧИНА ДОСТИГАЕТ МИНИМУМА ПРИ $m\approx350$; В ДЕЙСТВИТЕЛЬНОСТИ 
ЭТОТ МИНИМУМ ОЧЕНЬ "ШИРОК". чНАЧЕНИЯ, ОЧЕНЬ БЛИЗКИЕ К ОПТИМАЛЬНОМУ, 
ДОСТИГАЮТСЯ ПРИ $m$ ОТ~200 ДО~500. эА ПРАКТИКЕ ПОЛУЧЕНИЕ ПОДОБНОГО 
ДИАПАЗОНА ХОРОШИХ ЗНАЧЕНИЙ $m$ ЗАВИСИТ ОТ ХАРАКТЕРИСТИК ИСПОЛЬЗУЕМЫХ 
ВНЕШНИХ ЗАПОМИНАЮЩИХ УСТРОЙСТВ И ОТ ДЛИНЫ ЗАПИСЕЙ В ТАБЛИЦЕ.

є. ш. ыАНДАУЭР [{\sl IEE Trans.\/}, {\bf EC-12} (1963), 863--871] 
ПРЕДЛОЖИЛ СТРОИТЬ $m$-АРНЫЕ ДЕРЕВЬЯ СЛЕДУЮЩИМ ОБРАЗОМ: РАЗМЕЩАТЬ УЗЛЫ 
НА УРОВНЕ $l+1$, ЛИШЬ ЕСЛИ УРОВЕНЬ $l$ ПОЧТИ ЗАПОЛНЕН. ¤ТА СХЕМА ТРЕБУЕТ 
ДОВОЛЬНО СЛОЖНОЙ СИСТЕМЫ ПОВОРОТОВ, ТАК КАК ДЛЯ ВСТАВКИ ОДНОГО НОВОГО 
ЭЛЕМЕНТА МОЖЕТ ПОТРЕБОВАТЬСЯ ОСНОВАТЕЛЬНАЯ ПЕРЕСТРОЙКА ДЕРЕВА; 
ыАНДАУЭР ИСХОДИЛ ИЗ ПРЕДПОЛОЖЕНИЯ, ЧТО ПОИСК ПРИХОДИТСЯ 
ПРОИЗВОДИТЬ ГОРАЗДО ЧАЩЕ ВСТАВОК И УДАЛЕНИЙ.

хСЛИ ФАЙЛ ХРАНИТСЯ НА ДИСКЕ И ЯВЛЯЕТСЯ ОБоЕКТОМ СРАВНИТЕЛЬНО РЕДКИХ 
ВСТАВОК И УДАЛЕНИЙ, ТО ДЛЯ ЕГО ПРЕДСТАВЛЕНИЯ ПОДХОДИТ ТРЕХУРОВНЕВОЕ 
ДЕРЕВО, ГДЕ ПЕРВЫЙ УРОВЕНЬ РАЗВЕТВЛЕНИЯ ОПРЕДЕЛЯЕТ, КАКОЙ ЦИЛИНДР БУДЕТ 
ИСПОЛЬЗОВАТЬСЯ, СЛЕДУЮЩИЙ УРОВЕНЬ РАЗВЕТВЛЕНИЯ ОПРЕДЕЛЯЕТ 
СООТВЕТСТВУЮЩУЮ ДОРОЖКУ НА ЭТОМ ЦИЛИНДРЕ, А ТРЕТИЙ УРОВЕНЬ СОДЕРЖИТ СОБСТВЕННО
%% 563
ЗАПИСИ. ЄАКОЙ МЕТОД НАЗЫВАЕТСЯ \dfn{ИНДЕКСНО-ПОСЛЕДОВАТЕЛЬНОЙ} 
ОРГАНИЗАЦИЕЙ ФАЙЛА [СР. {\sl JACM\/}, {\bf 16} (1969), 569--571].

Ё. ьЮНЦ И Ё. єЗГАЛИС [Proc. Princeton Conf. on Inf. Sciences and Systems, 
4 (1970), 345--349] ПРЕДЛОЖИЛИ МОДИФИКАЦИЮ АЛГОРИТМА 6.2.2Є, ГДЕ ВСЕ 
ВСТАВКИ ПОРОЖДАЮТ УЗЛЫ, ПРИНАДЛЕЖАЩИЕ ТОЙ ЖЕ СТРАНИЦЕ, ЧТО И ИХ 
ПРЕДШЕСТВЕННИК (ЕСЛИ ТОЛЬКО ЭТО ВОЗМОЖНО); ЕСЛИ СТРАНИЦА ПОЛНОСТЬЮ ЗАНЯТА, 
ЗАВОДИТСЯ НОВАЯ СТРАНИЦА (ЕСЛИ ТАКОВАЯ ИМЕЕТСЯ). яРИ НЕОГРАНИЧЕННОМ 
КОЛИЧЕСТВЕ СТРАНИЦ И СЛУЧАЙНОМ ПОРЯДКЕ ПОСТУПАЮЩИХ ДАННЫХ СРЕДНЕЕ 
ЧИСЛО ОБРАЩЕНИЙ, К ДИСКУ, КАК МОЖНО ПОКАЗАТЬ, ПРИБЛИЖЕННО 
РАВНО $H_N/(H_m-1)$, ЧТО ЛИШЬ НЕМНОГИМ БОЛЬШЕ ЧИСЛА ОБРАЩЕНИЙ В СЛУЧАЕ 
НАИЛУЧШЕГО ВОЗМОЖНОГО $m$-АРНОГО ДЕРЕВА (СМ. УПР.~10).

\section $B\hbox{-ДЕРЕВЬЯ}$. т 1970~Г. Ё. сЭЙЕР И ¤. ьАК-ъРЭЙТ 
[{\sl Acta Informatica\/}, (1972), 173--189] 
И НЕЗАВИСИМО ОТ НИХ ПРИМЕРНО В ТО ЖЕ ВРЕМЯ ь. ъАУФМАН [НЕОПУБЛИКОВАНО] 
ПРЕДЛОЖИЛИ НОВЫЙ ПОДХОД К ВНЕШНЕМУ ПОИСКУ ПОСРЕДСТВОМ СИЛЬНО ВЕТВЯЩИХСЯ 
ДЕРЕВЬЕВ. шХ ИДЕЯ ОСНОВЫВАЕТСЯ НА ПОДВИЖНОСТИ НОВОГО ТИПА СТРУКТУР ДАННЫХ,
 НАЗВАННЫХ \dfn{$B\hbox{-ДЕРЕВЬЯМИ}$}, И ПОЗВОЛЯЕТ ПРОИЗВОДИТЬ ПОИСК ИЛИ
ИЗМЕНЯТЬ 
БОЛЬШОЙ ФАЙЛ С "ГАРАНТИРОВАННОЙ" ЭФФЕКТИВНОСТЬЮ В НАИХУДШЕМ СЛУЧАЕ, 
ИСПОЛЬЗУЯ ПРИ ЭТОМ СРАВНИТЕЛЬНО ПРОСТЫЕ АЛГОРИТМЫ.

\dfn{$B\hbox{-ДЕРЕВОМ}$ ПОРЯДКА $m$} НАЗЫВАЕТСЯ ДЕРЕВО, ОБЛАДАЮЩЕЕ СЛЕДУЮЩИМИ
СВОЙСТВАМИ:
\medskip
\item{i)} ъАЖДЫЙ УЗЕЛ ИМЕЕТ НЕ БОЛЕЕ $m$ СЫНОВЕЙ.
\item{ii)} ъАЖДЫЙ УЗЕЛ, КРОМЕ КОРНЯ И ЛИСТЬЕВ, ИМЕЕТ НЕ МЕНЕЕ
$m/2$ СЫНОВЕЙ.
\item{iii)} ъОРЕНЬ, ЕСЛИ ОН НЕ ЛИСТ, ИМЕЕТ НЕ МЕНЕЕ 2 СЫНОВЕЙ.
\item{iv)} тСЕ ЛИСТЬЯ РАСПОЛОЖЕНЫ НА ОДНОМ УРОВНЕ И НЕ СОДЕРЖАТ
ИНФОРМАЦИИ.
\item{v)} эЕЛИСТОВОЙ УЗЕЛ С $k$ СЫНОВЬЯМИ СОДЕРЖИТ $k-1$ КЛЮЧЕЙ.
\medskip
\noindent (ъАК И ОБЫЧНО, ЛИСТ---КОНЦЕВОЙ УЗЕЛ, У НЕГО НЕТ ПРЕЕМНИКОВ. ЄАК 
КАК ЛИСТЬЯ НЕ СОДЕРЖАТ ИНФОРМАЦИИ, ИХ МОЖНО РАССМАТРИВАТЬ КАК ВНЕШНИЕ 
УЗЛЫ, КОТОРЫХ В ДЕЙСТВИТЕЛЬНОСТИ НЕТ В ДЕРЕВЕ, ТАК ЧТО $\NULL$---ЭТО 
УКАЗАТЕЛЬ НА ЛИСТ.)

эА РИС.~30 ПОКАЗАНО $B\hbox{-ДЕРЕВО}$ ПОРЯДКА 7. ъАЖДЫЙ УЗЕЛ (КРОМЕ КОРНЯ И 
ЛИСТЬЕВ) ИМЕЕТ ОТ~$\lceil 7/2\rceil$ ДО~7 ПРЕЕМНИКОВ И СОДЕРЖИТ 3, 4, 5 
ИЛИ 6 КЛЮЧЕЙ. ъОРНЕВОЙ УЗЕЛ МОЖЕТ СОДЕРЖАТЬ ОТ~1 ДО~6 КЛЮЧЕЙ (В ДАННОМ 
СЛУЧАЕ 2). тСЕ ЛИСТЬЯ НАХОДЯТСЯ НА ТРЕТЬЕМ УРОВНЕ. чАМЕТЬТЕ, ЧТО (a) 
КЛЮЧИ РАСПОЛОЖЕНЫ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ СЛЕВА НАПРАВО, ЕСЛИ 
ИСПОЛЬЗОВАТЬ ЕСТЕСТВЕННОЕ ОБОБЩЕНИЕ ПОНЯТИЯ СИММЕТРИЧНОГО ПОРЯДКА, И 
(b) КОЛИЧЕСТВО ЛИСТЬЕВ РОВНО НА ЕДИНИЦУ БОЛЬШЕ КОЛИЧЕСТВА КЛЮЧЕЙ.

B-ДЕРЕВЬЯ ПОРЯДКА 1 И~2, ОЧЕВИДНО, НЕИНТЕРЕСНЫ; ПОЭТОМУ МЫ РАССМОТРИМ ЛИШЬ 
СЛУЧАЙ $m\ge 3$. чАМЕТЬТЕ, ЧТО (3-2)-ДЕРЕВЬЯ,
%% 564
\picture{ЁИС. 30. $B\hbox{-ДЕРЕВО}$ ПОРЯДКА 7}
%% 565
ОПРЕДЕЛЕННЫЕ В КОНЦЕ П.~6.2.3, ЯВЛЯЮТСЯ $B\hbox{-ДЕРЕВЬЯМИ}$ ПОРЯДКА 3;
И ОБРАТНО, $B\hbox{-ДЕРЕВО}$ ПОРЯДКА 3 ЕСТЬ (3-2)-ДЕРЕВО.

єЗЕЛ, СОДЕРЖАЩИЙ $j$ КЛЮЧЕЙ И $j+1$ УКАЗАТЕЛЕЙ, МОЖНО ПРЕДСТАВИТЬ В ВИДЕ
\picture{єЗЕЛ $B\hbox{-ДЕРЕВА}$}
ГДЕ $K_1<K_2<\ldots <K_j$, А $P_i$ УКАЗЫВАЕТ НА ПОДДЕРЕВО КЛЮЧЕЙ, БОЛЬШИХ 
$K_i$ И МЕНЬШИХ $K_{i+1}$. ёЛЕДОВАТЕЛЬНО, ПОИСК В $B\hbox{-ДЕРЕВЕ}$ АБСОЛЮТНО 
ПРЯМОЛИНЕЕН: ПОСЛЕ ТОГО КАК УЗЕЛ (1) РАЗМЕЩЕН ВО ВНУТРЕННЕЙ ПАМЯТИ, МЫ 
ИЩЕМ ДАННЫЙ АРГУМЕНТ СРЕДИ КЛЮЧЕЙ $K_1$, $K_2$, \dots, $K_j$. (яРИ БОЛЬШИХ 
$j$, ВЕРОЯТНО, ПРОИЗВОДИТСЯ БИНАРНЫЙ ПОИСК, А ПРИ МАЛЫХ $j$ НАИЛУЧШИМ 
БУДЕТ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК.) хСЛИ ПОИСК УДАЧЕН, НУЖНЫЙ КЛЮЧ НАЙДЕН; 
ЕСЛИ ПОИСК НЕУДАЧЕН В СИЛУ ТОГО, ЧТО АРГУМЕНТ ЛЕЖИТ МЕЖДУ $K_i$,
 И~$K_{i+1}$, МЫ "ПОДКАЧИВАЕМ" (ВЫЗЫВАЕМ В ОПЕРАТИВНУЮ ПАМЯТЬ) УЗЕЛ, 
УКАЗАННЫЙ $P_i$, И ПРОДОЛЖАЕМ ПРОЦЕСС. єКАЗАТЕЛЬ $P_0$ ИСПОЛЬЗУЕТСЯ, 
ЕСЛИ АРГУМЕНТ МЕНЬШЕ $K_1$, a $P_j$ ИСПОЛЬЗУЕТСЯ, ЕСЛИ АРГУМЕНТ БОЛЬШЕ 
$K_j$. яРИ $P_i=\NULL$ ПОИСК НЕУДАЧЕН.

яРИВЛЕКАТЕЛЬНОЙ ЧЕРТОЙ $B\hbox{-ДЕРЕВЬЕВ}$ ЯВЛЯЕТСЯ ИСКЛЮЧИТЕЛЬНАЯ ПРОСТОТА, С 
КОТОРОЙ ПРОИЗВОДЯТСЯ ВСТАВКИ. ЁАССМОТРИМ, НАПРИМЕР, РИС.~30; КАЖДЫЙ ЛИСТ 
СООТВЕТСТВУЕТ МЕСТУ ВОЗМОЖНОЙ ВСТАВКИ. хСЛИ НУЖНО ВСТАВИТЬ НОВЫЙ КЛЮЧ 
$337$, МЫ ПРОСТО МЕНЯЕМ УЗЕЛ
\picture{тСТАВКА В $B\hbox{-ДЕРЕВО}$}
ё ДРУГОЙ СТОРОНЫ, ПРИ ПОПЫТКЕ ВСТАВИТЬ НОВЫЙ КЛЮЧ $071$ МЫ ОБНАРУЖИВАЕМ, 
ЧТО В СООТВЕТСТВУЮЩЕМ УЗЛЕ УРОВНЯ 2 НЕТ МЕСТА---ОН УЖЕ "ПОЛОН". ¤ТУ 
ТРУДНОСТЬ МОЖНО ПРЕОДОЛЕТЬ, РАСЩЕПИВ УЗЕЛ НА ДВЕ ЧАСТИ ПО ТРИ КЛЮЧА В 
КАЖДОЙ И ПОДНЯВ СРЕДНИЙ КЛЮЧ НА УРОВЕНЬ 1:
\picture{ЁАСЩЕПЛЕНИЕ УЗЛА ПРИ ВСТАВКЕ}
%% 566 

тООБЩЕ, ЕСЛИ НУЖНО ВСТАВИТЬ НОВЫЙ ЭЛЕМЕНТ В $B\hbox{-ДЕРЕВО}$ ПОРЯДКА $m$, ВСЕ 
ЛИСТЬЯ КОТОРОГО РАСПОЛОЖЕНЫ НА УРОВНЕ $l$, НОВЫЙ КЛЮЧ ВСТАВЛЯЮТ В 
ПОДХОДЯЩИЙ УЗЕЛ УРОВНЯ $l-1$. хСЛИ УЗЕЛ ТЕПЕРЬ СОДЕРЖИТ $m$ КЛЮЧЕЙ, Т. Е. 
ИМЕЕТ ВИД (1) С $j=m$, ЕГО РАСЩЕПЛЯЮТ НА ДВА УЗЛА
\picture{ЁАСЩЕПЛЕНИЕ УЗЛА: ОБЩИЙ ВИД}
И ВСТАВЛЯЮТ КЛЮЧ $K_{\lceil m/2\rceil}$ В УЗЕЛ-ОТЕЦ. (ЄАКИМ ОБРАЗОМ, 
УКАЗАТЕЛЬ $P$ В НЕМ ЗАМЕНЯЕТСЯ ПОСЛЕДОВАТЕЛЬНОСТЬЮ $P$, $K_{\lceil 
m/2\rceil}$, $P'$.) ¤ТА ВСТАВКА В СВОЮ ОЧЕРЕДЬ МОЖЕТ ПРИВЕСТИ К 
РАСЩЕПЛЕНИЮ УЗЛА-ОТЦА. (ёР. С РИС.~27, ГДЕ ИЗОБРАЖЕН СЛУЧАЙ $m=3$.) 
хСЛИ НУЖНО РАСЩЕПИТЬ КОРНЕВОЙ УЗЕЛ, КОТОРЫЙ НЕ ИМЕЕТ ОТЦА, ТО ПРОСТО 
СОЗДАЮТ НОВЫЙ КОРЕНЬ И ПОМЕЩАЮТ В НЕГО ЕДИНСТВЕННЫЙ КЛЮЧ $K_{\lceil 
m/2\rceil}$, В ТАКОМ СЛУЧАЕ ДЕРЕВО СТАНОВИТСЯ НА ЕДИНИЦУ ВЫШЕ.

юПИСАННАЯ ПРОЦЕДУРА ВСТАВКИ СОХРАНЯЕТ ВСЕ СВОЙСТВА $B\hbox{-ДЕРЕВЬЕВ}$; ЧТОБЫ 
ОЦЕНИТЬ ВСЮ КРАСОТУ ИДЕИ, ЧИТАТЕЛЬ ДОЛЖЕН ВЫПОЛНИТЬ УПР.~1. чАМЕТЬТЕ, 
ЧТО ДЕРЕВО МАЛО-ПОМАЛУ РАСТЕТ ВВЕРХ ОТ ВЕРХНЕЙ ЧАСТИ, А НЕ ВНИЗ ОТ НИЖНЕЙ 
ЧАСТИ, ТАК КАК ЕДИНСТВЕННАЯ ПРИЧИНА, СПОСОБНАЯ ВЫЗВАТЬ РОСТ 
ДЕРЕВА,---РАСЩЕПЛЕНИЕ КОРНЯ.

єДАЛЕНИЯ ИЗ $B\hbox{-ДЕРЕВЬЕВ}$ ЛИШЬ НЕМНОГИМ СЛОЖНЕЕ ВСТАВОК (СМ. УПР.~7).

\section уАРАНТИРОВАННАЯ ЭФФЕКТИВНОСТЬ. ЁАССМОТРИМ, К СКОЛЬКИМ УЗЛАМ БУДЕТ 
ПРОИСХОДИТЬ ОБРАЩЕНИЕ В НАИХУДШЕМ СЛУЧАЕ ПРИ ПОИСКЕ В $B\hbox{-ДЕРЕВЕ}$ 
ПОРЯДКА $m$. яРЕДПОЛОЖИМ, ЧТО ИМЕЕТСЯ $N$ КЛЮЧЕЙ, А НА УРОВНЕ $l$ РАСПОЛОЖЕНО 
$N+1$ ЛИСТЬЕВ. ЄОГДА ЧИСЛО УЗЛОВ НА УРОВНЯХ 1, 2, 3, \dots НЕ МЕНЕЕ 2, 
$2\lceil m/2\rceil$,  $2\lceil m/2\rceil^2$, \dots; СЛЕДОВАТЕЛЬНО,
$$
N+1\ge 2\lceil m/2\rceil^{l-1}.
\eqno (5)
$$

шНЫМИ СЛОВАМИ,
$$
l\le 1+\log_{\lceil m/2\rceil}\left({N+1\over2}\right);
\eqno(6)
$$
ЭТО ОЗНАЧАЕТ, НАПРИМЕР, ЧТО ПРИ $N=1999998$ И $m=199$ ИМЕЕМ $l \le  3$. 
ЄАК КАК ПРИ ПОИСКЕ ПРОИСХОДИТ ОБРАЩЕНИЕ САМОЕ БОЛЬШЕЕ К $l$ УЗЛАМ, ЭТА 
ФОРМУЛА ГАРАНТИРУЕТ МАЛОЕ ВРЕМЯ РАБОТЫ АЛГОРИТМА.

яРИ ВСТАВКЕ НОВОГО КЛЮЧА МОЖЕТ ПОНАДОБИТЬСЯ РАСЩЕПИТЬ $l$ УЗЛОВ. юДНАКО 
СРЕДНЕЕ ЧИСЛО РАСЩЕПЛЯЕМЫХ УЗЛОВ МНОГО МЕНЬШЕ, ТАК КАК ОБЩЕЕ КОЛИЧЕСТВО 
РАСЩЕПЛЕНИЙ ПРИ ПОСТРОЕНИИ ДЕРЕВА РОВНО НА ЕДИНИЦУ МЕНЬШЕ КОЛИЧЕСТВА 
УЗЛОВ, КОТОРОЕ МЫ ОБОЗНАЧИМ ЧЕРЕЗ $p$. т ДЕРЕВЕ НЕ МЕНЕЕ 
$1 + (\lceil m/2\rceil-1) (p-1)$
%% 567
КЛЮЧЕЙ; СЛЕДОВАТЕЛЬНО,
$$
p\le 1+{N-1\over \ceil{m/2}-1}.
\eqno(7)
$$
¤ТО ОЗНАЧАЕТ, ЧТО СРЕДНЕЕ ЧИСЛО РАСЩЕПЛЕНИЙ, ТРЕБУЮЩИХСЯ НА ОДНУ ВСТАВКУ, 
МЕНЬШЕ~$1/(\ceil{m/2}-1)$.

\section єЛУЧШЕНИЯ И ИЗМЕНЕНИЯ. яРЕДЛОЖЕННЫЕ МЕТОДЫ МОЖНО УЛУЧШИТЬ, ЕСЛИ 
СЛЕГКА ИЗМЕНИТЬ ОПРЕДЕЛЕНИЕ $B\hbox{-ДЕРЕВА}$. яРЕЖДЕ.ВСЕГО ЗАМЕТИМ, ЧТО 
ВСЕ УКАЗАТЕЛИ В УЗЛАХ НА УРОВНЕ~$l-1$ РАВНЫ~$\NULL$ И НЕ РАВНЫ~$\NULL$ НА 
ДРУГИХ УРОВНЯХ. ¤ТО ЧАСТО ПРЕДСТАВЛЯЕТ СОБОЙ ЗНАЧИТЕЛЬНУЮ ПОТЕРЮ 
ПРОСТРАНСТВА, И МЫ МОЖЕМ СЭКОНОМИТЬ КАК ПРОСТРАНСТВО, ТАК И ВРЕМЯ, ЕСЛИ 
ИСКЛЮЧИМ ВСЕ~$\NULL$ И БУДЕМ ИСПОЛЬЗОВАТЬ ДЛЯ ВСЕХ НИЖНИХ УЗЛОВ ДРУГОЕ 
ЗНАЧЕНИЕ~$m$. шСПОЛЬЗОВАНИЕ ДВУХ РАЗЛИЧНЫХ~$m$ НЕ УХУДШАЕТ АЛГОРИТМА 
ВСТАВКИ, ТАК КАК ОБЕ ПОЛОВИНКИ РАСЩЕПЛЕННОГО УЗЛА ОСТАЮТСЯ НА ТОМ ЖЕ 
УРОВНЕ, ЧТО И ПЕРВОНАЧАЛЬНЫЙ УЗЕЛ. ьОЖНО ОПРЕДЕЛИТЬ ОБОБЩЕННОЕ 
$B\hbox{-ДЕРЕВО}$ ПОРЯДКОВ~$m_1$, $m_2$, $m_3$,~\dots, ПОТРЕБОВАВ, ЧТОБЫ 
ВСЕ НЕКОРНЕВЫЕ УЗЛЫ НА УРОВНЕ~$l-i$ ИМЕЛИ ОТ~$m_i/2$ ДО~$m_i$ ПРЕЕМНИКОВ; 
У ПОДОБНОГО $B\hbox{-ДЕРЕВА}$ СВОЕ~$m$ ДЛЯ КАЖДОГО УРОВНЯ, ОДНАКО АЛГОРИТМ 
ВСТАВКИ РАБОТАЕТ, В СУЩНОСТИ, ПО-ПРЕЖНЕМУ.

ЁАЗВИВАЯ ИДЕЮ ПРЕДЫДУЩЕГО АБЗАЦА, МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ СОВЕРШЕННО РАЗНЫЕ 
ФОРМАТЫ УЗЛОВ ДЛЯ РАЗНЫХ УРОВНЕЙ ДЕРЕВА, МОЖЕМ, КРОМЕ ТОГО, ХРАНИТЬ В 
ЛИСТЬЯХ ИНФОРМАЦИЮ. шНОГДА КЛЮЧИ СОСТАВЛЯЮТ ЛИШЬ НЕБОЛЬШУЮ ЧАСТЬ ЗАПИСЕЙ, 
И В ТАКИХ СЛУЧАЯХ БЫЛО БЫ ОШИБКОЙ ХРАНИТЬ ЗАПИСИ ЦЕЛИКОМ В УЗЛАХ, БЛИЗКИХ 
К КОРНЮ; ЭТО ПРИВЕЛО БЫ К СЛИШКОМ МАЛОМУ ЗНАЧЕНИЮ~$m$ И НЕ ДАЛО БЫ 
ЭФФЕКТИВНОГО РАЗВЕТВЛЕНИЯ.

єМЕСТНО ПОЭТОМУ СНОВА РАССМОТРЕТЬ РИС.~30, ПРЕДСТАВЛЯЯ СЕБЕ, ЧТО ВСЕ 
ЗАПИСИ ФАЙЛА ХРАНЯТСЯ ТЕПЕРЬ В ЛИСТЬЯХ И ЧТО ЛИШЬ НЕСКОЛЬКО КЛЮЧЕЙ 
ПРОДУБЛИРОВАНО В ОСТАЛЬНЫХ УЗЛАХ. т ТАКОМ СЛУЧАЕ САМЫЙ ЛЕВЫЙ ЛИСТ СОДЕРЖИТ 
ВСЕ ЗАПИСИ С КЛЮЧАМИ $\le011$;
ЛИСТ, ОТМЕЧЕННЫЙ БУКВОЙ~$A$, СОДЕРЖИТ ЗАПИСИ, КЛЮЧИ КОТОРЫХ УДОВЛЕТВОРЯЮТ 
СООТНОШЕНИЮ~$439<K\le 449$, И~Т.~П. ыИСТЬЯ РАСТУТ И РАСЩЕПЛЯЮТСЯ, КАК 
ДРУГИЕ УЗЛЫ, НО С ТОЙ СУЩЕСТВЕННОЙ РАЗНИЦЕЙ, ЧТО ЗАПИСИ НЕ ПЕРЕМЕЩАЮТСЯ 
ИЗ ЛИСТЬЕВ ВВЕРХ НА СЛЕДУЮЩИЙ УРОВЕНЬ. ЄАКИМ ОБРАЗОМ, ЛИСТЬЯ ВСЕГДА 
ЗАПОЛНЕНЫ НЕ МЕНЕЕ ЧЕМ НАПОЛОВИНУ; ПРИ ИХ РАСЩЕПЛЕНИИ В "НЕЛИСТОВУЮ" 
ЧАСТЬ ДЕРЕВА ПОСТУПАЕТ НОВЫЙ КЛЮЧ. хСЛИ КАЖДЫЙ ЛИСТ СВЯЗАН СО СВОИМ 
ПРЕЕМНИКОМ ОТНОШЕНИЕМ- СИММЕТРИЧНОГО ПОРЯДКА, МЫ ПОЛУЧАЕМ ВОЗМОЖНОСТЬ 
ЭФФЕКТИВНО И УДОБНО ОБХОДИТЬ ФАЙЛ КАК ПОСЛЕДОВАТЕЛЬНО, ТАК И СЛУЧАЙНЫМ ОБРАЗОМ.

эЕКОТОРЫЕ ВЫЧИСЛЕНИЯ ё.~я.~уХОША И~ь.~X.~ёЕНКО 
[{\sl JACM,\/} {\bf 16} (1969), 569--579] НАВОДЯТ НА МЫСЛЬ О ТОМ, ЧТО 
ПОЛЕЗНО ИМЕТЬ ДОВОЛЬНО БОЛЬШИЕ ЛИСТЬЯ; СКАЖЕМ ДО~10 ПОСЛЕДОВАТЕЛЬНЫХ 
СТРАНИЦ В ДЛИНУ. чНАЯ ДИАПАЗОН КЛЮЧЕЙ ДЛЯ КАЖДОГО ЛИСТА, С ПОМОЩЬЮ
%%568
ЛИНЕЙНОЙ ИНТЕРПОЛЯЦИИ МОЖНО ПРЕДУГАДАТЬ, КАКАЯ ИЗ 10~СТРАНИЦ 
СОДЕРЖИТ ДАННЫЙ АРГУМЕНТ ПОИСКА. хСЛИ ДОГАДКА ОКАЖЕТСЯ НЕВЕРНОЙ, МЫ 
ПОТЕРЯЕМ ВРЕМЯ, НО ЭКСПЕРИМЕНТЫ ПОКАЗЫВАЮТ, ЧТО ЭТА ПОТЕРЯ МОЖЕТ БЫТЬ 
МЕНЬШЕ, ЧЕМ ЭКОНОМИЯ ВРЕМЕНИ ОТ УМЕНЬШЕНИЯ РАЗМЕРА ДЕРЕВА.

Є.~X.~ьАРТИН (НЕ ОПУБЛИКОВАНО) УКАЗАЛ НА ТО, ЧТО ИДЕЯ, ЛЕЖАЩАЯ В ОСНОВЕ 
$B\hbox{-ДЕРЕВЬЕВ}$, ПОЛЕЗНА ТАКЖЕ ПРИ РАБОТЕ С КЛЮЧАМИ \emph{ПЕРЕМЕННОЙ 
ДЛИНЫ}. эЕТ НУЖДЫ ЗАКЛЮЧАТЬ ЧИСЛО СЫНОВЕЙ КАЖДОГО УЗЛА В ПРЕДЕЛЫ~$[m/2, 
m]$; ВМЕСТО ЭТОГО МОЖНО ПРОСТО СКАЗАТЬ, ЧТО КАЖДЫЙ УЗЕЛ ДОЛЖЕН БЫТЬ 
ЗАПОЛНЕН ДАННЫМИ НЕ МЕНЕЕ ЧЕМ НАПОЛОВИНУ. ьЕХАНИЗМ ВСТАВКИ И РАСЩЕПЛЕНИЯ 
РАБОТАЕТ ПО-ПРЕЖНЕМУ ПРЕВОСХОДНО, ХОТЯ ТОЧНОЕ ЧИСЛО КЛЮЧЕЙ В КАЖДОМ 
УЗЛЕ ЗАВИСИТ ОТ ИХ ДЛИН. юДНАКО НЕЛЬЗЯ ПОЗВОЛЯТЬ КЛЮЧАМ БЫТЬ СЛИШКОМ 
ДЛИННЫМИ (УПР.~5).

фРУГОЙ ВАЖНОЙ МОДИФИКАЦИЕЙ СХЕМЫ $B\hbox{-ДЕРЕВА}$ ЯВЛЯЕТСЯ 
ИДЕЯ "ПЕРЕЛИВАНИЯ", ВВЕДЕННАЯ сЭЙЕРОМ И~ьАК-ъРЭЙТОМ. юНА СОСТОИТ В ТОМ, 
ЧТОБЫ УЛУЧШИТЬ АЛГОРИТМ ВСТАВКИ ПУТЕМ УМЕНЬШЕНИЯ КОЛИЧЕСТВА РАСЩЕПЛЕНИЙ; 
ВМЕСТО НИХ ИСПОЛЬЗУЮТСЯ ЛОКАЛЬНЫЕ ПОВОРОТЫ. яУСТЬ ИМЕЕТСЯ ПЕРЕПОЛНЕННЫЙ 
УЗЕЛ, СОДЕРЖАЩИЙ $m$~КЛЮЧЕЙ И $m+1$~УКАЗАТЕЛЕЙ; ПРЕЖДЕ ЧЕМ РАСЩЕПЛЯТЬ ЭТОТ 
УЗЕЛ, СТОИТ ОБРАТИТЬ ВНИМАНИЕ НА ЕГО БРАТА СПРАВА, СОДЕРЖАЩЕГО, НАПРИМЕР, 
$j$~КЛЮЧЕЙ И $j+1$~УКАЗАТЕЛЕЙ. т УЗЛЕ-ОТЦЕ 
СУЩЕСТВУЕТ КЛЮЧ~$\overline{K}_f$, РАЗДЕЛЯЮЩИЙ КЛЮЧИ ЭТИХ фВУХ БРАТЬЕВ; 
СХЕМАТИЧЕСКИ ЭТО МОЖНО ИЗОБРАЗИТЬ ТАК:
\picture{ЁИС. СТР. 568}
яРИ $j<m-1$ ПРОСТОЕ ПЕРЕРАЗМЕЩЕНИЕ ДЕЛАЕТ РАСЩЕПЛЕНИЕ НЕНУЖНЫМ: МЫ 
ОСТАВЛЯЕМ $\ceil{(m+j)/2}$~КЛЮЧЕЙ В ЛЕВОМ УЗЛЕ, ЗАМЕНЯЕМ В 
УЗЛЕ-ОТЦЕ~$\overline{K}_f$ НА~$K_{\floor{(m+j)/2}+1}$,. А ОСТАЛЬНЫЕ КЛЮЧИ 
(ИХ $\ceil{(m+j)/2})$ И СООТВЕТСТВУЮЩИЕ УКАЗАТЕЛИ ПОМЕЩАЕМ В ПРАВЫЙ УЗЕЛ. 
ЄАКИМ ОБРАЗОМ, ИЗБЫТОК "ПЕРЕЛИВАЕТСЯ" В СОСЕДНИЙ УЗЕЛ. хСЛИ ЖЕ ОН БЫЛ 
ПОЛОН ($j=m-1$), МОЖНО РАСЩЕПИТЬ \emph{ОБА} УЗЛА, ПОЛУЧАЯ ТРИ ЗАПОЛНЕННЫХ 
ПРИМЕРНО НА ДВЕ ТРЕТИ УЗЛА, СОДЕРЖАЩИХ СООТВЕТСТВЕННО $\floor{(2m-2)/3}$,
 $\floor{(2m-1)/3}$ И $\floor{2m/3}$~КЛЮЧЕЙ:
\picture{ЁИС. СТР. 568}
%%569
хСЛИ У ИСХОДНОГО УЗЛА НЕТ ПРАВОГО БРАТА, УМЕСТНО ОПИСАННЫМ ОБРАЗОМ 
ИСПОЛЬЗОВАТЬ ЛЕВОГО. (хСЛИ ЖЕ СУЩЕСТВУЮТ ОБА БРАТА, МОЖНО ВОЗДЕРЖАТЬСЯ ОТ 
РАСЩЕПЛЕНИЯ, ПОКА ОБА НЕ ЗАПОЛНЯТСЯ.) эАКОНЕЦ, ЕСЛИ РАСЩЕПЛЯЕМЫЙ УЗЕЛ НЕ 
ИМЕЕТ БРАТЬЕВ, ТО ЭТО ОБЯЗАТЕЛЬНО КОРЕНЬ; МЫ МОЖЕМ ИЗМЕНИТЬ ОПРЕДЕЛЕНИЕ 
$B\hbox{-ДЕРЕВА}$, ДОПУСТИВ, ЧТОБЫ КОРЕНЬ СОДЕРЖАЛ ДО 
$2\floor{(2m-2)/3}$~КЛЮЧЕЙ, ТАК ЧТО ПРИ СВОЕМ РАСЩЕПЛЕНИИ ОН ПОРОЖДАЕТ ДВА 
УЗЛА, В КАЖДОМ ИЗ КОТОРЫХ $\floor{(2m-2)/3}$~КЛЮЧЕЙ.

яРИВЕДЕННЫЕ РАССУЖДЕНИЯ ПОЗВОЛЯЮТ "ВЫВЕСТИ НОВЫЙ, ЛУЧШИЙ ВИД" ДЕРЕВЬЕВ; 
НАЗОВЕМ ИХ $B^*\hbox{-ДЕРЕВЬЯМИ}$ И ОПРЕДЕЛИМ СЛЕДУЮЩИМ ОБРАЗОМ:

\medskip
\item{i)} ъАЖДЫЙ УЗЕЛ, КРОМЕ КОРНЯ, ИМЕЕТ НЕ БОЛЕЕ $m$~СЫНОВЕЙ.

\item{ii)} ъАЖДЫЙ УЗЕЛ, КРОМЕ КОРНЯ И ЛИСТЬЕВ, ИМЕЕТ НЕ МЕНЕЕ
$(2m-1)/3$~СЫНОВЕЙ.

\item{iii)} ъОРЕНЬ ИМЕЕТ НЕ МЕНЕЕ~2 И НЕ БОЛЕЕ $2\floor{(2m-2)/3}+1$~СЫНОВЕЙ.

\item{iv)} тСЕ ЛИСТЬЯ РАСПОЛОЖЕНЫ НА ОДНОМ УРОВНЕ.

\item{v)} єЗЛЫ, НЕ ЯВЛЯЮЩИЕСЯ ЛИСТЬЯМИ И ИМЕЮЩИЕ $k$~СЫНОВЕЙ, СОДЕРЖАТ 
$k-1$~КЛЮЧЕЙ.
\medskip

\noindent тАЖНОЕ ИЗМЕНЕНИЕ ДОСТАВЛЯЕТ УСЛОВИЕ (ii), УТВЕРЖДАЮЩЕЕ, ЧТО МЫ 
ИСПОЛЬЗУЕМ ПО КРАЙНЕЙ МЕРЕ ДВЕ ТРЕТИ ИМЕЮЩЕГОСЯ В КАЖДОМ УЗЛЕ 
ПРОСТРАНСТВА. ЄЕМ САМЫМ ЭКОНОМИТСЯ И ВРЕМЯ, ТАК. КАК В ФОРМУЛАХ~(6) И~(7) 
ВЕЛИЧИНУ "$\ceil{m/2}$" СЛЕДУЕТ ЗАМЕНИТЬ НА "$\ceil{(2m-1)/3}$".

тОЗМОЖНО, ЧИТАТЕЛЬ ОТНЕССЯ К $B\hbox{-ДЕРЕВЬЯМ}$ СКЕПТИЧЕСКИ ИЗ-ЗА ТОГО, 
ЧТО СТЕПЕНЬ КОРНЯ МОЖЕТ БЫТЬ РАВНА~2. чАЧЕМ ТРАТИТЬ ЦЕЛОЕ ОБРАЩЕНИЕ К 
ДИСКУ РАДИ РАЗВЕТВЛЕНИЯ ВСЕГО ЛИШЬ НА ДВА ПУТИ? яРОСТАЯ СХЕМА БУФЕРИЗАЦИИ, 
НАЗЫВАЕМАЯ "ЗАМЕЩЕНИЕМ ДОЛЬШЕ ВСЕГО НЕ ИСПОЛЬЗОВАВШЕЙСЯ СТРАНИЦЫ", 
ПОМОГАЕТ ПРЕОДОЛЕТЬ ЭТО НЕУДОБСТВО; МЫ МОЖЕМ ВЫДЕЛИТЬ ВО ВНУТРЕННЕЙ 
ПАМЯТИ НЕСКОЛЬКО БУФЕРОВ, ТАК ЧТО КОМАНДА РЕАЛЬНОГО ВВОДА БУДЕТ НЕ НУЖНА, 
ЕСЛИ СООТВЕТСТВУЮЩАЯ СТРАНИЦА УЖЕ ПРИСУТСТВУЕТ В ПАМЯТИ. яРИ ТАКОЙ СХЕМЕ 
АЛГОРИТМЫ ПОИСКА ИЛИ ВСТАВКИ ВЫПОЛНЯЮТ КОМАНДЫ "ВИРТУАЛЬНОГО ЧТЕНИЯ", 
КОТОРЫЕ НА САМОМ ДЕЛЕ ТРАНСЛИРУЮТСЯ В ИНСТРУКЦИИ ВВОДА, ЛИШЬ ЕСЛИ НУЖНОЙ 
СТРАНИЦЫ НЕТ В ПАМЯТИ; ПОСЛЕДУЮЩАЯ КОМАНДА "ОСВОБОЖДЕНИЯ" ВЫПОЛНЯЕТСЯ, 
КОГДА ИНФОРМАЦИЯ В БУФЕРЕ ОБРАБОТАНА И, ВОЗМОЖНО, ИЗМЕНЕНА АЛГОРИТМОМ. 
хСЛИ ТРЕБУЕТСЯ ДЕЙСТВИТЕЛЬНОЕ ЧТЕНИЕ, МЫ ВЫБИРАЕМ БУФЕР, ОСВОБОЖДЕННЫЙ 
РАНЕЕ ДРУГИХ, ЗАПИСЫВАЕМ ЕГО ОБРАТНО НА ДИСК, ЕСЛИ ОН ИЗМЕНИЛСЯ С МОМЕНТА 
СЧИТЫВАНИЯ, ЗАТЕМ В ВЫБРАННЫЙ БУФЕР СЧИТЫВАЕМ НУЖНУЮ СТРАНИЦУ.

ЄАК КАК ЧИСЛО УРОВНЕЙ ДЕРЕВА ОБЫЧНО МАЛО ПО СРАВНЕНИЮ. С ЧИСЛОМ БУФЕРОВ, 
ТАКАЯ СТРАНИЧНАЯ СИСТЕМА ОБЕСПЕЧИВАЕТ ПОСТОЯННОЕ ПРИСУТСТВИЕ В ПАМЯТИ 
КОРНЕВОЙ СТРАНИЦЫ; ТО ЖЕ САМОЕ
%%564
МОЖНО УТВЕРЖДАТЬ О СТРАНИЦАХ ПЕРВОГО УРОВНЯ, ЕСЛИ КОРЕНЬ ИМЕЕТ ДВА ИЛИ ТРИ 
СЫНА. ьОЖНО БЫЛО БЫ ВВЕСТИ СПЕЦИАЛЬНЫЙ МЕХАНИЗМ ДЛЯ ОБЕСПЕЧЕНИЯ 
ПОСТОЯННОГО ПРИСУТСТВИЯ ОПРЕДЕЛЕННОГО МИНИМАЛЬНОГО КОЛИЧЕСТВА БЛИЗКИХ К 
КОРНЮ СТРАНИЦ. чАМЕТЬТЕ, ЧТО ПРЕДЛОЖЕННАЯ СХЕМА АВТОМАТИЧЕСКИ 
ОБЕСПЕЧИВАЕТ ПРИСУТСТВИЕ В ПАМЯТИ СТРАНИЦ, НЕОБХОДИМЫХ ДЛЯ 
ВЫПОЛНЕНИЯ РАСЩЕПЛЕНИЙ, КОТОРЫЕ МОГУТ ПОНАДОБИТЬСЯ ПРИ ВСТАВКАХ.

ёУДЯ ПО ЭКСПЕРИМЕНТАМ, ПРОВЕДЕННЫМ ¤.~ьАК-ъРЭЙТОМ, ЭТА ИДЕЯ ОКАЗАЛАСЬ 
ВЕСЬМА УДАЧНОЙ. эАПРИМЕР, ОН ОБНАРУЖИЛ, ЧТО С ДЕСЯТЬЮ БУФЕРНЫМИ СТРАНИЦАМИ 
И~$m=121$ ПРОЦЕСС ВСТАВКИ В ВОЗРАСТАЮЩЕМ ПОРЯДКЕ 100000~КЛЮЧЕЙ ПОТРЕБОВАЛ 
ЛИШЬ 22~ДЕЙСТВИТЕЛЬНЫЕ КОМАНДЫ ЧТЕНИЯ И 857~ДЕЙСТВИТЕЛЬНЫХ КОМАНД ЗАПИСИ; 
ТАКИМ ОБРАЗОМ, БОЛЬШАЯ ЧАСТЬ ДЕЙСТВИЙ ПРОИЗВОДИЛАСЬ ВО ВНУТРЕННЕЙ ПАМЯТИ. 
фАЛЕЕ, ДЕРЕВО СОДЕРЖАЛО ЛИШЬ 835~УЗЛОВ---РОВНО НА~1 БОЛЬШЕ МИНИМАЛЬНО 
ВОЗМОЖНОГО ЗНАЧЕНИЯ~$\ceil{100000/(m-1)}=834$, Т.~Е. ПАМЯТЬ ИСПОЛЬЗОВАЛАСЬ 
ПОЧТИ НА~100\%. фЛЯ ЭТОГО ЭКСПЕРИМЕНТА ьАК-ъРЭЙТ ПРИМЕНИЛ 
ТЕХНИКУ ПЕРЕЛИВАНИЯ, НО С РАСЩЕПЛЕНИЕМ НА ДВЕ ЧАСТИ, КАК В~(4), А НЕ НА 
ТРИ, КАК В~(9). (ёМ.~УПР.~3.)

т ДРУГОМ ЭКСПЕРИМЕНТЕ (ТОЖЕ С 10~БУФЕРАМИ, $m=121$ И ТОЙ ЖЕ ТЕХНИКОЙ 
ПЕРЕЛИВАНИЯ) ОН ВСТАВИЛ В ПЕРВОНАЧАЛЬНО ПУСТОЕ ДЕРЕВО 5000~КЛЮЧЕЙ В 
СЛУЧАЙНОМ ПОРЯДКЕ. яОЛУЧИЛОСЬ ДВУХУРОВНЕВОЕ ДЕРЕВО С 48~УЗЛАМИ (ПАМЯТЬ 
ИСПОЛЬЗОВАЛАСЬ НА~87\%), И ПОТРЕБОВАЛИСЬ 2762~ДЕЙСТВИТЕЛЬНЫЕ КОМАНДЫ 
СЧИТЫВАНИЯ И 2739~ДЕЙСТВИТЕЛЬНЫХ КОМАНД ЗАПИСИ. яОСЛЕ ЭТОГО 
1000~СЛУЧАЙНЫХ ПОИСКОВ 786~РАЗ ПРОИЗВОДИЛИ ДЕЙСТВИТЕЛЬНЫЕ, 
СЧИТЫВАНИЯ. ЄОТ ЖЕ ЭКСПЕРИМЕНТ \emph{БЕЗ} МЕТОДА ПЕРЕЛИВАНИЯ ПОСЛЕ 
2743~ДЕЙСТВИТЕЛЬНЫХ СЧИТЫВАНИЙ И 2800~ДЕЙСТВИТЕЛЬНЫХ ЗАПИСЕЙ ПРИВЕЛ К 
ДВУХУРОВНЕВОМУ ДЕРЕВУ С 62~УЗЛАМИ (67\% ИСПОЛЬЗОВАНИЯ ПАМЯТИ); 
1000~ПОСЛЕДОВАТЕЛЬНЫХ СЛУЧАЙНЫХ ПОИСКОВ ПОТРЕБОВАЛИ 836~ДЕЙСТВИТЕЛЬНЫХ 
СЧИТЫВАНИЙ. ¤ТО ПОКАЗЫВАЕТ НЕ ТОЛЬКО ЭФФЕКТИВНОСТЬ СТРАНИЧНОЙ СХЕМЫ, НО 
ТАКЖЕ ПОЛЕЗНОСТЬ ЛОКАЛЬНОЙ ОБРАБОТКИ ПЕРЕПОЛНЕНИЯ ВМЕСТО НЕМЕДЛЕННОГО 
РАСЩЕПЛЕНИЯ. ¤НДРЮ ▀О ДОКАЗАЛ, ЧТО СРЕДНЕЕ ЧИСЛО УЗЛОВ ПОСЛЕ СЛУЧАЙНЫХ 
ВСТАВОК БЕЗ ПЕРЕЛИВАНИЯ ПРИ БОЛЬШИХ~$N$ И~$m$ 
СОСТАВИТ $N/(m\ln2)+O(N/m^2)$, ТАК ЧТО ПАМЯТЬ БУДЕТ ИСПОЛЬЗОВАТЬСЯ 
ПРИМЕРНО НА~$\ln 2=0.693$ [{\sl Acta Informatica,\/} БУДЕТ ОПУБЛИКОВАНО].

\excercises
\ex[10] ъАКОЕ $B\hbox{-ДЕРЕВО}$ ПОРЯДКА~7 ПОЛУЧИТСЯ ПОСЛЕ ВСТАВКИ 
КЛЮЧА~613 В ДЕРЕВО РИС.~30? (ьЕТОД ПЕРЕЛИВАНИЯ НЕ ПРИМЕНЯТЬ.)

\ex[15] тЫПОЛНИТЕ УПР.~1, ИСПОЛЬЗУЯ МЕТОД ПЕРЕЛИВАНИЯ С РАСЩЕПЛЕНИЕМ НА 
ТРИ ЧАСТИ, КАК В~(9).

\rex[23] яРЕДПОЛОЖИМ, ЧТО КЛЮЧИ 1, 2, 3,~\dots{} В ВОЗРАСТАЮЩЕМ 
ПОРЯДКЕ ВСТАВЛЯЮТСЯ В ПЕРВОНАЧАЛЬНО ПУСТОЕ $B\hbox{-ДЕРЕВО}$ ПОРЯДКА~101. 
ъАКОЙ КЛЮЧ ВПЕРВЫЕ ПРИВЕДЕТ К ПОЯВЛЕНИЮ ЛИСТЬЕВ НА УРОВНЕ 4: (a) ЕСЛИ НЕ 
ИСПОЛЬЗОВАТЬ
%%571
ПЕРЕЛИВАНИЯ; (b) ЕСЛИ ИСПОЛЬЗОВАТЬ ПЕРЕЛИВАНИЯ ЛИШЬ С РАСЩЕПЛЕНИЕМ НА ДВЕ 
ЧАСТИ, КАК В~(4); (c) ЕСЛИ ИСПОЛЬЗОВАТЬ $B^*\hbox{-ДЕРЕВЬЯ}$ ПОРЯДКА~101 С 
РАСЩЕПЛЕНИЕМ НА ТРИ ЧАСТИ, КАК В~(9)?

\ex[21] (сЭЙЕР И~ьАК-ъРЭЙТ.) юБоЯСНИТЕ, КАК ПРОИЗВОДИТЬ ВСТАВКИ В 
ОБОБЩЕННОЕ $B\hbox{-ДЕРЕВО}$, ЧТОБЫ ВСЕ УЗЛЫ, КРОМЕ КОРНЯ И ЛИСТЬЕВ, 
ИМЕЛИ НЕ МЕНЕЕ ${3\over4}m-{1\over2}$~ СЫНОВЕЙ.

\rex[21] яРЕДПОЛОЖИМ, ЧТО ПОД УЗЛЫ ОТВОДИТСЯ ПО 1000~БАЙТОВ ПОЗИЦИЙ ДЛЯ 
ЛИТЕР НА ВНЕШНЕЙ ПАМЯТИ. хСЛИ КАЖДАЯ ССЫЛКА ЗАНИМАЕТ 5~БАЙТОВ И ЕСЛИ КЛЮЧИ 
ИМЕЮТ ПЕРЕМЕННУЮ, НО КРАТНУЮ~5 ДЛИНУ ОТ~5 ДО~50 БАЙТОВ, ТО 
КАКОЕ МИНИМАЛЬНОЕ ЧИСЛО БАЙТОВ МОЖЕТ БЫТЬ ЗАНЯТО В УЗЛЕ ПОСЛЕ ЕГО 
РАСЩЕПЛЕНИЯ В ПРОЦЕССЕ ВСТАВКИ? (ЁАССМОТРИТЕ ЛИШЬ ПРОСТУЮ ПРОЦЕДУРУ 
РАСЩЕПЛЕНИЯ, АНАЛОГИЧНУЮ ОПИСАННОЙ В ТЕКСТЕ ДЛЯ $B\hbox{-ДЕРЕВЬЕВ}$ С 
КЛЮЧАМИ ФИКСИРОВАННОЙ ДЛИНЫ, БЕЗ ПЕРЕЛИВАНИЯ.)

\ex[22] ьОЖНО ЛИ ИСПОЛЬЗОВАТЬ ИДЕЮ $B\hbox{-ДЕРЕВА}$ ДЛЯ ВЫБОРКИ 
ЭЛЕМЕНТОВ ЛИНЕЙНОГО СПИСКА ПО ПОЗИЦИИ, А НЕ ПО ЗНАЧЕНИЮ КЛЮЧА? (ёР. С 
АЛГОРИТМОМ~6.2.3т.)

\ex[23] яРИДУМАЙТЕ АЛГОРИТМ УДАЛЕНИЯ ДЛЯ $B\hbox{-ДЕРЕВЬЕВ}$.

\ex[28] яРИДУМАЙТЕ АЛГОРИТМ КОНКАТЕНАЦИИ $B\hbox{-ДЕРЕВЬЕВ}$ (СР. С~П.~6.2.3).

\ex[30] юБДУМАЙТЕ, КАК БОЛЬШОЙ ФАЙЛ, ОРГАНИЗОВАННЫЙ В ВИДЕ 
$B\hbox{-ДЕРЕВА}$, МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ ДОСТУПА И ИЗМЕНЕНИЯ СО СТОРОНЫ 
БОЛЬШОГО ЧИСЛА ОДНОВРЕМЕННО РАБОТАЮЩИХ ПОЛЬЗОВАТЕЛЕЙ ТАК, ЧТОБЫ 
ПОЛЬЗОВАТЕЛИ РАЗЛИЧНЫХ СТРАНИЦ ПРАКТИЧЕСКИ НЕ СОЗДАВАЛИ ПОМЕХ ДРУГ ДРУГУ.

{\catcode`\!=\active\def!{\hfill}
\ex[ть37] ЁАССМОТРИМ ОБОБЩЕНИЕ ВСТАВКИ В ДЕРЕВО, ПРЕДЛОЖЕННОЕ ьЮНЦЕМ 
И~єЗГАЛИСОМ, КОГДА КАЖДАЯ СТРАНИЦА МОЖЕТ СОДЕРЖАТЬ $M$~КЛЮЧЕЙ. яУСТЬ МЫ 
ВСТАВИЛИ В ТАКОЕ ДЕРЕВО $N$~СЛУЧАЙНЫХ ЭЛЕМЕНТОВ; ТЕПЕРЬ ОНО ИМЕЕТ 
$N+1$~ВНЕШНИХ УЗЛОВ. юБОЗНАЧИМ ЧЕРЕЗ~$b^{(j)}_{Nk}$ ВЕРОЯТНОСТЬ ТОГО, ЧТО 
НЕУДАЧНЫЙ ПОИСК ТРЕБУЕТ ОБРАЩЕНИЙ К $k$~СТРАНИЦАМ И ЧТО ПРЕДШЕСТВЕННИК 
ТОГО ВНЕШНЕГО УЗЛА, ГДЕ КОНЧАЕТСЯ ПОИСК, ПРИНАДЛЕЖИТ К СТРАНИЦЕ, 
СОДЕРЖАЩЕЙ $j$~КЛЮЧЕЙ. яУСТЬ 
$B^{(j)}_N(z)=\sum b^{(j)}_{Nk} z^k$---СООТВЕТСТВУЮЩАЯ ПРОИЗВОДЯЩАЯ ФУНКЦИЯ. 
фОКАЖИТЕ, ЧТО
$$
\displaylines{
B^{(j)}_1(z)=\delta_{j1}z;\cr
B^{(j)}_N(z)={N-j-1\over N+1}B^{(j)}_{N-1}(z)+{j+1\over 
N+1}B^{(j-1)}_{N-1}(z),
\qquad 1<1<M;\cr
B^{(1)}_N(z)={N-2\over N+1}B^{(1)}_{N-1}(z)+{2z\over N+1}B^{(M)}_{N-1}(z);\cr
B^{(M)}_N(z)={N-1\over N+1}B^{(M)}_{N-1}(z)+{M+1\over N+1}B^{(M-1)}_{N-1}(z).\cr
}
$$
эАЙДИТЕ АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ 
$C'_N=\sum_{1\le j\le M} {B^{(j)}_N}'(1)$---СРЕДНЕГО ЧИСЛА СТРАНИЦ, К КОТОРЫМ 
ПРОИСХОДИТ ОБРАЩЕНИЕ В 
ПРОЦЕССЕ НЕУДАЧНОГО ПОИСКА. [\emph{єКАЗАНИЕ:} ВЫРАЗИТЬ РЕКУРРЕНТНОЕ 
СООТНОШЕНИЕ С ПОМОЩЬЮ МАТРИЦЫ
$$
W(z)=\pmatrix{
-3 & !0 & \ldots & !0! & !2z! \cr
!3 & -4 & \ldots & !0! & !0!\cr
!0 & !4 & \ldots & !0! & !0!\cr
!\vdots & !\vdots & & !\vdots! & !\vdots! \cr
!0 & !0 & \ldots & !-M-1! & !0!\cr
!0 & !0 & \ldots & !M+1 & -2! \cr
}
$$
И СОПОСТАВИТЬ $C'_N$ С МНОГОЧЛЕНОМ $N\hbox{-Й}$~СТЕПЕНИ В~$W(l)$.]
\par
}
%% 572

\bye