\input style
\chapnotrue
\chapno=6
\subchno=2
\subsubchno=2
%% 536
\subsubchap{сБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ}
тОЛЬКО ЧТО ИЗУЧЕННЫЙ НАМИ АЛГОРИТМ ВСТАВКИ В ДЕРЕВО ПОРОЖДАЕТ ХОРОШИЕ 
ДЕРЕВЬЯ ПОИСКА ПРИ СЛУЧАЙНЫХ ИСХОДНЫХ ДАННЫХ, НО ВСЕ ЖЕ СУЩЕСТВУЕТ 
ДОСАДНАЯ ВЕРОЯТНОСТИ ПОЛУЧИТЬ ВЫРОЖДЕННОЕ ДЕРЕВО. вОЗМОЖНО, МЫ МОГЛИ БЫ 
ИЗОБРЕСТИ АЛГОРИТМ, КОТОРЫЙ В ЛЮБОМ СЛУЧАЕ ДАЕТ ОПТИМАЛЬНОЕ ДЕРЕВО, НО,
 К СОЖАЛЕНИЮ, ЭТО ДАЛЕКО НЕ ПРОСТО. дРУГОЙ ПОДХОД СОСТОИТ В ХРАНЕНИИ 
ПОЛНОЙ ДЛИНЫ ПУТИ И РЕОРГАНИЗАЦИИ ДЕРЕВА ВСЯКИЙ РАЗ, КОГДА ДЛИНА ЕГО ПУТИ 
ПРЕВЫШАЕТ, СКАЖЕМ, $5N\log_2N$. нО ТОГДА В ПРОЦЕССЕ ПОСТРОЕНИЯ ДЕРЕВА 
ПОТРЕБОВАЛОСЬ БЫ ОКОЛО $\sqrt{N/2}$ РЕОРГАНИЗАЦИЙ.

оЧЕНЬ ОСТРОУМНОЕ РЕШЕНИЕ ПРОБЛЕМЫ ПОДДЕРЖАНИЯ ХОРОШЕГО ДЕРЕВА ПОИСКА БЫЛО 
НАЙДЕНО В 1962~Г. ДВУМЯ СОВЕТСКИМИ МАТЕМАТИКАМИ---г.~м.~аДЕЛЬСОНОМ-вЕЛЬСКИМ 
И е. м. лАНДИСОМ [{\sl дан ссср\/}, {\bf 146} (1962), 263--266]. 
иХ МЕТОД ТРЕБУЕТ ЛИШЬ ДВУХ ДОПОЛНИТЕЛЬНЫХ БИТОВ НА УЗЕЛ И 
НИКОГДА НЕ ИСПОЛЬЗУЕТ БОЛЕЕ $O(\log N)$ ОПЕРАЦИЙ ДЛЯ ПОИСКА ПО ДЕРЕВУ ИЛИ 
ДЛЯ ВСТАВКИ ЭЛЕМЕНТА. в ДАЛЬНЕЙШЕМ МЫ УВИДИМ, ЧТО ЭТОТ ПОДХОД 
ТАКЖЕ ПРИВОДИТ К ОБЩЕМУ МЕТОДУ ПРЕДСТАВЛЕНИЯ ПРОИЗВОЛЬНЫХ ЛИНЕЙНЫХ 
\emph{СПИСКОВ} ДЛИНЫ $N$, ПРИЧЕМ КАЖДАЯ ИЗ СЛЕДУЮЩИХ ОПЕРАЦИЙ ТРЕБУЕТ ЛИШЬ 
$O(\log N)$ ЕДИНИЦ ВРЕМЕНИ:
\medskip
\item{i)} нАЙТИ ЭЛЕМЕНТ ПО ДАННОМУ КЛЮЧУ.
\item{ii)} пРИ ДАННОМ $k$ НАЙТИ $k$-Й ЭЛЕМЕНТ.
\item{iii)} вСТАВИТЬ В ОПРЕДЕЛЕННОМ МЕСТЕ ЭЛЕМЕНТ. 
\item{iv)} уДАЛИТЬ ОПРЕДЕЛЕННЫЙ ЭЛЕМЕНТ.
\medskip
\noindent еСЛИ ДЛЯ ЛИНЕЙНЫХ СПИСКОВ ПРИНЯТО ПОСЛЕДОВАТЕЛЬНОЕ РАСПОЛОЖЕНИЕ, 
ТО ОПЕРАЦИИ (i) И (ii) БУДУТ ЭФФЕКТИВНЫМИ, НО ОПЕРАЦИИ (iii) И (iv) 
ЗАЙМУТ ПОРЯДКА $N$ ШАГОВ; С ДРУГОЙ СТОРОНЫ, ПРИ ИСПОЛЬЗОВАНИИ СВЯЗАННОГО 
РАСПОЛОЖЕНИЯ ЭФФЕКТИВНЫ ОПЕРАЦИИ (iii) И (iv), А (i) И (ii) ПОТРЕБУЮТ 
ПОРЯДКА $N$ ШАГОВ. пРЕДСТАВЛЕНИЕ ЛИНЕЙНЫХ СПИСКОВ В ВИДЕ ДЕРЕВА ПОЗВОЛЯЕТ 
СДЕЛАТЬ \emph{ВСЕ ЧЕТЫРЕ} ОПЕРАЦИИ ЗА $O(\log N)$ ШАГОВ. мОЖНО ТАКЖЕ 
СРАВНИТЕЛЬНО ЭФФЕКТИВНО ПРОИЗВОДИТЬ ДРУГИЕ СТАНДАРТНЫЕ ОПЕРАЦИИ; 
НАПРИМЕР, ВОЗМОЖНА КОНКАТЕНАЦИЯ (СЦЕПЛЕНИЕ) СПИСКА ИЗ $м$ ЭЛЕМЕНТОВ СО 
СПИСКОМ ИЗ $N$ ЭЛЕМЕНТОВ ЗА $O(\log (м+N))$ ШАГОВ.

мЕТОД, ДАЮЩИЙ ВСЕ ЭТИ ПРЕИМУЩЕСТВА ИСПОЛЬЗУЕТ ТАК НАЗЫВАЕМЫЕ 
"СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ". пРЕДЫДУЩИЙ АБЗАЦ СЛУЖИТ РЕКЛАМОЙ 
СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ---ЭТАКОЙ ПАНАЦЕИ ОТ ВСЕХ БЕД; ПО СРАВНЕНИЮ С НИМИ 
ВСЕ ДРУГИЕ СПОСОБЫ ПРЕДСТАВЛЕНИЯ ДАННЫХ КАЖУТСЯ УСТАРЕВШИМИ. нО НЕОБХОДИМО 
СБАЛАНСИРОВАТЬ НАШЕ ОТНОШЕНИЕ К СБАЛАНСИРОВАННЫМ ДЕРЕВЬЯМ! еСЛИ 
ТРЕБУЮТСЯ НЕ ВСЕ. ЧЕТЫРЕ РАССМОТРЕННЫЕ ОПЕРАЦИИ, ТО НАС МОЖЕТ УДОВЛЕТВОРИТЬ
%% 537
ЗНАЧИТЕЛЬНО МЕНЕЕ УНИВЕРСАЛЬНЫЙ, НО ПРОЩЕ ПРОГРАММИРУЕМЫЙ МЕТОД. 
бОЛЕЕ ТОГО, СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ ХОРОШИ ЛИШЬ ПРИ ДОСТАТОЧНО БОЛЬШИХ 
$N$; ТАК. ЕСЛИ ЕСТЬ ЭФФЕКТИВНЫЙ АЛГОРИТМ, ТРЕБУЮЩИЙ $20\log_2N$ ЕДИНИЦ 
ВРЕМЕНИ, И НЕЭФФЕКТИВНЫЙ АЛГОРИТМ, ТРЕБУЮЩИЙ $2N$ ЕДИНИЦ ВРЕМЕНИ, ТО ПРИ 
$N<1024$ СЛЕДУЕТ ИСПОЛЬЗОВАТЬ НЕЭФФЕКТИВНЫЙ МЕТОД. с ДРУГОЙ СТОРОНЫ, $N$ 
НЕ ДОЛЖНО БЫТЬ СЛИШКОМ ВЕЛИКО; СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ ПОДХОДЯТ ГЛАВНЫМ 
ОБРАЗОМ ДЛЯ ХРАНЕНИЯ ДАННЫХ ВО \emph{ВНУТРЕННЕЙ} ПАМЯТИ, А В П.~6.2.4 МЫ 
ИЗУЧИМ ЛУЧШИЕ МЕТОДЫ ДЛЯ ВНЕШНИХ ФАЙЛОВ С ПРЯМЫМ ДОСТУПОМ. тАК КАК СО 
ВРЕМЕНЕМ РАЗМЕРЫ ВНУТРЕННЕЙ ПАМЯТИ СТАНОВЯТСЯ ВСЕ БОЛЬШЕ И БОЛЬШЕ, 
СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ СТАНОВЯТСЯ ВСЕ БОЛЕЕ ВАЖНЫМИ.

\dfn{вЫСОТА} ДЕРЕВА ОПРЕДЕЛЯЕТСЯ КАК ЕГО НАИБОЛЬШИЙ УРОВЕНЬ, КАК 
МАКСИМАЛЬНАЯ, ДЛИНА ПУТИ ОТ КОРНЯ ДО ВНЕШНЕГО УЗЛА.
\picture{20. сБАЛАНСИРОВАННОЕ БИНАРНОЕ ДЕРЕВО}
бИНАРНОЕ ДЕРЕВО НАЗЫВАЕТСЯ \dfn{СБАЛАНСИРОВАННЫМ}; ЕСЛИ ВЫСОТА ЛЕВОГО 
ПОДДЕРЕВА КАЖДОГО УЗЛА ОТЛИЧАЕТСЯ ОТ ВЫСОТЫ ПРАВОГО ПОДДЕРЕВА НЕ БОЛЕЕ ЧЕМ 
НА $\pm1$. нА РИС.~20 ПОКАЗАНО СБАЛАНСИРОВАННОЕ ДЕРЕВО С 17 ВНУТРЕННИМИ 
УЗЛАМИ И ВЫСОТОЙ 5; \dfn{ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ} ПРЕДСТАВЛЕН 
ВНУТРИ КАЖДОГО УЗЛА ЗНАКАМИ $+$, $\cdot$ ИЛИ $-$, ЧТО ОТВЕЧАЕТ РАЗНОСТИ 
ВЫСОТ ПРАВОГО И ЛЕВОГО ПОДДЕРЕВЬЕВ, РАВНОЙ $+1$, $0$ ИЛИ $-1$ 
СООТВЕТСТВЕННО. фИБОНАЧЧИЕВО ДЕРЕВО НА РИС.~8 (П~6.2.1) ЯВЛЯЕТСЯ ДРУГИМ 
СБАЛАНСИРОВАННЫМ БИНАРНЫМ ДЕРЕВОМ ВЫСОТЫ 5, ИМЕЮЩИМ ТОЛЬКО 12 ВНУТРЕННИХ 
УЗЛОВ; БОЛЬШИНСТВО ПОКАЗАТЕЛЕЙ СБАЛАНСИРОВАННОСТИ РАВНО $-1$. 
"зОДИАКАЛЬНОЕ ДЕРЕВО" НА РИС.~10 (П.~6.2.2) \emph{НЕ} СБАЛАНСИРОВАНО, ТАК 
КАК ПОДДЕРЕВЬЯ УЗЛОВ |AQUARIUS| И |GEMINI| НЕ УДОВЛЕТВОРЯЮТ ПРИНЯТЫМ 
ОГРАНИЧЕНИЯМ.

эТО ОПРЕДЕЛЕНИЕ СБАЛАНСИРОВАННОСТИ ПРЕДСТАВЛЯЕТ СОБОЙ КОМПРОМИСС МЕЖДУ 
\emph{ОПТИМАЛЬНЫМИ} БИНАРНЫМИ ДЕРЕВЬЯМИ (ВСЕ ВНЕШНИЕ УЗЛЫ КОТОРЫХ 
РАСПОЛОЖЕНЫ НА ДВУХ СМЕЖНЫХ УРОВНЯХ)
%% 538
И \emph{ПРОИЗВОЛЬНЫМИ} БИНАРНЫМИ ДЕРЕВЬЯМИ. пОЭТОМУ УМЕСТНО СПРОСИТЬ, 
КАК ДАЛЕКО МОЖЕТ ОТКЛОНИТЬСЯ ОТ ОПТИМАЛЬНОСТИ СБАЛАНСИРОВАННОЕ ДЕРЕВО? 
оКАЗЫВАЕТСЯ, ЧТО ДЛИНА ЕГО ПОИСКОВОГО ПУТИ .НИКОГДА НЕ ПРЕВЫСИТ ОПТИМУМ 
БОЛЕЕ ЧЕМ НА 45\%.

\proclaim тЕОРЕМА а. (г. м. аДЕЛЬСОН-вЕЛЬСКИЙ И е. м. лАНДИС). 
вЫСОТА СБАЛАНСИРОВАННОГО ДЕРЕВА С $N$ ВНУТРЕННИМИ УЗЛАМИ ЗАКЛЮЧЕНА МЕЖДУ 
$\log_2(N+1)$ И $1.4404 \log_2(N+ 2)-0.328$.

\proof\ бИНАРНОЕ ДЕРЕВО ВЫСОТЫ $h$, ОЧЕВИДНО, НЕ МОЖЕТ СОДЕРЖАТЬ БОЛЕЕ ЧЕМ 
$2^h$ ВНЕШНИХ УЗЛОВ; ПОЭТОМУ $N+1\le 2^h$, Т.Е. 
$h\ge \lceil \log_2(N+1)\rceil$.

чТОБЫ НАЙТИ МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ $h$, ПОСТАВИМ ВОПРОС ПО-ДРУГОМУ: КАКОВО 
МИНИМАЛЬНОЕ ЧИСЛО УЗЛОВ В СБАЛАНСИРОВАННОМ ДЕРЕВЕ ВЫСОТЫ $h$? пУСТЬ 
$T_h$--- ТАКОЕ ДЕРЕВО С НАИМЕНЬШИМ ВОЗМОЖНЫМ КОЛИЧЕСТВОМ УЗЛОВ; ТОГДА ОДНО 
ПОДДЕРЕВО КОРНЯ, НАПРИМЕР ЛЕВОЕ, ИМЕЕТ ВЫСОТУ $h-1$, А ДРУГОЕ---ИЛИ $h-1$, 
ИЛИ $h-2$. в СИЛУ ОПРЕДЕЛЕНИЯ $T_h$ МОЖНО СЧИТАТЬ, ЧТО ЛЕВОЕ ПОДДЕРЕВО 
КОРНЯ ЕСТЬ $T_{h-1}$, А ПРАВОЕ---$T_{h-2}$. тАКИМ ОБРАЗОМ, СРЕДИ ВСЕХ 
СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ ВЫСОТЫ $h$ НАИМЕНЬШЕЕ КОЛИЧЕСТВО УЗЛОВ ИМЕЕТ 
\emph{ФИБОНАЧЧИЕВО ДЕРЕВО} ПОРЯДКА $h+1$. (сМ. ОПРЕДЕЛЕНИЕ ДЕРЕВЬЕВ 
фИБОНАЧЧИ В П.~6.2.1.) иТАК,
$$
N\ge F_{h+2}-1 > \phi^{h+2}/\sqrt{5}-2,
$$
И ТРЕБУЕМЫЙ РЕЗУЛЬТАТ ПОЛУЧАЕТСЯ ТАК ЖЕ, КАК СЛЕДСТВИЕ ИЗ ТЕОРЕМЫ 4.5.3F. \proofend

мЫ ВИДИМ, ЧТО ПОИСК В СБАЛАНСИРОВАННОМ ДЕРЕВЕ ПОТРЕБУЕТ БОЛЕЕ 25 СРАВНЕНИЙ,
 ТОЛЬКО ЕСЛИ ДЕРЕВО СОСТОИТ ИЗ ПО КРАЙНЕЙ МЕРЕ $F_{27}-1= 196417$ УЗЛОВ.

рАССМОТРИМ ТЕПЕРЬ, ЧТО ПРОИСХОДИТ, КОГДА НОВЫЙ УЗЕЛ ВСТАВЛЯЕТСЯ В 
СБАЛАНСИРОВАННОЕ ДЕРЕВО ПОСРЕДСТВОМ АЛГОРИТМА 6.2.2т. дЕРЕВО НА РИС.~20 
ОСТАЕТСЯ СБАЛАНСИРОВАННЫМ, ЕСЛИ НОВЫЙ УЗЕЛ ЗАЙМЕТ МЕСТО ОДНОГО ИЗ УЗЛОВ 
\leaf{4}, \leaf{5}, \leaf{Б}, \leaf{7}, \leaf{10} ИЛИ \leaf{13}, НО 
В ДРУГИХ СЛУЧАЯХ ПОТРЕБУЕТСЯ НЕКОТОРАЯ КОРРЕКТИРОВКА. тРУДНОСТИ 
ВОЗНИКАЮТ, ЕСЛИ ИМЕЕТСЯ УЗЕЛ С ПОКАЗАТЕЛЕМ СБАЛАНСИРОВАННОСТИ $+1$, 
ПРАВОЕ ПОДДЕРЕВО КОТОРОГО ПОСЛЕ ВСТАВКИ СТАНОВИТСЯ ВЫШЕ, ИЛИ ЕСЛИ 
ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ РАВЕН $-1$ И ВЫШЕ. СТАНОВИТСЯ ЛЕВОЕ 
ПОДДЕРЕВО. лЕГКО ПОНЯТЬ, ЧТО, В СУЩНОСТИ, НАС БЕСПОКОЯТ ЛИШЬ ДВА СЛУЧАЯ:
\picture{сЛУЧАИ ВСТАВКИ В авл-ДЕРЕВО}
%% 539
(дРУГИЕ "ПЛОХИЕ" СЛУЧАИ МОЖНО ПОЛУЧИТЬ, ЗЕРКАЛЬНО ОТРАЗИВ ЭТИ ДИАГРАММЫ 
ОТНОСИТЕЛЬНО ВЕРТИКАЛЬНОЙ ОСИ.) бОЛЬШИМИ ПРЯМОУГОЛЬНИКАМИ $\alpha$, 
$\beta$, $\gamma$, $\delta$ ОБОЗНАЧЕНЫ ПОДДЕРЕВЬЯ С СООТВЕТСТВУЮЩИМИ 
ВЫСОТАМИ. сЛУЧАЙ 1 ИМЕЕТ МЕСТО, ЕСЛИ НОВЫЙ ЭЛЕМЕНТ УВЕЛИЧИЛ ВЫСОТУ 
ПРАВОГО ПОДДЕРЕВА УЗЛА $B$ С~$h$ ДО~$h+1$, А СЛУЧАЙ 2---КОГДА НОВЫЙ ЭЛЕМЕНТ 
УВЕЛИЧИВАЕТ ВЫСОТУ ЛЕВОГО ПОДДЕРЕВА УЗЛА $B$. вО ВТОРОМ СЛУЧАЕ МЫ ИМЕЕМ 
ЛИБО $h=0$ (И ТОГДА САМ УЗЕЛ $X$ ЯВЛЯЕТСЯ НОВЫМ УЗЛОМ), ЛИБО УЗЕЛ $X$ 
ИМЕЕТ ДВА ПОДДЕРЕВА С СООТВЕТСТВЕННЫМИ ВЫСОТАМИ $(h-1, h)$ ИЛИ $(h,h--l).$

пРОСТЫЕ ПРЕОБРАЗОВАНИЯ ВОССТАНАВЛИВАЮТ БАЛАНС В ОБОИХ СЛУЧАЯХ, СОХРАНЯЯ В 
ТО ЖЕ ВРЕМЯ СИММЕТРИЧНЫЙ ПОРЯДОК УЗЛОВ $A$, $B$ И $X$.
\picture{пОВОРОТЫ}
в СЛУЧАЕ 1 МЫ ПРОСТО ПОВОРАЧИВАЕМ ДЕРЕВО НАЛЕВО, ПРИКРЕПЛЯЯ $\beta$ К 
$A$ ВМЕСТО $B$. эТО ПРЕОБРАЗОВАНИЕ ПОДОБНО ПРИМЕНЕНИЮ АССОЦИАТИВНОГО 
ЗАКОНА К АЛГЕБРАИЧЕСКОЙ ФОРМУЛЕ, КОГДА МЫ ЗАМЕНЯЕМ $\alpha (\beta\gamma)$ 
НА $(\alpha\beta)\gamma$. в СЛУЧАЕ 2 ЭТО ПРОДЕЛЫВАЕТСЯ ДВАЖДЫ:
СНАЧАЛА $(X,B)$ ПОВОРАЧИВАЕТСЯ НАПРАВО, ЗАТЕМ $(A,X)$---НАЛЕВО. в ОБОИХ 
СЛУЧАЯХ НУЖНО ИЗМЕНИТЬ В ДЕРЕВЕ ЛИШЬ НЕСКОЛЬКО ССЫЛОК. дАЛЕЕ НОВЫЕ ДЕРЕВЬЯ 
ИМЕЮТ ВЫСОТУ $h+2$, В ТОЧНОСТИ ТУ ЖЕ, ЧТО И ДО ВСТАВКИ ЭЛЕМЕНТА; 
СЛЕДОВАТЕЛЬНО, ЧАСТЬ ДЕРЕВА, РАСПОЛОЖЕННАЯ НАД УЗЛОМ $A$ (ЕСЛИ ТАКОВАЯ 
ИМЕЕТСЯ), ОСТАЕТСЯ СБАЛАНСИРОВАННОЙ.
\picture{дЕРЕВО РИС. 20, СБАЛАНСИРОВАННОЕ ПОСЛЕ ВСТАВКИ НОВОГО КЛЮЧА R}

%% 540

нАПРИМЕР, ЕСЛИ МЫ ВСТАВЛЯЕМ НОВЫЙ УЗЕЛ НА МЕСТО \leaf{17} (РИС.~20), ТО 
ПОСЛЕ ПОВОРОТА ПОЛУЧИМ СБАЛАНСИРОВАННОЕ ДЕРЕВО, ИЗОБРАЖЕННОЕ НА РИС.~21 
(СЛУЧАЙ 1). зАМЕТЬТЕ, ЧТО НЕКОТОРЫЕ ИЗ ПОКАЗАТЕЛЕЙ СБАЛАНСИРОВАННОСТИ ИЗМЕНИЛИСЬ.

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

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

пРЕДПОЛАГАЕТСЯ (КАК И В АЛГОРИТМЕ 6.2.2т), ЧТО УЗЛЫ СОДЕРЖАТ ПОЛЯ |KEY|, 
|LLINK| И |RLINK|. кРОМЕ ТОГО, ИМЕЕТСЯ НОВОЕ ПОЛЕ
|B(P)| = ПОКАЗАТЕЛЬ СБАЛАНСИРОВАННОСТИ УЗЛА |NODE(P)|, Т. Е. РАЗНОСТЬ 
ВЫСОТ ПРАВОГО И ЛЕВОГО ПОДДЕРЕВЬЕВ; ЭТО ПОЛЕ ВСЕГДА СОДЕРЖИТ $+1$, $0$ 
ИЛИ~$-1$. пО АДРЕСУ |HEAD| РАСПОЛОЖЕН СПЕЦИАЛЬНЫЙ ГОЛОВНОЙ УЗЕЛ; |RLINK 
(HEAD)| УКАЗЫВАЕТ НА КОРЕНЬ ДЕРЕВА, a |LLINK (HEAD)| ИСПОЛЬЗУЕТСЯ ДЛЯ 
ХРАНЕНИЯ ПОЛНОЙ ВЫСОТЫ ДЕРЕВА. дЛЯ ДАННОГО АЛГОРИТМА ВЫСОТА НЕ ИМЕЕТ 
ЗНАЧЕНИЯ, НО ЗНАНИЕ ЕЕ ПОЛЕЗНО ДЛЯ ПРОЦЕДУРЫ КОНКАТЕНАЦИИ, 
ОБСУЖДАЮЩЕЙСЯ НИЖЕ. мЫ ПРЕДПОЛАГАЕМ, ЧТО ДЕРЕВО \emph{НЕПУСТО}, 
Т.~Е. ЧТО |RLINK (HEAD)\NE \NULL|.

в ЦЕЛЯХ УДОБСТВА ОПИСАНИЯ В АЛГОРИТМЕ ИСПОЛЬЗУЕТСЯ ОБОЗНАЧЕНИЕ 
|LINK (А, р)| КАК СИНОНИМ |LLINK (р)| ПРИ $А=-1$ И КАК СИНОНИМ |RLINK (р)| 
ПРИ $a=+1$.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ $|т|\asg |HEAD|$, 
$|S|\asg |P|\asg |RLINK (HEAD)|$. [уКАЗАТЕЛЬНАЯ ПЕРЕМЕННАЯ |P| БУДЕТ ДВИГАТЬСЯ 
ВНИЗ ПО ДЕРЕВУ; |S| БУДЕТ УКАЗЫВАТЬ НА МЕСТО, ГДЕ МОЖЕТ ПОТРЕБОВАТЬСЯ 
БАЛАНСИРОВКА; |T| ВСЕГДА УКАЗЫВАЕТ НА ОТЦА |S|.]

\st[сРАВНЕНИЕ.] еСЛИ $K<|KEY(P)|$, ТО ПЕРЕЙТИ НА \stp{3}; 
ЕСЛИ $K>|KEY(P)|$, ТО ПЕРЕЙТИ НА \stp{4}; ЕСЛИ $K=|KEY(P)|$, ПОИСК УДАЧНО ЗАВЕРШЕН.
\st[шАГ ВЛЕВО.] уСТАНОВИТЬ $|Q|\asg |LLINK (р)|$. еСЛИ $|Q|=|\NULL|$, ВЫПОЛНИТЬ 
$|Q|\Asg|AVAIL|$ И $|LLINK(P)|\asg|Q|$; ЗАТЕМ ИДТИ НА \stp{5}. в ПРОТИВНОМ 
СЛУЧАЕ, ЕСЛИ $|B(Q)|\NE|0|$, УСТАНОВИТЬ $|T|\asg|р|$ И $|S| \asg |Q|$. нАКОНЕЦ, 
УСТАНОВИТЬ $|P|\asg|Q|$ И ВЕРНУТЬСЯ НА \stp{2}.

\st[шАГ ВПРАВО.] уСТАНОВИТЬ $|Q|\asg |RLINK (р)|$. еСЛИ $|Q|=|\NULL|$, ВЫПОЛНИТЬ 
$|Q|\Asg|AVAIL|$ И $|RLINK (р)|\asg |Q|$; ЗАТЕМ ИДТИ НА \stp{5}.

%% 541
в ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ $|B|(|Q|)\NE 0$, УСТАНОВИТЬ $|т|\asg |р|$ И $|S|\asg |Q|$. 
нАКОНЕЦ, УСТАНОВИТЬ |P\asg Q| И ВЕРНУТЬСЯ НА \stp{2}. (пОСЛЕДНЮЮ ЧАСТЬ 
ЭТОГО ШАГА МОЖНО ОБЎЕДИНИТЬ С ПОСЛЕДНЕЙ ЧАСТЬЮ ШАГА \stp{3}.)

\st[вСТАВКА.] (мЫ ТОЛЬКО ЧТО ПРИСОЕДИНИЛИ НОВЫЙ УЗЕЛ |NODE (Q)| К ДЕРЕВУ; 
ТЕПЕРЬ ЕГО ПОЛЯ НУЖДАЮТСЯ В НАЧАЛЬНОЙ УСТАНОВКЕ.) уСТАНОВИТЬ    
$|KEY|(|Q|)\asg |K|$, 
$|LLINK(Q)|\asg |RLINK(Q)|\asg\NULL$, $|B(Q)|\asg 0$. 

\st[кОРРЕКТИРОВКА ПОКАЗАТЕЛЕЙ СБАЛАНСИРОВАННОСТИ.] (тЕПЕРЬ НУЛЕВЫЕ ПОКАЗАТЕЛИ 
СБАЛАНСИРОВАННОСТИ МЕЖДУ |S| И |Q| НУЖНО ЗАМЕНИТЬ НА $\pm1$.) еСЛИ 
$K<|KEY(S)|$, УСТАНОВИТЬ 
$|R|\asg |P| \asg |LLINK(S)|$;  В ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ 
$|R|\asg |р| \asg |RLINK(S)|$. зАТЕМ НУЖНО 0 ИЛИ БОЛЕЕ РАЗ ПОВТОРЯТЬ СЛЕДУЮЩУЮ 
ОПЕРАЦИЮ, ПОКА |P| НЕ СТАНЕТ РАВНЫМ |Q|: ЕСЛИ $K<|KEY(P)|$, УСТАНОВИТЬ 
$|B(P)|\asg -1$ И $|P|\asg |LLINK(P)|$;
ЕСЛИ $K > |KEY(P)|$, УСТАНОВИТЬ $|B(P)|\asg +1$  И $|P|\asg |RLINK (р)|$. (еСЛИ 
$K= |KEY(р)|$, ЗНАЧИТ, $|P|=|Q|$, И МОЖНО ПЕРЕЙТИ К СЛЕДУЮЩЕМУ ШАГУ.)

\st[пРОВЕРКА СБАЛАНСИРОВАННОСТИ.] еСЛИ $K<|KEY (S)|$, УСТАНОВИТЬ 
$a\asg -1$; В ПРОТИВНОМ СЛУЧАЕ $a\asg +1$. тЕПЕРЬ ВОЗМОЖНЫ ТРИ СЛУЧАЯ:

\medskip
\item{i)} еСЛИ $|в (S)| = 0$ (ДЕРЕВО СТАЛО ВЫШЕ), УСТАНОВИТЬ 
$|в (S)|\asg a$, $|LLINк (HEAD)| \asg  |LLINк(HEAD)| + 1$; АЛГОРИТМ 
ЗАВЕРШЕН.

\item{ii} еСЛИ $|B(S)|=-a$ (ДЕРЕВО СТАЛО БОЛЕЕ СБАЛАНСИРОВАННЫМ),
УСТАНОВИТЬ $|B(S)|\asg 0$; АЛГОРИТМ ЗАВЕРШЕН. 

\item{iii)} еСЛИ $|B(S)|=a$ (ДЕРЕВО ПЕРЕСТАЛО БЫТЬ СБАЛАНСИРОВАННЫМ), 
ПРИ $|B(R)|=a$ ИДТИ НА \stp{8}, ПРИ $|B(R)|=-a$ ИДТИ НА \stp{9}.
\medskip

\noindent(сЛУЧАЙ (iii) СООТВЕТСТВУЕТ СИТУАЦИИ, ИЗОБРАЖЕННОЙ НА ДИАГРАММЕ (1), 
ПРИ $a=+1$; |S| И |R| УКАЗЫВАЮТ СООТВЕТСТВЕННО
НА УЗЛЫ $A$ И $B$, a $|LINK|(-a, |S|)$ УКАЗЫВАЕТ НА $\alpha$ И Т.Д.) 

\st[оДНОКРАТНЫЙ ПОВОРОТ.] уСТАНОВИТЬ $|P|\asg |R|$, 
$|LINK| (a, |S|)\asg |LINK|(-a, |R|)$, $|LINK|(-a, |R|)\asg |S|$, 
$|B|(|S|)\asg |B|(|R|)\asg 0$. пЕРЕЙТИ НА \stp{10}.
\st[дВУКРАТНЫЙ ПОВОРОТ.] уСТАНОВИТЬ $|P|\asg |LINK|(-a, |R|)$, $|LINK|(-a, 
|R|)\asg |LINK|(a, |P|)$, $|LINK|(a, |P|)\asg |R|$, $|LINK|(a, 
|S|)\asg |LINK|(-a, |P|)$,  $|LINK|(-a, |P|)\asg |S|$. тЕПЕРЬ УСТАНОВИТЬ
$$
(|B|(|S|), |B|(|R|))\asg \cases{
(-a, 0), & ЕСЛИ $|B|(|P|)=a$;\cr
( 0, 0), & ЕСЛИ $|B|(|P|)=0$;\cr
(0, a),  & ЕСЛИ $|B|(|P|)=-a$;\cr
}
\eqno(3)
$$
ЗАТЕМ $|B|(|P|)\asg 0$. 

\st[пОСЛЕДНИЙ ШТРИХ.] [мЫ ЗАВЕРШИЛИ БАЛАНСИРУЮЩЕЕ 
ПРЕОБРАЗОВАНИЕ ОТ (1) К (2), |P| УКАЗЫВАЕТ НА НОВЫЙ КОРЕНЬ,
%% 542
А |т|---НА ОТЦА СТАРОГО КОРНЯ.] еСЛИ $|S|=|RLINK(T)|$, ТО УСТАНОВИТЬ   
$|RLINK(T)|\asg |P|$;   В   ПРОТИВНОМ   СЛУЧАЕ $|LLINK(T)|\asg |P|$. 
\algend

эТОТ АЛГОРИТМ ДОВОЛЬНО ДЛИННЫЙ, НО РАЗДЕЛЯЕТСЯ НА ТРИ ПРОСТЫЕ ЧАСТИ: ШАГИ 
а1--а4 (ПОИСК), ШАГИ а5--а7 (ВСТАВКА НОВОГО УЗЛА), ШАГИ а8--а10 
(БАЛАНСИРОВКА ДЕРЕВА, ЕСЛИ ОНА НУЖНА).
\picture{22. пОИСК С ВСТАВКОЙ ПО СБАЛАНСИРОВАННОМУ ДЕРЕВУ}

мЫ ЗНАЕМ, ЧТО ДЛЯ РАБОТЫ АЛГОРИТМА ТРЕБУЕТСЯ ОКОЛО $C\log N$ ЕДИНИЦ 
ВРЕМЕНИ ПРИ НЕКОТОРОМ $C$, НО ЧТОБЫ ЗНАТЬ, ПРИ КАКИХ $N$ ВЫГОДНО 
ИСПОЛЬЗОВАТЬ СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ, НУЖНО ОЦЕНИТЬ ВЕЛИЧИНУ $C$. 
аНАЛИЗ СЛЕДУЮЩЕЙ \MIX-ПРОГРАММЫ ПОЗВОЛЯЕТ ПОДОЙТИ К РЕШЕНИЮ ЭТОГО ВОПРОСА.
\prog а.(пОИСК С ВСТАВКОЙ ПО СБАЛАНСИРОВАННОМУ ДЕРЕВУ.) эТА РЕАЛИЗАЦИЯ 
АЛГОРИТМА а ИСПОЛЬЗУЕТ СЛЕДУЮЩИЙ ФОРМАТ УЗЛОВ ДЕРЕВА:
\picture{фОРМАТ УЗЛА авл-ДЕРЕВА}
%% 543
$|rA|\equiv K$, $|rI1|\equiv|P|$, $|rI2|\equiv |Q|$, $|rI3|\equiv |R|$, 
$|rI4|\equiv S$, $|rI5|\equiv |т|$. пРОГРАММА ДЛЯ ШАГОВ а7--а9 ДУБЛИРУЕТСЯ,
 ТАК ЧТО ВЕЛИЧИНА $a$ В ЯВНОМ ВИДЕ В ПРОГРАММЕ НЕ ФИГУРИРУЕТ.
\code
B     &EQU   &0:1
LLINK &EQU   &2:3
RLINK &EQU   &4:5
START &LDA   &к              &   1      &A1. нАЧАЛЬНАЯ УСТАНОВКА.
      &ENT5  &HEAD           &   1      &$|т|\asg |HEAD|$.
      &LD2   &0,5 (RLINK)    &   1      &$|Q|\asg |RLINK(HEAD)|$.
      &JMP   &2F             &   1      &нА а2 С $|S|\asg |P| \asg |Q|$
4н    &LD2   &0,1 (RLINK)    &  с2      &а4. шАГ ВПРАВО. $|Q|\asg |RLINK(P)|$
      &J2Z   &5F             &  с2      &нА а5, ЕСЛИ $|Q|=\NULL$.
1н    &LDX   &0,2 (в)        &  C-1     &$|rX|\asg |B(Q)|$.
      &JXZ   &*+3            &  C-1     &пЕРЕХОД, ЕСЛИ $|B(Q)|=0$.
      &ENT5  &0,1            &  D-1     &$|T|\asg |P|$.
2H    &ENT4  &0,2            &  D       &$|S|\asg |Q|$.
      &ENT1  &0,2            &  с       &$|P|\asg |Q|$.
      &CMPA  &1,1            &  с       &а2. сРАВНЕНИЕ.
      &JG    &4в             &  с       &нА а4,ЕСЛИ $K>|KEY(P)|$.
      &JE    &SUCCESS        &  с1      &вЫХОД, ЕСЛИ $к=|KEY(р)|$.
      &LD2   &0,1 (LLINK)    & C1-S     &A3. шАГ ВЛЕВО. $|Q|\asg |LLINK(р)|$.
      &J2NZ  &1в             & C1-S     &пЕРЕХОД, ЕСЛИ $|Q|\ne\NULL$.
\noalign{20--29 5н (СКОПИРОВАТЬ ЗДЕСЬ СТРОКИ 14---23 ПРОГРАММЫ 6.2.2 т)   а5. вСТАВКА.}
6H    &CMPA  &1,4            & 1-S      &A6. KoppeКТ. ПОКАЗАТ. СБАЛАНСИР.
      &JL    &*+3            & 1-S      &пЕРЕХОД, ЕСЛИ $K< |KEY(S)|$.
      &LDS   &0,4 (RLINK)    &  E       &$|R|\asg |RLINK(S)|$.
      &Jмр   &*+2            &  E
      &LD3   &0,4 (LLINK)    & 1-S-E    &$|R|\asg |LLINK(S)|$.
      &ENT1  &0,3            & 1-S      &$|P|\asg |R|$.
      &ENTX  &-1             & 1-S      &$|rX|\asg -1$.
      &JMP   &1F             & 1-S      &нА ЦИКЛ СРАВНЕНИЯ.
4н    &JE    &7F             &F2+1-S    &нА а7, ЕСЛИ $K=|KEY(P)|$.
      &STX   &0,1 (1:1)      &  F2      &$|B(P)|\asg +1$ (ОН БЫЛ $+0$).
      &LD1   &0,1 (RLINK)    &  F2      &$|P|\asg |RLINK(P)|$.
1н    &CMPA  &1,1            &F+1-S
      &JGE   &4B             &F+1-S     &пЕРЕХОД, ЕСЛИ $к \ge |KEY (P)|$.
      &STX   &0,1 (в)        &  F1      &$|в(р)|\asg -1$.
      &LD1   &0,1 (LLINK)    &  F1      &$|P|\asg |LLINK(P)|$.
      &JMP   &1B             &  F1      &нА ЦИКЛ СРАВНЕНИЯ.
7н    &LD2   &0,4(B)         & 1-S      &A7. пРОВЕРКА СБАЛАНСИР. $|rI2|\asg |B(S)|$.
      &STZ   &0,4 (в)        & 1-S      &$|B(S)|\asg 0$.
      &CMPA  &1,4            &1-S
      &JG    &A7R            &1-S       &нА $a=+1$ ПОДПРОГРАММУ,  ЕСЛИ $K>|KEY(S)|$.
\twocols
A7L & J2P  & DONE       & A7R  & J2N  & DONE       & 1-S & вЫХОД, ЕСЛИ $|rl2|=-a$.
    & J2Z  & 7F         &      & J2Z  & 6F         & G+J & пЕРЕХОД, ЕСЛИ |B(S)| БЫЛ НУЛЕМ.
    & ENT1 & 0,3        &      & ENT1 & 0,3        & G   & $|P|\asg|R|$.
    & LD2  & 0,3(в)     &      & LD2  & 0,3(в)     & G   & $|rI2|\asg |B(R)|$.
    & J2N  & A8L        &      & J2P  & A8R        & G   & нА. A8, ЕСЛИ $|rI2|=a$.
A9L & LD1  & 0,3(RLINK) & A9R  & LD1  & 0,3(LLINK) & H   & A9. дВУКРАТНЫЙ ПОВОРОТ.
    & LDX  & 0,1(LLINK) &      & LDX  & 0,1(RLINK) & H   & $|LINK|(a, |P|\asg |LINK|(-a, |R|))$
    & STX  & 0,3(RLINK) &      & STX  & 0,3(LLINK) & H   & $\rasg |LINK|(-a, |R|)$.
    & ST3  & 0,1(LLINK) &      & ST3  & 0,1(RLINK) & H   & $|LINK|(a, |P|)\asg|R|$.
    & LD2  & 0,1(B)     &      & LD2  & 0,1(B)     & H   & $|rI2|\asg|B|(|P|)$.
    & LDX  & T1,2       &      & LDX  & T2,2       & H   & $-a$, $0$ ИЛИ~$0$
    & STX  & 0,1(B)     &      & STX  & 0,4(B)     & H   & $\rasg |B|(|S|)$.
    & LDX  & T2,2       &      & LDX  & T1,2       & H   & $0$, $0$ ИЛИ~$a$
    & STX  & 0,3(B)     &      & STX  & 0,3(B)     & H   & $\rasg |B|(|R|)$
A8L & LDX  & 0,1(RLINK) & A8R  & LDX  & 0,1(LLINK) & G   & A8. оДНОКРАТНЫЙ ПОВОРОТ.
    & STX  & 0,4(LLINK) &      & STX  & 0,4(RLINK) & G   & $|LINK|(a, |S|)\asg |LINK|(-a, |P|)$.
    & ST4  & 0,1(RLINK) &      & ST4  & 0,1(LLINK) & G   & $|LINK|(-a, |P|)\asg|S|$.
    & JMP  & A8R1       & A8R1 & STZ  & 0,1(B)     & G   & $|B|(|P|)\asg 0$. 
\endtwocols
A10  & смр4 & 0,5(RLINK)   & G   & A10. пОСЛЕДНИЙ ШТРИХ.
     & JNE  & *+3          & G   & пЕРЕХОД, ЕСЛИ $|RLINK|(|T|)\ne |S|$.
     & ST1  & 0,5(RLINK)   & G2  & $|RLINK|(|T|)\asg|P|$.
     & JMP  & DONE         & G2  & вЫХОД.
     & ST1  & 0,5(LLINK)   & G1  & $|LLINK|(|T|)\asg|P|$.
     & JMP  & DONE         & G1  & вЫХОД.
     & CON  & +1
T1   & CON  & 0            &     & тАБЛИЦА ДЛЯ~(3).
T2   & CON  & 0
     & CON  & -1
6H   & ENTX & +1           & J2  & $|rX|\asg +1$.                        
7H   & STX  & 0,4(B)       & J   & $|B|(|S|)\asg a$.
     & LDX  & HEAD(LLINK) & J   & $|LLINK|(|HEAD|)$.
     & INCX & 1            & J   & $+1$
     & STX  & HEAD(LLINK)  & J   & $\rasg |LLINK|(|HEAD|)$.
DONE & EQU  & *            & 1-S & вСТАВКА ЗАВЕРШЕНА.
\endcode
\progend

\section аНАЛИЗ ВСТАВКИ В СБАЛАНСИРОВАННОЕ ДЕРЕВО.  [чИТАТЕЛИ, НЕ 
ИНТЕРЕСУЮЩИЕСЯ  МАТЕМАТИКОЙ, МОГУТ СРАЗУ ПЕРЕЙТИ К ФОРМУЛЕ~(10).] чТОБЫ 
ВЫЧИСЛИТЬ ВРЕМЯ РАБОТЫ АЛГОРИТМА~A, НУЖНО СНАЧАЛА ОТВЕТИТЬ НА СЛЕДУЮЩИЕ ВОПРОСЫ:
\itemize
\li сКОЛЬКО СРАВНЕНИЙ ПРОИЗВОДИТСЯ ВО ВРЕМЯ ПОИСКА?
\li кАК ДАЛЕКО ДРУГ ОТ ДРУГА БУДУТ НАХОДИТЬСЯ УЗЛЫ~|S| И~|Q|?
(иНЫМИ СЛОВАМИ, СКОЛЬКО НУЖНО ПРОИЗВЕСТИ КОРРЕКТИРОВОК В ШАГЕ~A6?)
\li кАК ЧАСТО НУЖНО ПРОИЗВОДИТЬ ОДНОКРАТНЫЙ ИЛИ ДВУКРАТНЫЙ ПОВОРОТ?
\itemend
\noindent вОСПОЛЬЗОВАВШИСЬ ТЕОРЕМОЙ~A, НЕТРУДНО ВЫВЕСТИ ВЕРХНЮЮ ОЦЕНКУ 
ВРЕМЕНИ РАБОТЫ, НО НАС, РАЗУМЕЕТСЯ, ИНТЕРЕСУЕТ СРЕДНИЙ УРОВЕНЬ. дО СИХ ПОР 
НЕ УДАЛОСЬ ТЕОРЕТИЧЕСКИ ОЦЕНИТЬ, КАК ВЕДЕТ СЕБЯ АЛГОРИТМ В СРЕДНЕМ, 
ПОСКОЛЬКУ ОН ОКАЗАЛСЯ ДОВОЛЬНО СЛОЖНЫМ, ОДНАКО БЫЛИ ПОЛУЧЕНЫ НЕКОТОРЫЕ 
ИНТЕРЕСНЫЕ ЭМПИРИЧЕСКИЕ РЕЗУЛЬТАТЫ.

%% 545

\bye