\input style
%% 181
$7A+14B+4C+20N-2D+15\lfloor N/2 \rfloor -28$ �����, ����� �������, � 
������� �������� $16N \log_2 N+0.2N$ ������.

����� �� ����.~2, ������ �������� � ��, ��� ������������� ���������� ��� 
�� ����������: ������� ����� ������������ ����� ������, ��� �� �������� 
�������� �� ������! ��� � � ����� ���� �������� ������ ���������� ��� 
����� $N$. ����� ���������� 16 ������ �� ����.~2 ����� $1068u$, ����� ��� 
������� ����� ������� ������� (��������� 5.2.1S) ������� ����� 
$514u$. ��� ���������� ������� ������� (��������� S) ��������� $853u$.

��� ������� $N$ ��������� H ����� ����������. ������������� ��������� � 
����������� ������� ����� � ��������� ����� (��������� 5.2.1D) � ������� 
����������� ����� (��������� 5.2.2Q), ��� ��� �� ���� ���� ���������� 
���������� ������������ ����� ��������� ������, ������ 
��������������� ������ ������������ ���� ��� ��� �� ������������ �����. 
��� $N=1000$ ������� ������� ������ ����� ��������������
$$
\eqalign{
160000u & \hbox{ ��� ������������� ����������;}\cr
130000u & \hbox{ ��� ���������� ������� �����;}\cr
  80000u  &\hbox{ ��� ������� ����������.}\cr
}
$$
(\MIX---�������� ������������� ����������� ����������� �������������� 
�����, ��, ����������, �� ���������� ������� ��������� ��������� ���� 
������������� ��������.) � ������ $N$ ������������� ���������� ���������� 
�� �������� ����� �����, �� ��������������� ������� $16N\log_2 N \approx  
23.08N\ln N$ ������� �� ������ ����� ��������� ��� ������� ���������� 
$12.67N \ln N$. ����������� ������������� ����������, ����������� � 
���.~18, ������� ������� �� ������ �������������� �������, �� ���� � ���� 
������������������� ������������� ���������� �� ��������� �������� ������� ����������.

� ������ �������, ������� ���������� ���������� ���� � �������; � 
��������� ������ �� ����� ������ ��������������� $N^2$. ������������� �� 
���������� �������� ��� ���������� ���������, ��� ��� ��� ��������� 
������ �� ������� ���� ��������. ������ ����������� �����������
$$
A\le 1.5 N, \quad B \le N \lfloor \log_2 N \rfloor, 
\quad C\le N\lfloor \log_2 N\rfloor;
\eqno (8)
$$
����� �������, ���������� �� ������������� �������� ������ ���������� 
��������� H �� ������ ����� 
$18N \lfloor \log_2 N\rfloor+38N$
������ �������. ������������� ����������---������ �� ������������� ���� �� 
��� ��� ������� ����������, ����� ������ �������� \emph{��������} ����� 
������� $N\log N$. ���������� ����������� �������, ������� ����� 
����������� ����, � �.~5.2.4, ���� �������� ���� ���������, �� ��� ������� 
������ ������.

%% 182

\section ���������� �� ����������---������ �����������. 
� ��. 2 ��
������, ��� �������� ������ ����� ����� ���������� ������������������� 
�� ��������� ������������ ��� ���� �������� ��������� � ����������. 
\emph{����} ����� ���� �� �������� "��������� ����������---������ 
�����������" � ��� ������, ��� ��� ������ ���������� ��������� ����� 
������� ������� ������ (�������, ������� ��� �������� ����� ���� ������ 
���������, �������������� � ������ ������ � ������). ������� 
\emph{�������} ����� ���� �� �������� "������ ����������---������ 
�����������" � ��� ������, ��� ��� ������ ���������� ��������� ����� 
������� �� ��������� ���������. � ����� ������� ���������, �����, ��� 
������������� ����� � �.~2.2.5, ��������� ������ ���� "���������� �� 
����������---������ �����������", ��� ��� ������ ���������� ��������� 
�������, ������� ���������� ����. ����� ������ ����� 
������� \dfn{������������ ��������}, ��� ��� ���� ������� �������� 
�������� ��� ������������� ����������� ������ �������� 
������. ���������� ����������� ������---������� ������ ������������ �������, 
��� ������� ������������ ������� $N$ �������� �������, � ����� $N$ 
�������� ��������.

������������ ������� ��������� � ����� ������������� �����������. ��������,
 � ��������� ��������� ����������� ������ ����������� ����� ��������, 
�������� ���������� (��� ����������) �������� ���������� ������������ 
��������; ��������� ���������� �������� ����������, � �� ����� 
����������� � ������ � ����� ����������� ���������,- ��������������� ����� 
��������� ����������. ������������ ������� ����� ������������ � 
������������ �������� ��� ������������ �������. ������ �������� 
���������� ������������ �������� ����������� � ���.~15, 29 �~36; ����� 
����, ����� �������� ���������� � ����������� ������.

��� �� ����������� ������������ �������? ���� �� ��������� 
��������---������������ ��������������� ������ ���������, ������������� ��. 
������. ����� ��������� ������ ��������, �� ��������, �������� � ������, 
������������� ���� ��� �������� ���������� ��������� � �.~5.2.1. ��� 
������, ��� ����� ��������� ������� ������ � ������������ �������� 
�������� � ������ �������� � ������������ �������, � ����� ��� 
������ ������� ��������, ���������� ������������ ����� ����������� (��� 
�����������) ����� ������ ���, ����� ���������� ���������� ����������. � 
����� ���� ��������� �������� ������������ ������� � ���, ��� ��������� 
������� $N$ ����� ��� ���������� ���� �������� �������, ���� �������� 
��������, ���� � ������ ���������� $N$ ���������, �. �. ��� ������� $N$ 
��� �������� �������� ������� ����� �������.

� ����� ������ � ������������� ���������� ������� ������
%% 183
�� ��, ��� �������� �������� �������� ��� ���������� � �������� 
������������� ���������, ��� ��� ������� ����� �������� � �������� ��� 
������� �� ��� �� $O(\log N)$ �����; � ���� �� ��� �������� �������� 
��������� ������������� � ���������������� ������� ������. ���� ������ � 
��������� H---��� ������������������ ����� �������� � �������� ���� 
\emph{���������� �� ����������---������ �����������}: ����� ��������� 
���������� ������� $K_1$ �� ������� ��� � "������������" ������� $K_N$ � 
����� �������� �� $N-1$ ���������. (���� ����� �������� ���� 
\emph{���������� �� ����������---������ �����������}, ��� ��� ������������� 
�����, ��, ��������, ����� �������� ����������� ��������, ������� � (3) 
���� "$\ge$" �� "$\le$"; ��� �������� �� ����� ������������� ����� ���� 
������ "���������� �� ����������---������ �����������".) ������, ���� 
��������� ��������� ���������� �������, � ����� �������� ����� ������� 
$x$, �� ����� ��������� ��������� ������������� � $l=1$, $r=N$ � $K=x$. 
���� �� ���������� �������� ������� ��� ���������������� ����������, �� 
����� ��������������� "����������" ���������� �� ���. 16.

\section ��������� ������������� ������������ ��������. 
����������� ������ ������������� ������������ �������� � ���� 
��������� �������� �������� ��������� � 1971~�. �����~�.~�����. ��� ����� 
������� ������� � ������ ������ ���� ����� ����� � ��������� ���� 
��������, �� �� ��������� � ���������� �� �������� ���������� ��������������:
\enumerate
\li ���� � ������������ �������� �������� ��� �� ������, �� �������� 
��������� � ���������� ����� ���������� (��� �������� ������������� �����, 
�� ��������� �� ����� �������).

\li ������ ������� �� ������������, ���������� ������ ���������.

\li  ����� ����� ��� ���������������� ������������ �������, ���������� � 
����� ��������� $N$ ���������, � ���� ����� �� $O (\log N)$ �����.
\enumend

������ �������������� ����� ������ ���������������� �� ���.~27, �� ������� 
������� ������ ��� ��������� ��������� ������. ������ ���� �������� ���� 
|KEY|, ���� |DIST| � ��� ���� �����---|LEFT| � |RIGHT|. ���� |DIST| ������ 
��������������� ������ ����� ����������� ���� �� ����� ���� �� 
��������� ���� (�. �. �� ������� ���� $\NULL$) ������. ���� �������, 
��� $|DIST|(\NULL) = 0$ �~$|KEY|(\NULL) =-\infty$, �� ���� |KEY| �~|DIST| 
� ���� ������ ������������� ��������� ������������:
$$
\displaylines{
\hfill|KEY| (|�|)\ge  |KEY| (|LEFT| (|P|)), |KEY| (|P|) \ge |KEY| (|RIGHT| 
(|P|));     \hfill\llap{(9)}\cr
\hfill|DIST| (|P|)=1+\min (|DIST| (|LEFT| (|P|)), |DIST| (|RIGHT| (|P|))); 
\hfill\llap{(10)}\cr
\hfill|DIST| (|LEFT| (|P|)) \ge  |DIST| (|RIGHT| (|P|)).\hfill\llap{(11)}\cr
}
$$
%%184
����������� (9) ���������� ������� �������� (3) � ������ ��������� ����, 
��� � ����� ������ ��������� ���������� ����, � ����������� (10)---��� 
������ ����������� ���� |DIST|, ���������������� ����. ����������� (11) 
������������ ����� ���������� ���������: �� ���� �������, ��� ���������� 
���� � ��������� ���� ������ ����� ��������, �������� ������. ��
\picture{���. 27. ������������ �������, �������������� � ���� 
�������������� ������.}
����� �������� �������� ������ � ���� ��������� ������������� �������, 
��������� ���, ��� �������, ������ "�������" �����.

�� ���� ����������� ����, ��� ��������� $|DlST|(|P|)=n$ ������������� 
������������� �� ������� ���� $2^n$ �������� ����� ���� |P|; � ��������� 
������ ������� �� �����, �������� ���� �� |P| �� ��������� ����. ����� 
�������, ���� � ������������� ������ ������� $N$ �����, �� ����, ������� 
�� ����� ���� �� ����������� ������, �������� �� ����� ��� $\lfloor 
\log_2(N+1)\rfloor$ �����. ����� ���� ����� �������� � ������������ 
�������, ������ �� ����� ���� (��. ���.~32); �������������, � 
������ ������ ���������� ����� $O(\log N)$ �����. ��������� ������
%%185
�����������, ����� ������ ������� (��� ����� |RIGHT| ����� $\NULL$), � 
��������� ������ �����������, ����� ������ ��������� ��������������.

����� ������� ���� �� �����, ����� ������ ����� ��� ��� ���������. 
�������� ������� ���� ���������������� ������������� ��������, �� 
������� ��������� ��������� |P| �~|Q|, �� ����� ���� ������: ���� 
$|KEY|(|P|)\ge |KEY| (|Q|)$, �� ����� � �������� ����� |P| � ������� |Q| � 
������ ���������� |P|; ��� ���� ��������� $|DIST|(|P|)$, a $|LEFT|(|�|)$ 
�������� ������� � $|RIGHT|(|P|)$, ���� ��� ����������. �������� ��������� 
��������� �������� ����� �������� (��. ���.~32).

\section ��������� ������� ������ � ������������� ���������. ���� ����� 
����� $N$ ����, �� ��� ����������� ������������ ������� ����� ����� 
��������� ���� �� ������� ������� � �������������� �������� �������. 
���� �� $N$ ������, ��, ��������, ������� ����� ������� ����� �����, ����� 
������ �������� ������� $\log N$. ������� ������� ������������ ������� ������
������������ � ���� ������� ��� ������������� ��������. � �.~6.2.3 �� 
������� ��� ���� ������ ������������� �������� ������� � ���� 
\emph{���������������� ��������}, ������� �������� � �������� ������, 
���������� ��� ������������� ������������ ��������, � �������� ������ 
������� $\log N$. ������� ������� �������� ��� ��� ������.

�� ������, ��� �������� ��� �������������� ��������� � ����� ��������� 
�������, ��� �������� ��� ����������, �� �������� �������� ������ ������. 
���������������� ������� �������� �������� ������� �� ������, ������� 
������������� ������� (���� �����, ���� ������); �������� ��� ���� 
���������, ��� ��� ����������, � ���������������� �������, �� ��������� 
���������������� �������� � ��������� ���������� ����������� ����� ������. 
������� � ����������, �� ��� ������ �����������, ��� ���������� � 
����������, ���� � ��� ������ �����; ������ �������������, ��� �������� � 
������� ������� ����� �������������� �� �������� "��������� 
����������--- ������ �����������" ��� "������ ����������---������ 
�����������", ���� ������ ���� �� �������� � �� �������� 
��������������� ���� "���������� ����� �������", � ����� ������ ������ 
������ ���. � ������ �������, ���� ��������� ���������������� �������, 
����� ����� ��������� ������� �������
������������ ������ ������. ����� ����� ��������� ����� ��������, ��� 
"�������� $x$ ��������������� ����� (��� �����) $y$". ���������������� 
������� �����������, ��� ��� � ����� ������ ����� ��������� ���� 
����������, ���� ���������� �������,
� �� ����� ��� ������������� ������� � �������� ������ ����
��� ��� ����� �������������. (��. ��� �� ����� ���.~31, � �������
%% 186
\picture{���. 28. ��� �������� ��������...}
%%187
��������, ��� ������� \emph{������������} ��������.) 
���������������� ������� ����� ������������ ��� ��� ������, ��� � ��� 
����������; � �� ����������������� ������ ����� �������� ������ ������� 
���������������� ����� ���������. �� ��� ���������������� ������ ������ 
����� ����� ��� �� $O(N)$ �����, � �� ����� ��� ��� ������������� ������ 
����� ����� ����� �� $O (\log N)$ �����.

����, �������� �������� �������� � ����� ������ ������;
������������� ������� ������ ���, ��� ����� ������ ����� ��� 
���������������� ������������ �������; �, ���� �����, �� ��������� 
�������������� ����� �������� �� ��������, ����� ������������� 
���������������� �������.

\section * ������ ������������� ����������. �������� H �� ��� ��� �� ��� 
��������� ���������������, �� ��������� ��� �������� ����� ������� ��� 
������� �����. ������� �� �������� ���� ����� �������� ��������� 
�������������, ���������� �������.

�� ���. 28 �������� ����� �������� �� 26 ���������;
������ ���� ������� �������� ������, ��������������� ��� ������� � 
��������. ����������� � ���� ��������� ��������
��� ���������� \dfn{������ ����}, ������� ����� �� ���� ��~1 �~$N$.

���� �� �������� ������ ������������� ��������---����� �������� �� 
�����������. ��������, �� ���.~28 ������� ����������� � ������� � ����� 
1,2, \dots, 26 ����� ��������������
$$
26^*, 15,10^*, 7, 7, 6^*, 3, 3, 3, 3, 3, 3, 2^*, 1,1,1,1,1,1,1,1,1,1,1,1, 1^*.
\eqno (12)
$$
����������� �������� \dfn{������ ����������} � ������� � ������ �����; � 
���.~20 ��������, ��� ���� $N$ ����� �������� �������������
$$
N=(b_n b_{n-1} \ldots b_1 b_0)_2, \qquad n=\lfloor\log_2 N\rfloor,
\eqno (13)
$$
�� ������� ������ ����������� �����
$$
(1 b_{n-1}\ldots b_1 b_0)_2, (1 b_{n-2}\ldots b_1 b_0)_2, \ldots,
(1 b_1 b_0)_2, (1 b_0)_2, (1)_2.
\eqno(14)
$$
(�������� ���������� ������ ��������� ��������������, ��� ��� �� ������� 
������ ����� ��� $2^k-1$. � ���.~21 ��������, ��� ����� �������� 
����������� ������� �����
$$
\matrix{
\hbox{$\lfloor(N-1)/2 \rfloor$ �������  1,} &  & 
\hbox{$\lfloor(N-2)/4\rfloor$ ������� 3,}\hfill\cr
\hbox{$\lfloor(N-4)/8\rfloor$ ������� 7,} & \ldots  & 
\hbox{$\lfloor(N-2^{n-1})/2^n\rfloor$ ������� $(2^n-1)$,}\hfill\cr
}
\eqno(15)
$$
��������, �� ���.~28 ���������� ���������� �������� ����������� 
�������~1, ����� ����������� �������~3, 
���---�������~7 � ����---�������~15.
%%188

\bye