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

� ������ ������� ��� ����� ������������ �����~$B_{nh}$ ���������������� 
�������� �������� � $n$~����������� ������ � �������~$h$. ��� 
���������~$h$ �� �����������
$$
B_0(z)=1,\quad B_1(z)=z,\quad B_{h+1}(z)=zB_h(z)(B_h(z)+2B_{h-1}(z))
\eqno(5)
$$
�������� ��������� ������������ �������~$B_h(z)=\sum_{n\ge0}B_{nh}z^n$ 
(��. ���.~6).  �� �������,
$$
\matrix{
B_2(z)=& 2z^2+z^3,&\cr
B_3(z)=&& 4z^4+6z^5+4z^6&+z_7\cr
B_4(z)=&&&16z^7&+32z^8+44z^9+\cdots+8z^{14}+z^{15},\cr
}
$$
� ������ $B_h(z)$ ��� $h\ge3$ ����� ���
$$
2^{F_{h+1}-1}z^{F_{h+2}-1}+2^{F_{h+1}-2}L_{h-1}z^{F_{h+2}}
+\hbox{������� �����}+2^{h-1}z^{2^h-2}+z^{2^h-1},
\eqno(6)
$$
��� $L_k=F_{k+1}+F_{k-1}$. (풀 ������� �������� �������~A.) 爑�� ���� 
���������������� �������� ������~$h$ ����� $B_h=B_h(1)$ � ������������� 
������������� �����������
$$
B_0=B_1=1,\quad B_{h+1}=B^2_h+2B_hB_{h-1},
\eqno(7)
$$
��� ��� $B_2=3$, $B_3=3\cdot5$, $B_4=3^2\cdot5\cdot7$, 
$B_5=3^3\cdot5^2\cdot7\cdot23$; � ����� ������
$$
B_h=A_0^{F_h}\cdot A_1^{F_h-1}\ldots A_{h-1}^{F_1}\cdot A_h^{F_0},
\eqno(8)
$$
��� $A_0=1$, $A_1=3$, $A_2=5$, $A_3=7$, $A_4=23$, $A_5=347$, \dots, 
$A_h=A_{h-1}B_{h-2}+2$. ������������������ $A_h$ � $B_h$ ������ 
����� ������, ��� "���������� ����������"; �� ���.~7 �������, 
��� ���������� �������������� ����� $\theta\approx1.43684$, �����, ���
$$
B_h=\floor{\theta^{2^h}}-\floor{\theta^{2^h-1}}+\floor{\theta^{2^h-2}}
-\cdots+(-1)^h\floor{\theta^{2^0}}.
\eqno(9)
$$
���� �������, ��� ��� $B_h$~�������� �������������, ��, ��� ���������� 
���.~8, ������� ����� ����� � ������ ������~$h$ �����
$$
B'_h(1)/B_h(1)\approx (0.70118)\cdot 2^h.
\eqno(10)
$$
풎 ��������, ��� ������ ����������������� ������ � $n$~������ ������ 
������� ����� �~$\log_2 n$, ��� �~$\log_\phi n$.

� ���������, ���������� ���������� �� ����� ��������� � ���������~A, ��� 
��� �������� ����� ��������� ������ ��������� ������� ������� ����� 
����������, ��� ������. ����������, ��������, ������~$N=7$, ����� 
���������� 17~���������������� ��������. ����� ����� ��������� $7!=5040$ 
���������� ���������, ��� ���� �������� ���������������� "�����������"
%%546
������
\picture{���. �� ���. 546}
���������� 2160~���. � ����������������� ����� ������������ ������
\picture{���. �� ���. 546}
����������� ���� 144~����, � ������� ������
\picture{���. �� ���. 546}
����������� 216~���. [������� ����� ���������� �~(12) �~(13) ������������� 
����������������� ��������� � �������� ������ � ����� ��������� ������� 
������������ ������������ ���, ������� 16~��������� ��������; ������ 
��������, ���������� ��~(12), ����������� �� 144~����, � ���������� 
��~(13)---�� 216~���. �������� �������, ��� (13) ����������� ����, ��� (12).]

⎒ ����, ��� �������� ���������������� ������� ���������� � ����� 
������� ������������---��������� � ��������~(10), ��������������� ������ 
������ ������������,---������ ����������� �������������� �����������: 
(������� ����� ��������� ��� ������ �� ����������������� ������)%
$\approx\log_2 N+c$, ��� $c$---����� ���������. �������������, ������������ 
�������� ����������, ��� ������� ����� ���������, ��������� ��� 
������� $N\hbox{-��}$ ��������, ��� �� ������� �����~$N$ �������� 
�����~$1.01\log_2 N+0.1$

璎�� ������� ��������� ���������~A �� ����� ������� � ������������, ����� 
���������������� ������� ���� ����������������� ������, ��� �������� �� 
���.~23. ����, ������� �� �������� ���� �����, ����������� 
������������������� ������ � ������� ("|+|" ��� ������ ������, "|-|" ��� 
�����); �� ���������� ��, ���� �� ��������� ������� ���� � ���������
%% 547
����������� ������������������ ��� (���� ����� ����� ���) ���� �� 
��������� �����. ����� �� ����� |A| ���~|B| � ������������ � ���, ����� 
�� ����� ������, ���������� ����� ������� �� ������ ����� ����������� ����,
 ���������������� ��� ���.  /���� �� (3) ����� ���������� |++-B|, ��� 
�������� "������ ������, ������ ������, ����� ������, 
����������������". ���� ��� ������������ ��~|A|, ����� ������� ������ ���� ��
\picture{
���. 23.���� �������������, ������������ ��������� ��������� A ����� �������.
}
��������� ������������; ���, �������������� ��~|++B| ���~|--B|, 
������� ������������ ��������, � ���, �������������� ��~|+-B| ���~|-+B|, 
������� ����������� ��������. ���� ���� ������� �� $k$~�������, � ����~A6 
�������������� ����� $k-1$~����������� ������������������.  �� �������, 
��������� ������������������ ���� ����������� ���������� � ������� ������ 
�����~A6--A10.

팏��������� �������� �� ���������� ������� � ��������� $100\le N\le2000$ 
���� ������������ ����������� ��� ����� ��������� ����� (����.~1); 
��������, ��� ����������� ������ ������������ � ���������� ��������� 
���~$N\to\infty$. � ����.~2 ���� ��������������� ������ ����������� 
($N=10$; ��� $10!$~������������ ��������� ���������������.)

�� ����.~1 �� �����, ��� ����������� �������~$k\le 2$ 
����� $0.144+0.153+0.144+0.144=0.585$; ����� �������, ����� � 60\%~������� 
���~A6 ���������. ᐅ���� ����� ��������� ������������� 
������������������ �� ���� ���� (0 ���������� ��~$\pm1$) �������� 
�����~$1.8$. ᐅ���� ����� ��������� ������������� ������������������ 
��~$\pm1$ ��~$0$ � �����~A7--A10 ����� $0.535+2(0.233+0.232)\approx1.5$,  
�.~�.~������� ������  ������ ���� ��������� � ������� 
$0.3$~������������������� ����. 풎 ����������� � ��� ������, ��� ����� 
68\% ���� ����� � ��������� ��������, ���������� � ������� ���������~A, ��������� 
�����������������.

%%548
{
\def\!#1{\overline{\mathstrut #1}}
\htable{ ���� 1}{������������ ����������� ��� ������� $N\hbox{-��}$ ��������}%
{#&\hfill$#$&&\bskip\hfill$#$\hfill\cr
 & \hbox{����� ����} &  \hbox{ ��� ������������} &  \hbox{ ����������� �������} & \hbox{���������� �������}\cr
\noalign{\hrule}
\mathstrut&1 & .144  &  .000  & .000  \cr
    &      2 & .153  &  .144  & .144  \cr
    &      3 & .093  &  .048  & .048  \cr
    &      4 & .058  &  .023  & .023  \cr
    &      5 & .036  &  .010  & .010  \cr
     &    >5 & .051  &  .008  & .007  \cr
ave&\!{2.78}&\!{.535}&\!{.233}&\!{.232}\cr
\noalign{\hrule}
}

\htable{ ���� 2}{⎗��� ����������� ��� ������� $10\hbox{-��}$ ��������}%
{#&\hfill$#$\hfill&&\bskip\hfill$#$\hfill\cr
 &\hbox{����� ����} &  \hbox{ ��� ������������} &  \hbox{ ����������� �������} & \hbox{���������� �������}\cr
\noalign{\hrule}
\mathstrut& 1  & 1/7      &  0       & 0     \cr
   &        2  & 6/35     &  1/7     & 1/7   \cr
   &        3  & 4/21     &  2/35    & 2/35  \cr
   &        4  &  0       &  1/21    & 1/21  \cr
ave&\!{247/105}&\!{53/105}&\!{26/105}&\!{26/105}\cr
\noalign{\hrule}
}
}

������������ ������ ��������� ���������~A ���� ���������� �.~�.~䎑����� 
[Proc. ACM Nat. Conf., {\bf 20}, (1965), 192--205]. ������ ��� �� ������ 
���������, �� ���������� ������ � ������, ����� �������� �������� ����. 
�����������, ��� � ������� ������, ����������� � ������� ���������~A, 
���������� ������������������ ������� ���� � ������������~$p$ �����~0; 
����� ���� ���������� �����~$+1$ � ������������~${1\over2}(1-p)$ �
� ��� �� ������������ �����~$-1$. ����������� ����� (��� ������ 
�����������), ��� ���������� ������������������ ���� ����� ����������. 
⎃�� ����������� ����, ��� ���~A6 ������ ���������� ����� 
$(k-1)$~�����������, �����~$p^{k-1}(1-p)$, ������� ������� ��������~$k$ 
����~$1/(1-p)$. ����������� ����, ���
����� ��������� ����� ������, �����~${1\over2}$. � ������� ������� ������ 
���� ������ ��������� ����� ���������������� ����� ��~$p$; ��� ����� � 
���������������� ������������� ��~1 � ����~A5, �� $-p1(1-�)$ � ����~A6, 
��~${1\over2}$ � ����~A7 � ��~${1\over2}\cdot2$ � ����~A8 ��� A9, ��� ��� 
�� ��������
$$
p=1-p/(1-p)+{1\over2}+1.
$$
%%549
������� ����� ��������� ������������~$p$ ���� �������� �������� � ����.~1:
$$
p={9-\sqrt{41}\over 4}\approx 0.649;\quad 1/(1-p)\approx 2.851.
\eqno(14)
$$

����� ������ ���� ������ ���������~A (������ 01--19) �����
$$
10C+C1+2D+2-3S,
\eqno(15)
$$
��� $C$, $C1$, $S$---�� �� �����, ��� � � ���������� ���������� ���� �����,
 a $D$---����� ������������������ �����, ���������� ��� ������. 
팏��������� �������� ����������, ��� �����
�������� $D\approx{1\over3}C$, $C1\approx{1\over2}(C+S)$,
$C+S\approx1.01\log_2N+0.1$, ���
��� ������� ����� ������ �������� ����� $11.3\log_2N+3-13.7S$~������. 
(���� ����� ������������ ������� ���� �������, �� ����� ��, ����������, 
������������ ���������, ����� ������� ��������� ������, ��� ��� �� ���� �� 
������������� ������� �� �������������� ������������������; � ���� ������ 
������� ����� ������ ��������� �� ���� $(6.6\log_2N+3)u$, � � ��������� 
������ ����� ������ ����� ��� �� ������, ��� ������� ����� ������ 
��������� 6.2.2�.)

���� ����� ��������, ����� ������ ���� ������� � ���������~� (������ 
20--45) ����� $8F+26+(0, 1\hbox{ ��� }2)$~������. ������ ����.~1 
����������, ��� � ������� $F\approx1.8$. 䀇� ������������ (������ 
46--101) ������� $16.5$, $8$, $27.5$ ��� $45.5(\pm0.5)$~������ � 
����������� �� ����, ����������� �� �� ������ ������, ������ �� ������� 
��� ������������ ��� �� ���������� ����������� ��� ���������� �������. 
������ ������ ����� �� �����������, � ������ ����������� � 
������������� ������������� $0.535$, $0.233$, $0.232$, ������� ������� 
����� ���������� ��������������� ���������-��������������� 
����� ���������~A ���������� �������� $63u$.

품 ����� ����������, ��� �������� ��� ����������������� ��������� 
�������� ������, ���� ��������� � �������� ����� ����� � ������. ���� 
�������� ������ �������� ����������, �� ������� �������� ������� � 
������ (�.~6.2.2) ���������� ���� ������� �������� �� $50u$~�������, �� 
������������� ���������������� �������� ����������� ������� ���������� 
���� ��� ����������� �������� ������.

���� �� �������� ��������� ���������~A � ���������� 6.2.2� ������� � 
������������ ���������� ��� ��������� ��������� ������. ���� �� 
�������������� ����������� �������, ����������� ��� ������� � ������������ 
������� $N$~������ � ������������� ������ ������, �� ��������, ��� 
���������~A ��������� ��� $N\le 26$ � ������� ��� $N\ge 27$.

%%550
\picture{���. 24. ���� RANK, ������������ ��� ������ �� �������.}

%% 551
\section ������������� ��������� ������. �������� ������ � ���������, 
���������� � ������ ����� ������, � ���, ��� ���������������� ������� 
����� �������������� ��� ������������� �������� ������� ����� �������, ��� 
����� ����� ������ ��������� �������� (����������� ��������� 
����������������� ������������), �������� ��� ���� ��������� ������ � 
��������� ������ (�. �. ����������� ��������� ���������� ������������).

���� ������� � ���, ����� � ������ ���� ������ ����� ���� � ������ |RANK|. 
풎 ���� ���������� ������������� ��������� ���� � ����� ���������, �.~�. 
��� ����� ������� ���� ����� ����� � ����� ���������. �� ���.~24 
���������� ��������~|RANK| ��� ��������� ������ �� ���.~23. �� ����� 
��������� ��������� ����~|KEY|, ��� ��� ������� ����� ����� ��� ����, 
��� ��������� �������� �������� ��� �� �������� �����, ��� � �� 
�������������� ��������� � ������.

������������� ����~|RANK| ��������� ������ ����� �� ������� � ��������� 
����������.

\alg �.(����� �� ������� � ������.) ������� �������� ������, 
�������������� � ���� ��������� ������. �������� ��������� �� �������~$k$ 
����� $k\hbox{-�}$~������� ������ ($k\hbox{-�}$~���� ������ � ������������ 
�������). ��������������, ���, ��� � � ���������~A, ������� �������� ����, 
� ������ ���� ���� ����~|LLINK| �~|RL1NK| �, ����� ����, ����~|RANK|, 
��������� ����.

\st[��������� ���������.] 㑒������� $|M|\asg k$, $|P|\asg |RLINK|(|HEAD|)$.

\st[᐀������.] ���� $|P|=\NULL$, �������� ��������� ��������. (풎 ����� 
���������, ���� ���� $k$ ������ ����� ����� � ������ ��� $k\le 0$.) � 
��������� ������, ���� $|M|<|RANK|(|P|)$, ������� �� \stp{3}; ���� 
$|M|>|RANK|(|P|)$, ������� �� \stp{4}; � ���� $|M|=|RANK|(|P|)$, �������� 
��������� ������ (|P| ��������� �� $k\hbox{-�}$~����).

\st[考 �����.] 㑒������� $|P|\asg|LLINK|(|P|)$ � ��������� ��~\stp{2}.

\st[考   ������.] 㑒�������   $|M|\asg|M|-|RANK|(|P|)$,  
$|P|\asg|RLINK|(|P|)$ � ��������� ��~\stp{2}. 
\algend

� ������ ��������� ������� ������������ ���� 
��������~$|M|\asg |M|-|RANK|(|P|)$ � ���� �4. ����� ����������� ������� 
�������������� ��������� �������, ���� ���� ���� ��������.

\alg C.(������� � ���������������� ������ �� �������.) ������� �������� 
������, �������������� � ���� ����������������� ��������� ������. 
�������� ��������� ��� ������~$k$ �������� ����� ���� (|Q|---��������� �� 
����) ����� $k\hbox{-�}$~��������� ������. ���� $k=N+1$, ����� ���� 
���������� � ����� ������.

%%552

����� ����, ��� ��������� ������� ���������~A, ��������������, ��� 
������ ���� �������� ����~|RANK|. 풎� �������� ����� ����� �� 
��������~A � ��� ���� ��������, ��� ������ ����~|KEY| ������������ ����~|RANK|.

\st[��������� ���������.] 㑒������� $|T|\asg|HEAD|$, 
$|S|\asg|P|\asg|RLINK|(|HEAD|)$,  $|U|\asg|M|\asg k$.

\st[᐀������.] ���� $|M|\le |RANK|(|P|)$, ������� ��~\stp{3}; � 
��������� ������ ������� ��~\stp{4}.

\st[考 �����.] 㑒������� $|RANK|(|P|)\asg|RANK|(|P|)+1$ (�� ����� 
��������� ����� ���� ����� ��~$|P|$). 㑒������� $|R|\asg|LLINK|(|P|)$. 
����  $|R|=\NULL$, ���������� $|LLINK|(|P|)\asg|Q|$ � ������� ��~\stp{5}. 
� ��������� ������, ���� $|B|(|R|)\ne0$, ���������� $|T|\asg|P|$, 
$|S|\asg|R|$ �~$|U|\asg|M|$.  㑒������� $|P|\asg|R|$ � ��������� ��~\stp{2}.

\st[考 ������.] 㑒������� $|M|\asg|M|-|RANK|(|P|)$ 
�~$|R|\asg|RLINK|(|P|)$.  ���� $|R|=\NULL$, ���������� 
$|RLINK|(|P|)\asg|Q|$ �
������� ��~\stp{5}. � ��������� ������, ���� $|B|(|R|)\ne0$, ���������� 
$|T|\asg|P|$, $|S|\asg|R|$, $|U|\asg|M|$. �������, ���������� $|P|\asg|R|$ 
� ��������� �� \stp{2}.

\st[�������.]   㑒�������   $|RANK|(|Q|)+1$,   
$|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$, $|B|(|Q|)\asg0$.

\st[������������� ����������� ������������������.] 
㑒�������~$|M|\asg|U|$. (⅌ ����� ����������������� 
���������� �������� |M|, ����� |P| ���� �����~|S|; ��� ����~|RANK| 
���������� ������� �����������.) ���� $|M|<|RANK|(|S|)$, 
����������~$|R|\asg|P|\asg|LLINK|(|S|)$; � ��������� ������ ���������� 
$|R|\asg|P|\asg|RLINK|(|S|)$ �~$|M|\asg|M|-|RANK|(|S|)$. �����, ����~|�| 
�� ������ ������~|Q|, ����� ��������� ��������� ��������: ���� 
$|M|<|RANK|(|P|)$, ���������� $|B|(|P|)\asg-1$ � $|P|\asg|LLINK|(|P|)$; 
���� $|M|>|RANK|(|P|)$, ���������� $|B|(|P|)\asg+1$, 
$|M|\asg|M|-|RANK|(|P|)$ �~$|P|\asg|RLINK|(|P|)$. (���� $|M|=|RANK|(|P|)$,
 ��~$|P|=|Q|$, � ����� ������� � ���������� ����.)

\st[�������� ������������������.] ���� $|U|<|RANK|(|S|)$, ���������� 
$a\asg-1$; � ��������� ������ $a\asg+1$. ⅏��� �������� ��������� �������:
\itemitem{i)} ���� $|B|(|S|)=0$, ���������� $|B|(|S|)\asg a$, 
$|LLINK|(|HEAD|)\asg|LLINK|(|HEAD|)+1$; �������� ��������.
\itemitem{ii)} ���� $|B|(|S|)=-a$, ���������� $|B|(|S|)\asg0$; �������� ��������.
\itemitem{iii)} ���� $|B|(|S|)=a$, �� ��� $|B|(|R|)=a$ ����� ���� ��~\stp{8}, �
��� $|B|(|R|)=-a$---��~\stp{9}.

\st[����������� �������.] 㑒������� $|P|\asg|R|$, 
$|LINK|(a, |S|)\asg|LINK|(-a, |R|)$, $|LINK|(-a, |R|)\asg|S|$,   
$|B|(|S|)\asg|B|(|R|)\asg0$. ���� $a= +1$, ���������� 
$|RANK|(|R|)\asg|RANK|(|R|)+|RANK|(|S|)$;
%%553
���� $a=-1$, ���������� $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|R|).$ ������� ��~\stp{10}.

\st[���������� �������.] ��������� ��� �������� ����~A9 (��������� ~A).  
�����,  ����  $a=+1$,   
���������� $|RANK|(|R|)\asg|RANK|(|R|)-|RANK|(|P|)$, 
$|RANK|(|P|)\asg|RANK|(|P|) +|RANK|(|S|)$, ���� $a=-1$, ���������� 
$|RANK|(|P|)\asg|RANK|(|P|)+|RANK|(|R|)$, ����� $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|P|)$.

\st [��������� �����.] ���� $|S|=|RLINK|(|T|)$, �� 
���������� $|RLINK|(|T|)\asg|P|$; � ��������� ������ $|LLINK|(|T|)\asg|P|$.
\algend

\section {*㄀�����, ������������ � �. �}. ������ ������, ���������� ����� 
������ ��������, ������� �� �������� ������������������ ��������, �� 
��������������� ��������� ���������� ������, ��� ��� �� �� ����� 
������������� �� ��������. ������� ���� �������� ����, � �������������� 
�������� ������ ��� �������� ����� ������������ ����������� ������.

������ ��������, ���� ��������� �� ���������, �������� �� $O(\log N)$~����� 
[�.~�.~Foster, A Study of AVL Trees, Goodyear Aerospace Corp. 
report GER-12158 (April 1965)]. ������ ����� �������� ������������� ���� 
����� ������ � �������� �������� ����~|P|, � ������� $|LLINK|(|P|)$ 
���~$|RLINK|(|P|)$ �����~$\NULL$, ��� � ���������~6.2.2D. 풎� �������� 
������� �������������� ����� �������, ����� �� ������ ������ ����������, 
������������ ���� � ����~|P|:
$$
(P_0, a_0), (P_1, a_1), \ldots, (P_l, a_l),
\eqno(16)
$$
���   $P_0=|HEAD|$,   $a_0=+1$;  $|LINK| (a_i, P_i)=P_{i+1}$, $0\le i<l$;
$P_l=|P|$, $|LINK|(a_l, P_l)=\NULL$. 틅����� ����� ������ � 
�������� ������ �� ������ ����� �������� �� ��������������� ����. ������� 
�������� ����~|P| 
�������������~$|LINK|(a_{l-1}, P_{l-1})\asg|LINK|(-a_l, P_l)$, � ����� 
���������������� ���������� ������������������ ����~$P_{l-1}$. �����������,
 ��� �� ������ ���������������� ���������� ������������������ ����~$P_k$, 
������ ��� ����������� ������ ���������~$a_k$; ����� ������������ 
��������� ��������� �������������: ����~$k=0$, ��������� 
$|LLINK|(|HEAD|)\asg|LLINK|(|HEAD|)-1$; �������� ��������, ��� ��� 
����������� ������ ����� ������. � ��������� ������ ����� ����������� 
���������� ������������������~$|B|(P_k)$, �������� ��� ��������:

\item{i)} $|B|(P_k)=a_k$. 㑒������� $|B|(P_k)\asg0$, ��������� $k$ �� 1 �
��������� ������������� ��� ������ ��������~$k$.

\item{ii)} $|B|(P_k) = 0$. 㑒������� $|B|(P_k)\asg-a_k$; �������� ��������.

\item{iii)} $|B|(P_k)=-a_k$. ␅������ ������������!

������������ ��������� � ����� � ��� �� �������, ��� � � ��������� 
�������; ������� ����� ��������� � (1), ��� � ����
%%554
$A$ ���������~$P_k$, � � ����~$B$---����~$|LINK|(-a_k, P_k)$, 
������������� 
�����, \emph{���������������} ���, �� ������� ������������ ��������. ���� 
������ ���� �������: ����~$B$ ����� ���� ����������������, � ����� ������� 
����� ������~3, ����������� ������~1, �� $\beta$~����� ���� ������~$h+1$. 
� �������~1 �~2 ������������, �������~(2), ��������, ��� �� ��������� 
������, ������������ � �������� �����~(2) ����~$|LINK|(a_{k-1}, P_{k-1})$, 
��������~$k$ ��~1 � ����������� ��������� ������������� ��� ������ 
��������~$k$. � ������~3 �� ���������� ����������� �������, ��� �� 
�������� ����� ������, �� ������ ���������� ������������������ ���~$A$, 
��� �~$B$ ����������; ������� ����� ��������� �~$|LINK|(a_{k-1}, P_{k-1})$ 
������ ����~$B$ �������� �����������.

������ ������������� ����� �������� ������� � ���, ��� ��� ����� 
����������� �� $\log N$~���������, � �� ����� ��� ��� ������� ������ 
������� ������. ������� ����� ������ ����, ���� ���������� ������� ����� 
������ ���� ������ 䈁������ (��.~���.~8, �~6.2.1).

������������� ���������������� �������� ��� ������������� �������� ������� 
������ ����������� �������� \emph{������������}, ����� ����� ������~$L_2$ 
����������� ������ �� ������~$L_1$ ��� ��������� �������. ����� �. ����� 
�������� ������������ ������� ���� ������. �����������, ��� 
"$\mathop{\rm ������}\nolimits(L_1)\ge \mathop{\rm ������}\nolimits(L_2)$"; 
������ ������ �������������� ����������� �������. 
㄀��� ��~$L_2$ ������ ����, ������ ��� ����������� �����~$J$, � 
�����~$L'_2$ ��������� ����� ������ ��� $L_2\backslash\{J\}$. ����� ����� 
���������� �� ������ ������ ������~$L_1$, ���� �� ��������� ����~$P$, 
������, ���
$$
\mathop{\rm ������}\nolimits(P)-\mathop{\rm ������}\nolimits(L'_2)=0
\hbox{ ��� } 1;
$$
��� ������ ��������, ��� ��� ��� �������� �� ����� ������ ������� ������ 
���������� ��~1 ���~2. ⅏��� ��������
\picture{���. ���. 554}
� ���������� � �������������~$L_1$, ��� ���� �� ����� ����~$J$ ��� 
�������� ����������� ���������~A.

����� ����� ����� ����� ������� �������� ������: \emph{���������} ������ 
�� ��� �����, ������������ ������� ���� �� �������������� ������. 
����������, ��������, ������ ����������� ������ ���.~20 ��� ��������� ���� 
�������, ��������� �� ��������� $\{\, |A|, \ldots, |I|\,\}$ � 
$\{\, |J|, \ldots, |Q|\,\}$ ��������������: ��������� ������������ 
�������������� �����������. � ����� ������,
%% 555 
����� �� ����� ��������� ������ � ������ ����~$P$, ���� �~$P$ ����� ����� 
�� ���� ���.~25. �� ������ �� ��������� ����� ������, ���������� 
$\alpha_1$, $P_1$, $\alpha_4$, $P_4$, $\alpha_6$, $P_6$, $\alpha_7$, $P_7$,
 $\alpha$, $P$ � ������������ �������, � ������ ������, ���������� 
$\beta$, $P_8$, $\beta_8$, $P_5$, $\beta_5$, $P_3$, $\beta_3$, $P_2$, 
$\beta_2$. 풎 ����� ������� ������������������� ������������: ������� 
���������~$P$ ������ ��~$\alpha$, ����� �������������~$\beta$ � 
$\beta_8$, ���������~$P_8$ � �������� ������������ ����,
\picture{���. 25.  ������ ����������� ������.}
������������� $\alpha_7$ � $\alpha P$ (����~$P_7$ �����������), $\alpha_6$ 
� $\alpha_7P_7\alpha P$ (���������~$P_6$), $\beta P_8\beta_8$ �~$\beta_5$ 
(���������~$P_5$) �~�.~�.; ���� $P_8$, $P_7$,~\dots{}, $P_1$, ������� �� 
���� �~$P$, ������������ ��� �����������. ����� �������, ���, ���� 
�������� ������ �������� $N$~�����, ���� �������� ����������� ������� ���� 
$O(\log N)$~������ �������. ���� � ���, ��� ������������ � 
�������������� ������� ���� � �������� ������������ �������� 
$O(k)$~�����, ��� $k$---�������� ����� ��������������� ��������, 
� ��������~$k$, � ��������, �������� �������������� ����������.

��� ��� ��������� ����� �������� ��� � ������~|KEY|, ��� � � ������~|RANK| 
(��� � ������ ������), ������, � ������ ������������ ��� ����� 
������~$L_2$ ������ ���� ������ ������~$L_1$. ��� ����� ����� ����� 
���������������� ������������ ������� � \emph{����� �������}, � ������� 
������ � ������~|LLINK| �~|RLINK| ������������ ����~|UP|, ����������� �� 
����, � ����������� ������� ����, �������� �� ������ ���� "�����" ��� 
"������" �����. ������������� � ���� �������� � ����� ������� �������
%%556
�������� ��������� � ������ ��������� ������������ ���� ��� ������ 
�������� ���� � ���� �� �����; �� ����� �������� ������������ �������� �� 
�������~|P| ����~$|NODE|(|P|)$ ��� ����, ���������� ��~$|NODE|(|P|)$ � 
������������ ������� (�.~�.~����~$|NODE|(|P|\$))$, ��� ������������ 
���������� ������, �����������~$|NODE|(|P|)$ �~�.~�. � ��������� �������� 
��� �������� � ����� ������� �� ����� ������� ������~(16), ��� ��� 
������~|UP| ���� ����������� ����������. ����������, � ���� ������ 
��� �������, �������� ��� �������� �������� ������ ��������� ������ ������.
 ������������� ������ � ����� ������� ������ ���� ���������� ������������� 
������������� ������ ������ �������������: ����������� �� ������ �����, �� 
����� ���� ��� ������, ��� � �����. ������ �������� ���������� ������ 
�� ��������, ���������� �� ������������� ���������������� �������� � 
����� �������, ����� ����� � ���������� ����������� ������ �. ������ 
(ᒝ��������� �����������, 1972).

\section ���������� ���������������� ��������. ������� ���� ���������� 
��������� ������ �������� ����������� �������� ��������, ������������� 
�� ����� ��� ��������������� ���� ������� ������ ��� ���������� ����� 
�����. � ���������� ������� ��� ������� �� ���������; ��������, ��� ��� 
��������� ��� ��� ������� �������� ���������������� ���������������� ��������.

���������� ������� ������ �� \emph{���������������� �����} ������� 
�.~������������, �.~����������� � �.~�.~㎍��. ������ ������ 
��������������� ��� ������---�� ����������� ������ ����� ��� ������� �����---� 
�� ��� ���� ���������� �������
$$
\sqrt{2}-1<{\hbox{��� ������ ���������}
\over\hbox{��� ������� ���������}}<\sqrt{2}+1.
\eqno(17)
$$
����� ��������, ��� ������ ���� ����������� ����� �������, ����, ������� 
���������~A, ������������ ��� ������������ ����������� � ���������� 
�������� (��.~���.~25). ������ �� ����� ����� ������� ����� ������������� 
����� ���������. ���� �������� �������~(17), �� ������������ ������ 
����� �������, ������, �� ���� ���������� ������� ������.

�� ������ ������ ����� ����������, ��� ������� �� ���������������� ����� 
������� ������ ������, ��� ������� ����������������, �� �� ����� ���� 
������ ��� ������� ��������� ������! ���� � ������ ���� ��� ���� 
����~|RANK| ��� ������������� ��������� ������, �� ��� � �������� ��� 
������ ���������, � ��������������� ������ ���� ����� ���������� 
��� �������� ���� �� ������. �������, ������, ��� ��������� �������, 
����������� ��� ���������� �������� �������, �������� ������ �������, 
��� ��������~A, � �������� ���� ����� �� ����, ��������, �� �������� 
����������� ������������.

%%557

������ ���������� ������ � ���������������� ��������, ��������� 
"(3-2)-�������", ��� ��������� � 1970~�. ������ 厏������� [��. Aho, 
Hopcroft, Ullman, The Design and Analysis of Computer Algorithms 
(Reading, Mass.; Addison-Wesley, 1974), ch.~4]. ���� ������� � ���, ��� �� 
������� ���� ����� �������� ���� ���, ���� ��� �����, �� ������ ���������, 
����� ��� ������� ���� ������������� �� ����� ������. ������ ���������� 
���� �������� ���� ����, ���� ��� �����, ��� �������� �� ���.~26.

������� � (3-2)-������ ��������� ��������� �����, ��� ������� � 
���������������� ������. ���� �� ����� ���������
\picture{���. 26.  (3-2)-������.}
����� ���� � ����, ���������� ����� ���� ����, �� ������ ��������� ��� � 
�������� ������� �����. � ������ �������, ���� ���� ��� �������� ��� �����,
 �� ����� ��� �� ��� ������������ ���� � ��������� ������ ���� � 
����-����. 풎 � ���� ������� ����� ������� ������� ����. �� ���.~27 
������� ������� ������� ������ ����� � (3-2)-������ ���.~26.

厏����� �������, ��� �������� ��������, ������������ � ����������� 
���������� ��� (3-2)-��������� ���������� ������ � ������ ������ �� 
��������������� �������� �� ����������������� ���������.

�.~����� [{\sl Proc. ACM-SIGFIDET Workshop\/} (1971), 219--235] ��������� 
���������� ������������� (3-2)-�������� � ������� �������� ��������. �� 
���.~28 �������� ����� ������������� (3-2)-������ ���.~26; ���� ��� � 
������ ���� ������������, ����� �������� "��������������" ������ ������ �� 
"������������". �������, ���, ��� � � ����� �������� ������ ������, 
����� ����������� ����� ������� � ������������ �������. �����������, ��� 
��� ������� ������ ����� � ����� ������� ����� ����������� �� �� ��������, 
��� � � ������ ���������������� ��������, � ������ ����������� � 
���������� ��������, ������, ����� ���� ���� ������ ������� �������� 
(��� ��������� ������������ ������������ ���, ��������� � ����������~� �~�).

%%558

\picture{���. 27.������� ������ ����� "|M|" � (3-2)-������ ���. 26.}

%%559

\picture{���. 28.  (3-2)-������ ���.~26, �������������� ��� �������� 
������ ������.}

\excercises
\ex[01] ������ � (1), ������ 2, ��� �������������� ������� ������ ������ 
�������� ������� ����� ���������� �����~$A$ �~$B$?

\ex[16] ���������, ������ ������ ����� �� ���� ������� ����, ���� 
�� �������� ����~�7 �~$|B|(|S|) = 0$.

\rex[�25] ��������, ��� ���������������� ������, ������� 
$N$~���������� �����, �� ����� ����� ����� $(\phi-1)N=0.61803N$~����� � 
���������� ������������ ������������������.

\ex[�22] �������� ��� ������������ ���������: ����� ���� 
���������������� �������� � $F_{n+1}-1$~����������� ������ ������ 
䈁������ �������~$n$ ����� ���������� ����� ����������� ����.

\rex[�25] �������� ��� ������������ ���������: ���� ��������~A 
������������ ��� ������� $N$~������ � ������������� ������ ������ � ���� 
��� ����� ��������� � ������������ �������, �� ���������� ������ 
���������� (�.~�. ��� ����� ����������� ����� ����������� ���� ����� ���� 
�������� �������� � $N$~������).

\ex[�21] ��������, ��� (5) ���������� ������������ ������� ��� 
���������������� �������� ������~$h$.

\ex[�27] (�.~��.~�~ዎ�� �~�.~�.~���.) �������� ������������� 
�������~(9) ��� ����� ���������������� �������� ������~$h$. 
[\emph{㊀�����:} �������� $C_n=B_n+B_{n-1}$ � ������������ ��� ����, 
��� $\log(C_{n+1}/C_n^2)$ ������ ��� ��� �������~$n$.]

\ex[�24] (�.~�.~切���.) ��������, ��� ���������� ���������~$\beta$, �����,
 ��� $B'_h(l)/B_h(1)-2^h\beta\to1$ ���~$h\to\infty$.

\ex[�47] ������ ��������������� ����� ���������������� �������� �������� 
� $n$~����������� ������ $\sum_{h>0}B_{nh}$? ������ ��������������� �������
������~$\sum_{h\ge0}hB_{nh}/\sum_{h\ge0}B_{nh}$?

\ex[�48] ����� ��, ��� ��� ������� $N\hbox{-��}$ �������� ��������~A 
��������� � ������� $\sim\log_2N+c$~��������� ($c$---��������� ���������)?

\ex[22] ��������~$0.144$ ������ ���������� � ����.~1: ���� ��� ���~$k=l$ � 
������ ���~$k=2$. ��������~$1/7$ ����������� � ��� �� ���� ������ ����.~2. 
����� �� �����������, ��� �� ���� ���� ������ ����� ���������� ��������,
 ��� �� �� ���� �������?

\ex[24] 煌� ����� ������������ ����� ������ ���������~A ��� ������� 
�������� ���� � ���������������� ������? ������ ���������� ��������� 
����� ����� �������?

\ex[10] ������ ����~|RANK| ����� ������������ ���, ��� � ������, � 
�� ���������� � �������� ����� ����� ���� ("1" � ������ ����, "2" �� ������ 
�~�.~�)?

%%560

\ex[11] ��������� ����������������� ������ � ������� ����~|RANK| ���� 
������������� ��� ������ � ��������� ��������. ����� �� ����� �� ������� 
������������ ��������� 6.2.2� � 6.2.2D?

\ex[18] (�.~�.~�����.) �����������, ��� ������������� �������� ������ 
����������� � ���� ��������� ������ � ������~|KEY| �~|RANK| � ������ ����. 
���������� ��������, ������� ����������� � ������ ������ ����~$K$ 
� ���������� ���������~$K$ � ������, �.~�. ������� �����~$M$, �����, ��� 
������~$K$ ���� $M-1$~������.

\rex[20] ��������� ���������������� ������, ������� ���������� �� 
����� �������� ��������� ����~|F| �� ������ ���.~20 � ������� ��������� 
��������, ������������� � ������.

\rex[21] ��������� ���������������� ������, ������� ���������� �� 
����� ������������ ������ 䈁������ (12): (a) ������ � (b) ����� �� 
������ ���.~20, ���� ������������ �������� ������������, ������������ � ������.

\ex[21] ��������� ���������������� �������, ������� ���������� �� ����� 
����������� ������ ���.~20 �� ��� �����: $\{\, |A|, \ldots, |I|\,\}$ 
�~$\{\, |J|, \ldots, |Q|\,\}$---� ������� ������������� � ������ ��������� 
�����������.

\rex[26] ������� ������ ��� ������������� ������ ���������������� ������,
 ����� ���������� ������������������ ����� ���� ������� ��~$-1$. 
���� �������������� ������ ��������� ������������ ������� �����; ��� 
������ ��������� ������� ���������������� ������ �� $O(1)$~������ ������� 
���������� �� ����� ��� �����.

\ex[40] ����������� ���� ������������� ������������� ������ 
���������������� ��������, ��� ���� ������� ����� ���������� 
������������������~$0$ ���~$+1$. (⎃�� ����~|B| ����� ������ � ������ 
����.) ᓙ������� �� ��� ����� �������� ��������� ������� � �������� 
��������������?

\rex[30] ���������� ��������, ������� ������ �� ����������� (� ������ 
���. 5) $N\hbox{-�������}$ �������� ������� �� $O(N)$~�����. ��� �������� 
������ ���� "����������" � ��� ������, ��� �� �������� ���� �� ������ � 
������������ ������� � ������ ��������� �������, �� ���� ������� 
�������������� ��������~$N$. ( �� �������� ����� ���� �� ������������ 
��� ����������� ����� ����������������� ������ ��� ��� ������� ������ �� 
���� �������� � ���� ������.)

\ex[�20] ����� ������ �������~A ��� �������� �� ���������������� �����?

\ex[�20] (�.~���������.) (a)~��������, ��� ���������� ���������������� 
������� � ����������� ����� ������� ���������� 
"(��� ������ ���������)/(��� ������� ���������)". 
(b)~��������, ��� ���������� ������� �� ���������������� �����, ������� 
����� ������ ������� �������� ����� �������� ������ � ������� �����������.

\ex[�22] (�.~���������.) ��������, ��� ������������� ��������� ���������,
 ���������������� ���������� ������� (17)
$$
{1\over2}<{\hbox{��� ������ ���������}\over\hbox{��� ������� ���������}}<2,
$$
�������� �������� ���������������� ������� � $2^n-1$~����������� 
������. (� ����� �������� ����� � ������ ���� � ������ ���� ����� ����� �����.)

\ex[27] (�.~����������, �.~���������, �.~㎍.) ��������, ��� 
����� ��������� �������� ������� ��� �������� �� ���������������� �����, 
����������� �������~(17) � ������������ �� ����� $O(\log N)$ ��������� 
�� �������.

\ex[40] ���������� �������� ���������������� $t\hbox{-�����}$ �������� 
���~$t>2$.

\rex[M23] ������� ������������ ����� ���������, ����������� ��� ������ � 
(3-2)-������ � $N$~����������� ������.

\ex[41] ����� ����������� ���������� ���������� (3-2)-������.

\ex[�47] ��������������� ��������� (3-2)-�������� � ������� ��� 
��������� ��������.

%% 561

\ex[26] (�.~���-�����.) � \S~2.5 ����������� ��������� ��������� 
������������� ������������� ������, ������� "�������� ����������" 
(����� ������� ����������� �������, ��������������� �������) � "������ 
����������" (����� ������� � ���������� �������, ��������������� 
�������). ��������, ��� ���� ��������� ������������ ������� � �������� 
������, � ��������� ������, ����������������, �� ����� ����� (a)~"�������� 
����������" � (b)~"������ ����������" ������� � $O(\log n)$~������ 
�������, ��� $n$~���� ����� ��������� �������� ������. 
(���������~\S~2.5 ��������� ������� $n$~�����.)

\ex[34] (�.~䐅����.) ���������� ������������� �������� �������,
 ���������� ��� ���������, ��� ������� ������ �������� ����� 
��������� $m-1$ �~$m$ ��� ������~$m$ ������� $O(\log m)$~������ �������.

\subsubchap{ላ��� ���������� ������� } %6.2.4.
��������� ���� ������ ������ �� ������ ���� ������� � �������� ��� 
����������� ������, �.~�.~����� ����������� ������� ������� ���������� � 
������� ���������� ������ ���. ⅏��� �� ���������� ������ �������� ������,
 ����� ����� ������� ���������� �� ����� �������� �����, �������������� 
�� ������� ������������ ����������� � ������ ��������, �����, ��� 
��������� ����� ��� ��������. (� ������ � ��������� ����� ��������� � �.~5.4.9.)

\picture{
���. 29. ������� �������� ������ ������ ����� ���������  �� "��������".
}

����������� ��������� �������� ������ ��� �������� ������ (����������, 
���� ��� ������������ ���������� �������). ���������� ������� �������� 
������ ������ (���.~29) � �����������, ��� ��� �������� � �������� �����.
 (���� |LLINK| �~|RLINK| �������� ������ ������ �� �����, � �� ������ 
���������� ������.) ���� �� ������� ����������� � ����� 
��������� ��������� ��������� ���������� ������ �� ������, ��� 
����������� ����� $\log_2 N$~��������� � �����. ��� $N$, ������ ��������,
%%562
�� ����� �������� 20. �� ���� ��������� ������ �� "��������" �� 7 
����� � ������, ��� �������� ��������� �� ���.~29, � ���� � ������ ������ 
������� �������� ���� ���� ��������, �� ����������� �������� � ��� ���� 
������ ���������, �. �. ����� ��������� � ��� ����!

����������� ����� � ��������, �� ��������, ����������� �������� ������� � 
��������, ��������������� � ������ ��������-���� �� 8 �����. ���� 
��������� �������� ������� ��������, ��������������� �� 128 ����� ����� 
������� ��������� � �����, �� ����� �������� ��������� ���� � ������� 
�� �������� ���������, ���������� ���� ��� ��������. ����� ��������� 
������� �������� �������� �� ���������� ������;
����� ����������� ���� ��� ��������� � �����, ���� � ����� ������ 
������� �� ���������� ������ ����� �� ����� 254 ������.

����������, �� ������� ������ �������� ����� ��������, ��� ��� ������� 
���������� ������ ���������� � ������ ������� �������� �������� ������ 
�������. �����������, ��������, ��� ������ ��������, ����������� 
������������ �� $m$ �����, �������� $72.5+0.05m$ ��. ����� �� ���������� 
��������� ������ �������� �������� ����� $a+b\log m$ ��, ��� $a$ ���� �� 
��������� � $72.5$, ��� ��� ������ �����, ����������� �� ����� � ������� 
�������, �������� ��������������� $\log N$, ����������� ��
$$
(72.5 + 0.05m)/\log m +b.
$$
풀 �������� ��������� �������� ��� $m\approx350$; � ���������������� 
���� ������� ����� "�����". ��������, ����� ������� � ������������, 
����������� ��� $m$ ��~200 ��~500. �� �������� ��������� ��������� 
��������� ������� �������� $m$ ������� �� ������������� ������������ 
������� ������������ ��������� � �� ����� ������� � �������.

�. �. �������� [{\sl IEE Trans.\/}, {\bf EC-12} (1963), 863--871] 
��������� ������� $m$-����� ������� ��������� �������: ��������� ���� 
�� ������ $l+1$, ���� ���� ������� $l$ ����� ��������. 풀 ����� ������� 
�������� ������� ������� ���������, ��� ��� ��� ������� ������ ������ 
�������� ����� ������������� ������������� ����������� ������; 
�������� ������� �� �������������, ��� ����� ���������� 
����������� ������� ���� ������� � ��������.

���� ���� �������� �� ����� � �������� �������� ������������ ������ 
������� � ��������, �� ��� ��� ������������� �������� ������������� 
������, ��� ������ ������� ������������ ����������, ����� ������� ����� 
��������������, ��������� ������� ������������ ���������� 
��������������� ������� �� ���� ��������, � ������ ������� �������� ����������
%% 563
������.  �� ����� ���������� \dfn{��������-����������������} 
������������ ����� [��. {\sl JACM\/}, {\bf 16} (1969), 569--571].

�. ���� � �. ㇃���� [Proc. Princeton Conf. on Inf. Sciences and Systems, 
4 (1970), 345--349] ���������� ����������� ��������� 6.2.2�, ��� ��� 
������� ��������� ����, ������������� ��� �� ��������, ��� � �� 
�������������� (���� ������ ��� ��������); ���� �������� ��������� ������, 
��������� ����� �������� (���� ������� �������). ��� �������������� 
���������� ������� � ��������� ������� ����������� ������ ������� 
����� ���������, � �����, ��� ����� ��������, ����������� 
����� $H_N/(H_m-1)$, ��� ���� �������� ������ ����� ��������� � ������ 
���������� ���������� $m$-������ ������ (��. ���.~10).

\section $B\hbox{-�������}$. � 1970~�. �. ����� � �. ���-����� 
[{\sl Acta Informatica\/}, (1972), 173--189] 
� ���������� �� ��� �������� � �� �� ����� �. ������� [��������������] 
���������� ����� ������ � �������� ������ ����������� ������ ���������� 
��������. �� ���� ������������ �� ����������� ������ ���� �������� ������,
 ��������� \dfn{$B\hbox{-���������}$}, � ��������� ����������� ����� ���
�������� 
������� ���� � "���������������" �������������� � ��������� ������, 
��������� ��� ���� ������������ ������� ���������.

\dfn{$B\hbox{-�������}$ ������� $m$} ���������� ������, ���������� ����������
����������:
\medskip
\item{i)} ������ ���� ����� �� ����� $m$ �������.
\item{ii)} ������ ����, ����� ����� � �������, ����� �� �����
$m/2$ �������.
\item{iii)} ������, ���� �� �� ����, ����� �� ����� 2 �������.
\item{iv)} ��� ������ ����������� �� ����� ������ � �� ��������
����������.
\item{v)} ���������� ���� � $k$ ��������� �������� $k-1$ ������.
\medskip
\noindent (��� � ������, ����---�������� ����, � ���� ��� ����������.   
��� ������ �� �������� ����������, �� ����� ������������� ��� ������� 
����, ������� � ���������������� ��� � ������, ��� ��� $\NULL$---��� 
��������� �� ����.)

�� ���.~30 �������� $B\hbox{-������}$ ������� 7. ������ ���� (����� ����� � 
�������) ����� ��~$\lceil 7/2\rceil$ ��~7 ���������� � �������� 3, 4, 5 
��� 6 ������. �������� ���� ����� ��������� ��~1 ��~6 ������ (� ������ 
������ 2). ��� ������ ��������� �� ������� ������. ��������, ��� (a) 
����� ����������� � ������������ ������� ����� �������, ���� 
������������ ������������ ��������� ������� ������������� �������, � 
(b) ���������� ������� ����� �� ������� ������ ���������� ������.

B-������� ������� 1 �~2, ��������, �����������; ������� �� ���������� ���� 
������ $m\ge 3$. ��������, ��� (3-2)-�������,
%% 564
\picture{���. 30. $B\hbox{-������}$ ������� 7}
%% 565
������������ � ����� �.~6.2.3, �������� $B\hbox{-���������}$ ������� 3;
� �������, $B\hbox{-������}$ ������� 3 ���� (3-2)-������.

㇅�, ���������� $j$ ������ � $j+1$ ����������, ����� ����������� � ����
\picture{㇅� $B\hbox{-������}$}
��� $K_1<K_2<\ldots <K_j$, � $P_i$ ��������� �� ��������� ������, ������� 
$K_i$ � ������� $K_{i+1}$. ዅ����������, ����� � $B\hbox{-������}$ ��������� 
�����������: ����� ���� ��� ���� (1) �������� �� ���������� ������, �� 
���� ������ �������� ����� ������ $K_1$, $K_2$, \dots, $K_j$. (��� ������� 
$j$, ��������, ������������ �������� �����, � ��� ����� $j$ ��������� 
����� ���������������� �����.) ���� ����� ������, ������ ���� ������; 
���� ����� �������� � ���� ����, ��� �������� ����� ����� $K_i$,
 �~$K_{i+1}$, �� "�����������" (�������� � ����������� ������) ����, 
��������� $P_i$, � ���������� �������. ㊀������ $P_0$ ������������, 
���� �������� ������ $K_1$, a $P_j$ ������������, ���� �������� ������ 
$K_j$. ��� $P_i=\NULL$ ����� ��������.

��������������� ������ $B\hbox{-��������}$ �������� �������������� ��������, � 
������� ������������ �������. ����������, ��������, ���.~30; ������ ���� 
������������� ����� ��������� �������. ���� ����� �������� ����� ���� 
$337$, �� ������ ������ ����
\picture{������� � $B\hbox{-������}$}
� ������ �������, ��� ������� �������� ����� ���� $071$ �� ������������, 
��� � ��������������� ���� ������ 2 ��� �����---�� ��� "�����". 풓 
��������� ����� ����������, �������� ���� �� ��� ����� �� ��� ����� � 
������ � ������ ������� ���� �� ������� 1:
\picture{����������� ���� ��� �������}
%% 566 

������, ���� ����� �������� ����� ������� � $B\hbox{-������}$ ������� $m$, ��� 
������ �������� ����������� �� ������ $l$, ����� ���� ��������� � 
���������� ���� ������ $l-1$. ���� ���� ������ �������� $m$ ������, �. �. 
����� ��� (1) � $j=m$, ��� ���������� �� ��� ����
\picture{����������� ����: ����� ���}
� ��������� ���� $K_{\lceil m/2\rceil}$ � ����-����. ( �� �������, 
��������� $P$ � ��� ���������� ������������������� $P$, $K_{\lceil 
m/2\rceil}$, $P'$.) 풀 ������� � ���� ������� ����� �������� � 
����������� ����-����. (�. � ���.~27, ��� ��������� ������ $m=3$.) 
���� ����� ��������� �������� ����, ������� �� ����� ����, �� ������ 
������� ����� ������ � �������� � ���� ������������ ���� $K_{\lceil 
m/2\rceil}$, � ����� ������ ������ ���������� �� ������� ����.

��������� ��������� ������� ��������� ��� �������� $B\hbox{-��������}$; ����� 
������� ��� ������� ����, �������� ������ ��������� ���.~1. ��������, 
��� ������ ����-������ ������ ����� �� ������� �����, � �� ���� �� ������ 
�����, ��� ��� ������������ �������, ��������� ������� ���� 
������,---����������� �����.

㄀����� �� $B\hbox{-��������}$ ���� �������� ������� ������� (��. ���.~7).

\section ��������������� �������������. ����������, � �������� ����� ����� 
����������� ��������� � ��������� ������ ��� ������ � $B\hbox{-������}$ 
������� $m$. �����������, ��� ������� $N$ ������, � �� ������ $l$ ����������� 
$N+1$ �������. ⎃�� ����� ����� �� ������� 1, 2, 3, \dots �� ����� 2, 
$2\lceil m/2\rceil$,  $2\lceil m/2\rceil^2$, \dots; �������������,
$$
N+1\ge 2\lceil m/2\rceil^{l-1}.
\eqno (5)
$$

����� �������,
$$
l\le 1+\log_{\lceil m/2\rceil}\left({N+1\over2}\right);
\eqno(6)
$$
��� ��������, ��������, ��� ��� $N=1999998$ � $m=199$ ����� $l \le  3$. 
  ��� ��� ������ ���������� ��������� ����� ������� � $l$ �����, ��� 
������� ����������� ����� ����� ������ ���������.

��� ������� ������ ����� ����� ������������ ��������� $l$ �����. ������ 
������� ����� ������������ ����� ����� ������, ��� ��� ����� ���������� 
����������� ��� ���������� ������ ����� �� ������� ������ ���������� 
�����, ������� �� ��������� ����� $p$. � ������ �� ����� 
$1 + (\lceil m/2\rceil-1) (p-1)$
%% 567
������; �������������,
$$
p\le 1+{N-1\over \ceil{m/2}-1}.
\eqno(7)
$$
풎 ��������, ��� ������� ����� �����������, ����������� �� ���� �������, 
������~$1/(\ceil{m/2}-1)$.

\section ㋓������ � ���������. ������������ ������ ����� ��������, ���� 
������ �������� ����������� $B\hbox{-������}$. ������.����� �������, ��� 
��� ��������� � ����� �� ������~$l-1$ �����~$\NULL$ � �� �����~$\NULL$ �� 
������ �������. 풎 ����� ������������ ����� ������������ ������ 
������������, � �� ����� ���������� ��� ������������, ��� � �����, ���� 
�������� ���~$\NULL$ � ����� ������������ ��� ���� ������ ����� ������ 
��������~$m$. ������������� ���� ���������~$m$ �� �������� ��������� 
�������, ��� ��� ��� ��������� ������������� ���� �������� �� ��� �� 
������, ��� � �������������� ����. ����� ���������� ���������� 
$B\hbox{-������}$ ��������~$m_1$, $m_2$, $m_3$,~\dots, ����������, ����� 
��� ���������� ���� �� ������~$l-i$ ����� ��~$m_i/2$ ��~$m_i$ ����������; 
� ��������� $B\hbox{-������}$ ����~$m$ ��� ������� ������, ������ �������� 
������� ��������, � ��������, ��-��������.

�������� ���� ����������� ������, �� ����� ������������ ���������� ������ 
������� ����� ��� ������ ������� ������, �����, ����� ����, ������� � 
������� ����������. ������ ����� ���������� ���� ��������� ����� �������, 
� � ����� ������� ���� �� ������� ������� ������ ������� � �����, ������� 
� �����; ��� ������� �� � ������� ������ ��������~$m$ � �� ���� �� 
������������ ������������.

㌅���� ������� ����� ����������� ���.~30, ����������� ����, ��� ��� 
������ ����� �������� ������ � ������� � ��� ���� ��������� ������ 
�������������� � ��������� �����. � ����� ������ ����� ����� ���� �������� 
��� ������ � ������� $\le011$;
����, ���������� ������~$A$, �������� ������, ����� ������� ������������� 
�����������~$439<K\le 449$, �~�.~�. ������ ������ � ������������, ��� 
������ ����, �� � ��� ������������ ��������, ��� ������ �� ������������ 
�� ������� ����� �� ��������� �������.  �� �������, ������ ������ 
��������� �� ����� ��� ����������; ��� �� ����������� � "����������" 
����� ������ ��������� ����� ����. ���� ������ ���� ������ �� ����� 
���������� ����������- ������������� �������, �� �������� ����������� 
���������� � ������ �������� ���� ��� ���������������, ��� � ��������� �������.

��������� ���������� �.~�.~����� �~�.~X.~ᅍ�� 
[{\sl JACM,\/} {\bf 16} (1969), 569--579] ������� �� ����� � ���, ��� 
������� ����� �������� ������� ������; ������ ��~10 ���������������� 
������� � �����. ���� �������� ������ ��� ������� �����, � �������
%%568
�������� ������������ ����� �����������, ����� �� 10~������� 
�������� ������ �������� ������. ���� ������� �������� ��������, �� 
�������� �����, �� ������������ ����������, ��� ��� ������ ����� ���� 
������, ��� �������� ������� �� ���������� ������� ������.

�.~X.~������ (�� ������������) ������ �� ��, ��� ����, ������� � ������ 
$B\hbox{-��������}$, ������� ����� ��� ������ � ������� \emph{���������� 
�����}. ��� ����� ��������� ����� ������� ������� ���� � �������~$[m/2, 
m]$; ������ ����� ����� ������ �������, ��� ������ ���� ������ ���� 
�������� ������� �� ����� ��� ����������. �������� ������� � ����������� 
�������� ��-�������� �����������, ���� ������ ����� ������ � ������ 
���� ������� �� �� ����. ������ ������ ��������� ������ ���� ������� 
�������� (���.~5).

������ ������ ������������ ����� $B\hbox{-������}$ �������� 
���� "�����������", ��������� ������� �~���-�������. ��� ������� � ���, 
����� �������� �������� ������� ����� ���������� ���������� �����������; 
������ ��� ������������ ��������� ��������. ����� ������� ������������� 
����, ���������� $m$~������ � $m+1$~����������; ������ ��� ���������� ���� 
����, ����� �������� �������� �� ��� ����� ������, �����������, ��������, 
$j$~������ � $j+1$~����������. � ����-���� 
���������� ����~$\overline{K}_f$, ����������� ����� ���� ���� �������; 
������������ ��� ����� ���������� ���:
\picture{���. ���. 568}
��� $j<m-1$ ������� �������������� ������ ����������� ��������: �� 
��������� $\ceil{(m+j)/2}$~������ � ����� ����, �������� � 
����-����~$\overline{K}_f$ ��~$K_{\floor{(m+j)/2}+1}$,. � ��������� ����� 
(�� $\ceil{(m+j)/2})$ � ��������������� ��������� �������� � ������ ����. 
 �� �������, ������� "������������" � �������� ����. ���� �� �� ��� 
����� ($j=m-1$), ����� ��������� \emph{���} ����, ������� ��� ����������� 
�������� �� ��� ����� ����, ���������� �������������� $\floor{(2m-2)/3}$,
 $\floor{(2m-1)/3}$ � $\floor{2m/3}$~������:
\picture{���. ���. 568}
%%569
���� � ��������� ���� ��� ������� �����, ������� ��������� ������� 
������������ ������. (���� �� ���������� ��� �����, ����� ������������ �� 
�����������, ���� ��� �� ����������.) �������, ���� ������������ ���� �� 
����� �������, �� ��� ����������� ������; �� ����� �������� ����������� 
$B\hbox{-������}$, ��������, ����� ������ �������� �� 
$2\floor{(2m-2)/3}$~������, ��� ��� ��� ����� ����������� �� ��������� ��� 
����, � ������ �� ������� $\floor{(2m-2)/3}$~������.

����������� ����������� ��������� "������� �����, ������ ���" ��������; 
������� �� $B^*\hbox{-���������}$ � ��������� ��������� �������:

\medskip
\item{i)} ������ ����, ����� �����, ����� �� ����� $m$~�������.

\item{ii)} ������ ����, ����� ����� � �������, ����� �� �����
$(2m-1)/3$~�������.

\item{iii)} ������ ����� �� �����~2 � �� ����� $2\floor{(2m-2)/3}+1$~�������.

\item{iv)} ��� ������ ����������� �� ����� ������.

\item{v)} ㇋�, �� ���������� �������� � ������� $k$~�������, �������� 
$k-1$~������.
\medskip

\noindent ������ ��������� ���������� ������� (ii), ������������, ��� �� 
���������� �� ������� ���� ��� ����� ���������� � ������ ���� 
������������. ⅌ ����� ���������� � �����, ���. ��� � ��������~(6) �~(7) 
�������� "$\ceil{m/2}$" ������� �������� �� "$\ceil{(2m-1)/3}$".

��������, �������� ������� � $B\hbox{-��������}$ ����������� ��-�� ����, 
��� ������� ����� ����� ���� �����~2. ����� ������� ����� ��������� � 
����� ���� ������������ ����� ���� �� ��� ����? ������� ����� �����������, 
���������� "���������� ������ ����� �� ���������������� ��������", 
�������� ���������� ��� ����������; �� ����� �������� �� ���������� 
������ ��������� �������, ��� ��� ������� ��������� ����� ����� �� �����, 
���� ��������������� �������� ��� ������������ � ������. ��� ����� ����� 
��������� ������ ��� ������� ��������� ������� "������������ ������", 
������� �� ����� ���� ������������� � ���������� �����, ���� ���� ������ 
�������� ��� � ������; ����������� ������� "������������" �����������, 
����� ���������� � ������ ���������� �, ��������, �������� ����������. 
���� ��������� �������������� ������, �� �������� �����, ������������� 
����� ������, ���������� ��� ������� �� ����, ���� �� ��������� � ������� 
����������, ����� � ��������� ����� ��������� ������ ��������.

  ��� ����� ������� ������ ������ ���� �� ���������. � ������ �������, 
����� ���������� ������� ������������ ���������� ����������� � ������ 
�������� ��������; �� �� �����
%%564
����� ���������� � ��������� ������� ������, ���� ������ ����� ��� ��� ��� 
����. ����� ���� �� ������ ����������� �������� ��� ����������� 
����������� ����������� ������������� ������������ ���������� ������� � 
����� �������. ��������, ��� ������������ ����� ������������� 
������������ ����������� � ������ �������, ����������� ��� 
���������� �����������, ������� ����� ������������ ��� ��������.

ᓄ� �� �������������, ����������� �.~���-�������, ��� ���� ��������� 
������ �������. ��������, �� ���������, ��� � ������� ��������� ���������� 
�~$m=121$ ������� ������� � ������������ ������� 100000~������ ���������� 
���� 22~�������������� ������� ������ � 857~�������������� ������ ������; 
����� �������, ������� ����� �������� ������������� �� ���������� ������. 
�����, ������ ��������� ���� 835~�����---����� ��~1 ������ ���������� 
���������� ��������~$\ceil{100000/(m-1)}=834$, �.~�. ������ �������������� 
����� ��~100\%. ��� ����� ������������ ���-����� �������� 
������� �����������, �� � ������������ �� ��� �����, ��� �~(4), � �� �� 
���, ��� �~(9). (�.~���.~3.)

� ������ ������������ (���� � 10~��������, $m=121$ � ��� �� �������� 
�����������) �� ������� � ������������� ������ ������ 5000~������ � 
��������� �������. ���������� ������������� ������ � 48~������ (������ 
�������������� ��~87\%), � ������������� 2762~�������������� ������� 
���������� � 2739~�������������� ������ ������. ����� ����� 
1000~��������� ������� 786~��� ����������� ��������������, 
����������. ⎒ �� ����������� \emph{���} ������ ����������� ����� 
2743~�������������� ���������� � 2800~�������������� ������� ������ � 
�������������� ������ � 62~������ (67\% ������������� ������); 
1000~���������������� ��������� ������� ����������� 836~�������������� 
����������. 풎 ���������� �� ������ ������������� ���������� �����, �� 
����� ���������� ��������� ��������� ������������ ������ ������������ 
�����������. 퍄�� � �������, ��� ������� ����� ����� ����� ��������� 
������� ��� ����������� ��� �������~$N$ �~$m$ 
�������� $N/(m\ln2)+O(N/m^2)$, ��� ��� ������ ����� �������������� 
�������� ��~$\ln 2=0.693$ [{\sl Acta Informatica,\/} ����� ������������].

\excercises
\ex[10] ����� $B\hbox{-������}$ �������~7 ��������� ����� ������� 
�����~613 � ������ ���.~30? (����� ����������� �� ���������.)

\ex[15] ��������� ���.~1, ��������� ����� ����������� � ������������ �� 
��� �����, ��� �~(9).

\rex[23] �����������, ��� ����� 1, 2, 3,~\dots{} � ������������ 
������� ����������� � ������������� ������ $B\hbox{-������}$ �������~101. 
����� ���� ������� �������� � ��������� ������� �� ������ 4: (a) ���� �� 
������������
%%571
�����������; (b) ���� ������������ ����������� ���� � ������������ �� ��� 
�����, ��� �~(4); (c) ���� ������������ $B^*\hbox{-�������}$ �������~101 � 
������������ �� ��� �����, ��� �~(9)?

\ex[21] (����� �~���-�����.) ���������, ��� ����������� ������� � 
���������� $B\hbox{-������}$, ����� ��� ����, ����� ����� � �������, 
����� �� ����� ${3\over4}m-{1\over2}$~ �������.

\rex[21] �����������, ��� ��� ���� ��������� �� 1000~������ ������� ��� 
����� �� ������� ������. ���� ������ ������ �������� 5~������ � ���� ����� 
����� ����������, �� �������~5 ����� ��~5 ��~50 ������, �� 
����� ����������� ����� ������ ����� ���� ������ � ���� ����� ��� 
����������� � �������� �������? (����������� ���� ������� ��������� 
�����������, ����������� ��������� � ������ ��� $B\hbox{-��������}$ � 
������� ������������� �����, ��� �����������.)

\ex[22] ����� �� ������������ ���� $B\hbox{-������}$ ��� ������� 
��������� ��������� ������ �� �������, � �� �� �������� �����? (�. � 
����������~6.2.3�.)

\ex[23] ���������� �������� �������� ��� $B\hbox{-��������}$.

\ex[28] ���������� �������� ������������ $B\hbox{-��������}$ (��. �~�.~6.2.3).

\ex[30] ���������, ��� ������� ����, �������������� � ���� 
$B\hbox{-������}$, ����� ������������ ��� ������� � ��������� �� ������� 
�������� ����� ������������ ���������� ������������� ���, ����� 
������������ ��������� ������� ����������� �� ��������� ����� ���� �����.

{\catcode`\!=\active\def!{\hfill}
\ex[��37] ���������� ��������� ������� � ������, ������������ ������ 
�~㇃������, ����� ������ �������� ����� ��������� $M$~������. ����� �� 
�������� � ����� ������ $N$~��������� ���������; ������ ��� ����� 
$N+1$~������� �����. ��������� �����~$b^{(j)}_{Nk}$ ����������� ����, ��� 
��������� ����� ������� ��������� � $k$~��������� � ��� �������������� 
���� �������� ����, ��� ��������� �����, ����������� � ��������, 
���������� $j$~������. ����� 
$B^{(j)}_N(z)=\sum b^{(j)}_{Nk} z^k$---��������������� ������������ �������. 
��������, ���
$$
\displaylines{
B^{(j)}_1(z)=\delta_{j1}z;\cr
B^{(j)}_N(z)={N-j-1\over N+1}B^{(j)}_{N-1}(z)+{j+1\over 
N+1}B^{(j-1)}_{N-1}(z),
\qquad 1<1<M;\cr
B^{(1)}_N(z)={N-2\over N+1}B^{(1)}_{N-1}(z)+{2z\over N+1}B^{(M)}_{N-1}(z);\cr
B^{(M)}_N(z)={N-1\over N+1}B^{(M)}_{N-1}(z)+{M+1\over N+1}B^{(M-1)}_{N-1}(z).\cr
}
$$
������� ��������������� ��������� 
$C'_N=\sum_{1\le j\le M} {B^{(j)}_N}'(1)$---�������� ����� �������, � ������� 
���������� ��������� � 
�������� ���������� ������. [\emph{㊀�����:} �������� ������������ 
����������� � ������� �������
$$
W(z)=\pmatrix{
-3 & !0 & \ldots & !0! & !2z! \cr
!3 & -4 & \ldots & !0! & !0!\cr
!0 & !4 & \ldots & !0! & !0!\cr
!\vdots & !\vdots & & !\vdots! & !\vdots! \cr
!0 & !0 & \ldots & !-M-1! & !0!\cr
!0 & !0 & \ldots & !M+1 & -2! \cr
}
$$
� ����������� $C'_N$ � ����������� $N\hbox{-�}$~������� �~$W(l)$.]
\par
}
%% 572

\bye
