\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)-ДЕРЕВО ОБRЯСНИТЬ НЕСКОЛЬКО ЛЕГЧЕ, ЧЕМ ВСТАВКУ В
СБАЛАНСИРОВАННОЕ ДЕРЕВО. еСЛИ МЫ ХОТИМ ПОМЕСТИТЬ
\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] оБRЯСНИТЬ, ПОЧЕМУ ДЕРЕВО СТАЛО НА ОДИН УРОВЕНЬ ВЫШЕ, ЕСЛИ
МЫ ДОСТИГЛИ ШАГА~а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$ ПОЧТИ ЗАПОЛНЕН. эТА СХЕМА ТРЕБУЕТ
ДОВОЛЬНО СЛОЖНОЙ СИСТЕМЫ ПОВОРОТОВ, ТАК КАК ДЛЯ ВСТАВКИ ОДНОГО НОВОГО
ЭЛЕМЕНТА МОЖЕТ ПОТРЕБОВАТЬСЯ ОСНОВАТЕЛЬНАЯ ПЕРЕСТРОЙКА ДЕРЕВА;
лАНДАУЭР ИСХОДИЛ ИЗ ПРЕДПОЛОЖЕНИЯ, ЧТО ПОИСК ПРИХОДИТСЯ
ПРОИЗВОДИТЬ ГОРАЗДО ЧАЩЕ ВСТАВОК И УДАЛЕНИЙ.
еСЛИ ФАЙЛ ХРАНИТСЯ НА ДИСКЕ И ЯВЛЯЕТСЯ ОБRЕКТОМ СРАВНИТЕЛЬНО РЕДКИХ
ВСТАВОК И УДАЛЕНИЙ, ТО ДЛЯ ЕГО ПРЕДСТАВЛЕНИЯ ПОДХОДИТ ТРЕХУРОВНЕВОЕ
ДЕРЕВО, ГДЕ ПЕРВЫЙ УРОВЕНЬ РАЗВЕТВЛЕНИЯ ОПРЕДЕЛЯЕТ, КАКОЙ ЦИЛИНДР БУДЕТ
ИСПОЛЬЗОВАТЬСЯ, СЛЕДУЮЩИЙ УРОВЕНЬ РАЗВЕТВЛЕНИЯ ОПРЕДЕЛЯЕТ
СООТВЕТСТВУЮЩУЮ ДОРОЖКУ НА ЭТОМ ЦИЛИНДРЕ, А ТРЕТИЙ УРОВЕНЬ СОДЕРЖИТ СОБСТВЕННО
%% 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] (бЭЙЕР И~мАК-кРЭЙТ.) оБRЯСНИТЕ, КАК ПРОИЗВОДИТЬ ВСТАВКИ В
ОБОБЩЕННОЕ $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