\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