\input style
\chapno=6\subchno=1\chapnotrue

%% 483
\subchap{poisk posredstvom sravneniya klyuchej} %% 6.2

v |TOM PARAGRAFE MY RASSMOTRIM METODY POISKA, OSNOVANNYE NA LINEJNOM 
UPORYADOCHENII KLYUCHEJ (NAPRIMER, PORYADOK MOZHET BYTX CHISLOVYM ILI ALFAVITNYM).
 pOSLE SRAVNENIYA DANNOGO ARGUMENTA~$K$ S KLYUCHOM~$K_i$ IZ TABLICY POISK 
PRODOLZHAETSYA ODNIM IZ TREH SPOSOBOV V ZAVISIMOSTI OT TOGO, KAKOE IZ 
SOOTNOSHENIJ VERNO: $K<K_i$, $K=K_i$, $K>K_i$. pRI 
POSLEDOVATELXNOM POISKE MY, V SUSHCHNOSTI, DOLZHNY VYBIRATX ODNO IZ DVUH 
PRODOLZHENIJ ($K=K_i$ ILI~$K\ne K_i$), NO ESLI MY OSVOBODIMSYA 
OT OGRANICHENIYA IMETX LISHX POSLEDOVATELXNYJ DOSTUP K TABLICE, TO POLUCHIM 
VOZMOZHNOSTX |FFEKTIVNO ISPOLXZOVATX OTNOSHENIE PORYADKA.

\subsubchap{ pOISK V UPORYADOCHENNOJ TABLICE} % 6.2.1

chTO VY STANETE DELATX, ESLI VAM VRUCHAT BOLXSHUYU TELEFONNUYU KNIGU I 
POPROSYAT NAJTI IMYA CHELOVEKA, NOMER TELEFONA KOTOROGO 795-68-41? zA 
NEIMENIEM LUCHSHEGO PRIDETSYA VOSPOLXZOVATXSYA METODAMI POSLEDOVATELXNOGO 
POISKA, IZLOZHENNYMI V \S~6.1. (pRAVDA, LOVKIJ CHASTNYJ DETEKTIV MOG BY 
POPYTATXSYA NABRATX NOMER I SPROSITX, KTO GOVORIT; NE ISKLYUCHENO TAKZHE, CHTO 
U NEGO ESTX DRUZXYA NA TELEFONNOJ STANCII, IMEYUSHCHIE DOSTUP K SPRAVOCHNIKAM, 
GDE TELEFONY RASPOLOZHENY V PORYADKE VOZRASTANIYA NOMEROV.) dELO V TOM, CHTO 
GORAZDO LEGCHE NAJTI ZAPISX PO FAMILII ABONENTA, A NE PO NOMERU, HOTYA 
TELEFONNAYA KNIGA SODERZHIT VSYU INFORMACIYU, NUZHNUYU V OBOIH SLUCHAYAH. 
eSLI NEOBHODIMO NAJTI ZAPISX V BOLXSHOM FAJLE, O POSLEDOVATELXNOM POISKE 
POCHTI NE MOZHET BYTX RECHI, NO ISPOLXZOVANIE OTNOSHENIYA PORYADKA V OGROMNOJ 
STEPENI OBLEGCHAET RABOTU.

v NASHEM RASPORYAZHENII ESTX MNOGO METODOV SORTIROVKI (GL.~5), PO|TOMU DLYA 
NAS NE SOSTAVIT TRUDA UPORYADOCHITX FAJL, CHTOBY ZATEM BYSTREE PROIZVESTI 
POISK. rAZUMEETSYA, ESLI NUZHEN LISHX ODNOKRATNYJ PROSMOTR, TO BYSTREE 
PROIZVESTI EGO POSLEDOVATELXNO, BEZ PREDVARITELXNOJ SORTIROVKI. nO ESLI V 
ODNOJ I TOJ ZHE TABLICE PRIHODITSYA CHASTO PROIZVODITX POISK, TO 
|FFEKTIVNEE UPORYADOCHITX EE. v |TOM PUNKTE MY IZUCHIM METODY POISKA V 
TABLICAH SO SLUCHAJNYM DOSTUPOM I UPORYADOCHENNYMI KLYUCHAMI
$$
K_1<K_2<\ldots<K_N.
$$
%% 484
pOSLE SRAVNENIYA $K$ I~$K_i$ MY IMEEM ILI
$$
\eqalign{
&\bullet K < K_i \rem{[$R_i$, $R_{i+1}$,~\dots, $R_N$ ISKLYUCHAYUTSYA IZ RASSMOTRENIYA],}\cr
\hbox{ILI }&\bullet K=K_i \rem{[POISK ZAKONCHEN],}\cr
\hbox{ILI }&\bullet K>K_i \rem{[$R_1$, $R_2$,~\dots, $R_i$ ISKLYUCHAYUTSYA IZ RASSMOTRENIYA].}\cr
}
$$
uMELO DEJSTVUYA V KAZHDOM IZ |TIH SLUCHAEV, MY S|KONOMIM MNOGO VREMENI PO 
SRAVNENIYU S POSLEDOVATELXNYM POISKOM, ESLI TOLXKO $i$ NE SLISHKOM BLIZKO K 
KONCAM TABLICY. tAKIM OBRAZOM, UPORYADOCHENIE VEDET K |FFEKTIVNYM ALGORITMAM.

\section bINARNYJ POISK. pOZHALUJ, PERVYM PRIHODIT V GOLOVU SLEDUYUSHCHIJ 
OCHEVIDNYJ METOD: SNACHALA SRAVNITX~$K$ SO SREDNIM KLYUCHOM V TABLICE. 
rEZULXTAT SRAVNENIYA POZVOLIT OPREDELITX, V KAKOJ POLOVINE FAJLA PRODOLZHITX 
POISK, PRIMENYAYA K NEJ TU ZHE PROCEDURU, I T. D. pOSLE NE BOLEE CHEM 
PRIMERNO $\log_2 N$ SRAVNENIJ LIBO KLYUCH BUDET NAJDEN, LIBO BUDET 
USTANOVLENO EGO OTSUTSTVIE. tAKAYA PROCEDURA INOGDA NAZYVAETSYA 
"LOGARIFMICHESKIM POISKOM" ILI "METODOM DELENIYA POPOLAM", NO NAIBOLEE 
UPOTREBITELXNYJ TERMIN---\dfn{BINARNYJ POISK.}

oSNOVNAYA IDEYA BINARNOGO POISKA DOVOLXNO PROSTA, DETALI ZHE NETRIVIALXNY, I 
DLYA MNOGIH HOROSHIH PROGRAMMISTOV NE ODNA POPYTKA NAPISATX PRAVILXNUYU 
PROGRAMMU ZAKONCHILASX NEUDACHEJ. oDNA IZ NAIBOLEE POPULYARNYH REALIZACII 
METODA ISPOLXZUET DVA UKAZATELYA---$l$ I~$u$, SOOTVETSTVUYUSHCHIE VERHNEJ 
I NIZHNEJ GRANICAM POISKA, I SOSTOIT V SLEDUYUSHCHEM.

\alg v.(bINARNYJ POISK.) s POMOSHCHXYU DANNOGO ALGORITMA RAZYSKIVAETSYA 
ARGUMENT~$K$ V TABLICE ZAPISEJ $R_1$, $R_2$,~\dots, $R_N$, KLYUCHI KOTORYH 
RASPOLOZHENY V VOZRASTAYUSHCHEM PORYADKE: $K_1<K_2<\ldots<K_N$.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $l\asg 1$, $u\asg N$.

\st[nAHOZHDENIE SEREDINY.] (v |TOT MOMENT MY ZNAEM, CHTO ESLI $K$ ESTX V 
TABLICE, TO VYPOLNYAYUTSYA NERAVENSTVA $K_l\le K\le K_u$. bOLEE TOCHNOE 
OPISANIE SITUACII PRIVODITSYA NIZHE, V UPR.~1.) eSLI $u<l$, TO ALGORITM 
ZAKANCHIVAETSYA NEUDACHNO; V PROTIVNOM SLUCHAE USTANOVITX 
$i\asg\floor{(l+u)/2}$: TEPERX $i$~UKAZYVAET PRIMERNO V SEREDINU 
RASSMATRIVAEMOJ CHASTI TABLICY.

\st[sRAVNENIE.] eSLI $K<K_i$, TO PEREJTI NA \stp{4}; ESLI $K>K_i$, TO 
PEREJTI NA~\stp{5}; ESLI $K=K_i$, ALGORITM ZAKANCHIVAETSYA UDACHNO.

\st[kORREKTIROVKA~$u$]. uSTANOVITX $u\asg i-1$ I VERNUTXSYA K SHAGU~\stp{2}.

\st[kORREKTIROVKA~$l$.] uSTANOVITX  $l\asg i+1$ I VERNUTXSYA K SHAGU~\stp{2}.
\algend
%%485
\picture{rIS. 3. bINARNYJ POISK.}

rISUNOK~4 ILLYUSTRIRUET POVEDENIE ALGORITMA v V DVUH SLUCHAYAH: KOGDA 
RAZYSKIVAETSYA ARGUMENT, RAVNYJ IMEYUSHCHEMUSYA V TABLICE CHISLU~653, I KOGDA 
RAZYSKIVAETSYA OTSUTSTVUYUSHCHIJ ARGUMENT~400. sKOBKI SOOTVETSTVUYUT UKAZATELYAM 
$l$ I~$u$, PODCHERKNUTYJ KLYUCH PREDSTAVLYAET~$K_i$. v OBOIH SLUCHAYAH POISK 
KONCHAETSYA POSLE CHETYREH SRAVNENIJ.

\prog B.(bINARNYJ POISK.) kAK I V PROGRAMMAH \S~6.1, PREDPOLAGAETSYA, CHTO 
$K_i$ ZANIMAET POLNOE SLOVO PO ADRESU $|KEY|+i$. pRIVODIMAYA NIZHE PROGRAMMA 
ISPOLXZUET $|rI1|\equiv l$, $|rI2|\equiv u$, $|rI3|\equiv i$.
{\catcode`\!=\active\def!#1.{\underline{#1}}
 \catcode`\[=\active\def[{\hbox to 0pt{\hss$\lbrack$}}
 \catcode`\]=\active\def]{\hbox to 0pt{$\rbrack$\hss}}
$$
\displaylines{
\matrix{
\vbox{\halign{$\phantom{[}#\phantom{]}$\bskip&&$\phantom{[}#\phantom{]}$\bskip\cr
\noalign{\hbox{a)~pOISK CHISLA 653:}}
[061 & 087 & 154 & 170 & 275 & 426 & 503 &!509.& 512 & 612 &  653  & 677 & 703 & 765 & 897 & 908]\cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 & 612 &  653  &!677.& 703 & 765 & 897 & 908]\cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 &[512 &!612.&  653] & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 & 275 & 426 & 503 & 509 & 512 & 612 &[!653.]& 677 & 703 & 765 & 897 & 908 \cr
}}\hfill\cr
\vbox{\halign{$#$\bskip&&$#$\bskip\cr
\noalign{\hbox{b)~pOISK CHISLA 400:}}
[061 & 087 & 154 & 170 &  275  & 426 & 503 &!509.& 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908]\cr
[061 & 087 & 154 &!170.&  275  & 426 & 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 & [275  &!426.& 503]& 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 &[!275.]& 426 & 503 & 509 & 512 & 612 & 653 & 677 & 703 & 765 & 897 & 908 \cr
 061 & 087 & 154 & 170 &  275] &[426 & 503 & 509 & 512 & 612 & 658 & 677 & 703 & 765 & 897 & 908 \cr
}}\hfill\cr
}\cr
\hbox{rIS. 4.             pRIMERY BINARNOGO POISKA.}\cr
}
$$
}
%%486
\code
START & ENT1 & 1       & 1   & Bl. nACHALXNAYA USTANOVKA. $l\asg 1$.
      & ENT2 & N       & 1   & $u\asg N$.
      & JMP  & 2F      & 1   & nA B2.
5H    & JE   & SUCCESS & C1  & pEREHOD, ESLI $K=K_i$.
      & ENT1 & 1,3     & C1-S& B5. kORREKTIROVKA $l$. $l\asg l+1$.
2H    & ENTA & 0,1     &C+1-S& B2. nAHOZHDENIE SEREDINY.
      & INCA & 0,2     &C+1-S& $|rA|\asg l+u$.
      & SRB  & 1       &C+1-S& $|rA|\asg\floor{|rA|/2}$. (mENYAETSYA I~|rX|.)
      & STA  & TEMP    &C+1-S&
      & CMP1 & TEMP    &C+1-S&
      & JG   & FAILURE &C+1-S& pEREHOD, ESLI $u<l$.
      & LD3  & TEMP    &C    & $i\asg\hbox{\rm SEREDINA}$.
3H    & LDA  & K       &C    & B3. sRAVNENIE.
      & smra & KEY,3   &C    &
      & JGE  & 5B      &C    & pEREHOD, ESLI $K\ge K_i$.
      & ENT2 & -1,3    &C2   & B4. kORREKTIROVKA~$u$.
      & JMP  & 2B      &C2   & nA B2.
\endcode
\progend
dANNAYA PROCEDURA "REALIZUETSYA" NA MASHINE \MIX\ MENEE UDACHNO, CHEM 
PREDYDUSHCHIE, TAK KAK REGISTROVAYA ARIFMETIKA V \MIX\ NEBOGATA. vREMYA, 
RABOTY PROGRAMMY RAVNO $(18C-10S+12)u$, GDE
\picture{rIS. 5. bINARNOE DEREVO, SOOTVETSTVUYUSHCHEE BINARNOMU POISKU  ($N=16$).}
$C=C1+C2$---KOLICHESTVO PROIZVEDENNYH SRAVNENIJ (SKOLXKO RAZ VYPOLNYAETSYA 
SHAG~B3), $S=1$ ILI~0 V ZAVISIMOSTI OT UDACHNOGO ILI NEUDACHNOGO ISHODA. 
zAMETIM, CHTO STROKA~08 PROGRAMMY RASSHIFROVYVAETSYA KAK "SDVIG VPRAVO NA 
1" (shift right binary 1),
%% 487
CHTO DOPUSTIMO LISHX V DVOICHNYH VERSIYAH \MIX; V OBSHCHEM SLUCHAE EE SLEDUET 
ZAMENITX NA "|MUL =1//24+1=|", TOGDA VREMYA RABOTY PROGRAMMY UVELICHITSYA 
DO $(26C-18S +20)u$.

\section pREDSTAVLENIE V VIDE DEREVA. chTOBY DOSKONALXNO RAZOBRATXSYA V 
ALGORITME~B, LUCHSHE VSEGO PREDSTAVITX EGO V VIDE BINARNOGO DEREVA RESHENIJ. 
(nA RIS.~5 POKAZANO TAKOE DEREVO DLYA SLUCHAYA $N=16$.)

pRI $N=16$ PERVYM PROIZVODITSYA SRAVNENIE~$K:K_8$, CHTO PREDSTAVLENO NA 
RISUNKE KORNEVYM UZLOM~\node{8}. dALEE, ESLI $K<K_8$,  ALGORITM 
OBRABATYVAET LEVOE PODDEREVO, SRAVNIVAYA $K$ I~$K_4$,. ANALOGICHNO,  ESLI 
$K>K_8$, ISPOLXZUETSYA PRAVOE PODDEREVO.
nEUDACHNYJ POISK VEDET V ODIN IZ "VNESHNIH" KVADRATNYH UZLOV, ZANUMEROVANNYH 
OT~\leaf{0} DO~\leaf{$N$}; NAPRIMER, MY DOSTIGNEM UZLA~\leaf{6} TOGDA I 
TOLXKO TOGDA, KOGDA $K_6<K<K_7$.

bINARNOE DEREVO, SOOTVETSTVUYUSHCHEE BINARNOMU POISKU SREDI $N$~ZAPISEJ, MOZHNO 
POSTROITX SLEDUYUSHCHIM OBRAZOM: PRI $N=0$ DEREVO SVODITSYA K UZLU~\leaf{0}. v 
PROTIVNOM SLUCHAE KORNEVYM UZLOM YAVLYAETSYA
\picture{rIS. STR. 487}
LEVOE PODDEREVO SOOTVETSTVUET BINARNOMU DEREVU S $\ceil{N/2}-1$~UZLAMI, A 
PRAVOE---DEREVU S $\floor{N/2}$~UZLAMI I CHISLAMI V UZLAH, UVELICHENNYMI NA~$\ceil{N/2}$.

aNALOGICHNYM OBRAZOM \emph{LYUBOJ} ALGORITM POISKA V UPORYADOCHENNOJ TABLICE 
DLINY~$N$, PROIZVODIMOGO PUTEM SRAVNENIJ, MOZHNO PREDSTAVITX BINARNYM 
DEREVOM S UZLAMI, POMECHENNYMI CHISLAMI OT~$1$ DO~$N$ (PREDPOLAGAETSYA, CHTO 
ALGORITM NE SODERZHIT LISHNIH SRAVNENIJ). oBRATNO, LYUBOE BINARNOE DEREVO 
SOOTVETSTVUET NEKOTOROMU METODU POISKA V UPORYADOCHENNOJ TABLICE; MY 
PROSTO POMECHAEM UZLY
\picture{rIS. STR. 487}
V SIMMETRICHNOM PORYADKE SLEVA NAPRAVO.

eSLI ARGUMENT POISKA V ALGORITME~B ESTX $K_{10}$, TO PROIZVODYATSYA 
SRAVNENIYA $K>K_8$, $K<K_{12}$, $K=K_{10}$. nA RIS.~5 |TO SOOTVETSTVUET 
PUTI OT KORNYA K UZLU~\node{10}. aNALOGICHNO POVEDENIE ALGORITMA~B PRI 
DRUGIH~$K$ SOOTVETSTVUET INYM PUTYAM, VEDUSHCHIM IZ KORNYA DEREVA. s POMOSHCHXYU 
METODA POSTROENIYA BINARNYH DEREVXEV, SOOTVETSTVUYUSHCHIH ALGORITMU~B, I 
INDUKCII PO~$N$ LEGKO DOKAZYVAETSYA

\proclaim tEOREMA B. pRI $2^{k-1}\le N <2^k$ UDACHNYJ POISK,  ISPOLXZUYUSHCHIJ 
ALGORITM~B, TREBUET $(\min 1, \max k)$~SRAVNENIJ. nEUDACHNYJ POISK
%%488
TREBUET $k$~SRAVNENIJ PRI~$N= 2^k-1$ LIBO $k-1$ ILI $k$~SRAVNENIJ PRI 
$2^{k-1}\le N<2^k-1$. \endmark

\section dALXNEJSHIJ ANALIZ BINARNOGO POISKA. [rEKOMENDUEM NE 
INTERESUYUSHCHIMSYA MATEMATIKOJ PEREJTI SRAZU K SOOTNOSHENIYAM~(4).] 
pREDSTAVLENIE V VIDE DEREVA POZVOLYAET LEGKO PODSCHITATX \emph{SREDNEE} 
CHISLO SRAVNENIJ. chEREZ $C_N$ OBOZNACHIM SREDNEE CHISLO SRAVNENIJ PRI UDACHNOM 
POISKE V PREDPOLOZHENII, CHTO KAZHDYJ IZ $N$~KLYUCHEJ S RAVNOJ VEROYATNOSTXYU 
YAVLYAETSYA ARGUMENTOM POISKA. sREDNEE CHISLO SRAVNENIJ~$C'_N$ SOOTVETSTVUET 
NEUDACHNOMU POISKU; PREDPOLAGAETSYA, CHTO VSE INTERVALY (IH $N+1$) MEZHDU 
KLYUCHAMI I VNE KRAJNIH ZNACHENIJ RAVNOVEROYATNY. iMEEM PO OPREDELENIYU 
DLIN VNUTRENNEGO I VNESHNEGO PUTI
$$
\eqalign{
C_N&=1+{\hbox{\rm dLINA VNUTRENNEGO PUTI DEREVA}\over N};\cr
C'_N&={\hbox{\rm dLINA VNESHNEGO PUTI DEREVA}\over N+1}.\cr
}
$$
iZ FORMULY~(2.3.4.5-3) VIDNO, CHTO DLINA VNESHNEGO PUTI NA~$2N$ BOLXSHE DLINY 
VNUTRENNEGO PUTI; OTSYUDA SLEDUET DOVOLXNO NEOZHIDANNOE SOOTNOSHENIE MEZHDU 
$C_N$ I~$C'_N$
$$
C_N=\left(1+{1\over N}\right) C'_N-1.
\eqno(2)
$$
eTA FORMULA, POLUCHENNAYA hIBBARDOM [{\sl JACM,\/} {\bf 9} (1962), 16--17],
 SPRAVEDLIVA DLYA VSEH METODOV POISKA, SOOTVETSTVUYUSHCHIH BINARNYM DEREVXYAM, 
T.~E.~DLYA VSEH METODOV, NE SODERZHASHCHIH LISHNIH SRAVNENIJ. dISPERSIYA~$C_N$ 
TAKZHE MOZHET BYTX VYRAZHENA CHEREZ DISPERSIYU~$C'_N$ (SM.~UPR.~25).

iZ PRIVEDENNYH FORMUL VIDNO, CHTO "NAILUCHSHEMU" SPOSOBU POISKA PUTEM 
SRAVNENIJ SOOTVETSTVUET DEREVO S MINIMALXNOJ DLINOJ VNESHNEGO PUTI SREDI 
VSEH BINARNYH DEREVXEV, SODERZHASHCHIH $N$~VNUTRENNIH UZLOV. k SCHASTXYU, 
MOZHNO DOKAZATX, CHTO ALGORITM~B OPTIMALEN V |TOM SMYSLE, TAK KAK BINARNOE 
DEREVO IMEET MINIMALXNUYU DLINU PUTI TOGDA I TOLXKO TOGDA, KOGDA 
VSE VNESHNIE UZLY NAHODYATSYA NA ODNOM ILI DVUH SOSEDNIH 
UROVNYAH. (sM.~UPR.~5.3.1-20.) sLEDOVATELXNO, DLINA VNESHNEGO PUTI 
BINARNOGO DEREVA, SOOTVETSTVUYUSHCHEGO ALGORITMU~B, RAVNA
$$
(N+1)(\floor{\log_2  N}+2)-2^{\floor{\log_2 N}+1}.
\eqno(3)
$$
(sM.~(5.3.1-33).) iSPOLXZUYA~(3) I~(2), MOZHNO TOCHNO VYCHISLITX SREDNEE CHISLO 
SRAVNENIJ, ESLI PREDPOLOZHITX, CHTO VSE ARGUMENTY POISKA RAVNOVEROYATNY:
{\def\f#1,#2/#3.{#1{#2\over#3}}
\ctable{
\hfill$#$\bskip&&$#$\bskip\hfill\cr
   N=&1&  2     &  3     &  4     &  5     &  6     &  7     &  8     &  9      &  10     &  11     & 12       & 13       &  14      &  15     &  16\cr
 C_N=&1&\f1,1/2.&\f1,2/3.&  2     &\f2,1/5.&\f2,2/6.&\f2,3/7.&\f2,5/8.&\f2,7/9. &\f2,9/10.&  3      &\f3,1/12. &\f3,2/13. &\f3,3/14. &\f3,4/15.&\f3,6/16.\cr
C'_N=&1&\f1,2/3.&  2     &\f2,2/5.&\f2,4/6.&\f2,6/7.&  3     &\f3,2/9.&\f3,4/10.&\f3,6/11.&\f3,8/12.&\f3,10/13.&\f3,12/14.&\f3,14/15.&  4      &\f4,2/17.\cr
}
}
%%489
v OBSHCHEM SLUCHAE, ESLI $k=\floor{\log_2 N}$, IMEEM (SR.~S~(5.3.1-34))
$$
\matrix{
\hfill C_N &=k+1-(2^{k+1}-k-2)/N\hfill&=\log_2 N-1+\varepsilon+(k+2)/N;\hfill\cr
\hfill C'_N&=k+2-2^{k+1}/(N+1)  \hfill&=\log_2N+\varepsilon',\hfill\cr
}
\eqno(4)
$$
GDE $0\le\varepsilon$, $\varepsilon'<0.0861$.

iTAK, ALGORITM~B TREBUET MAKSIMUM $\floor{\log_2 N} +1$~SRAVNENIJ;
SREDNEE CHISLO SRAVNENIJ PRI UDACHNOM POISKE PRIBLIZHENNO RAVNO~$\log_2N-1$. 
nI ODIN METOD, OSNOVANNYJ NA SRAVNENII KLYUCHEJ, NE MOZHET DATX LUCHSHIH 
REZULXTATOV. sREDNEE VREMYA RABOTY PROGRAMMY v SOSTAVLYAET PRIMERNO
$$
\eqalign{
&(18\log_2N-15)u\rem{ DLYA UDACHNOGO POISKA;}\cr 
&(18\log_2N+13)u\rem{ DLYA NEUDACHNOGO POISKA}\cr
}
\eqno(5)
$$
(PREDPOLAGAETSYA, CHTO VSE ISHODY POISKA RAVNOVEROYATNY).

\section oDNA VAZHNAYA MODIFIKACIYA. sOBLAZNITELXNO VMESTO TREH UKAZATELEJ 
$l$, $i$, $u$ ISPOLXZOVATX LISHX DVA: TEKUSHCHEE POLOZHENIE~$i$ I VELICHINU EGO 
IZMENENIYA~$\delta$; POSLE KAZHDOGO SRAVNENIYA, NE DAVSHEGO RAVENSTVA, MY 
MOGLI BY USTANOVITX $i\asg i\pm\delta$ I~$\delta\asg\delta/2$ 
(PRIBLIZITELXNO). eTOT PUTX REALIZUEM, NO ON TREBUET OSOBOJ AKKURATNOSTI V 
DETALYAH, KAK V PRIVEDENNOM NIZHE ALGORITME;
BOLEE PROSTYE PODHODY OBRECHENY NA NEUDACHU!

\alg U.(oDNORODNYJ BINARNYJ POISK.) aLGORITM SLUZHIT DLYA OTYSKANIYA 
ARGUMENTA~$K$ V TABLICE ZAPISEJ $R_1$, $R_2$,~\dots, $R_N$, KLYUCHI KOTORYH 
RASPOLOZHENY V VOZRASTAYUSHCHEM PORYADKE: $K_1<K_2<\ldots<K_N$. pRI CHETNOM~$N$ 
INOGDA PROISHODIT OBRASHCHENIE K FIKTIVNOMU KLYUCHU~$K_0$, KOTORYJ NEOBHODIMO 
USTANOVITX RAVNYM~$-\infty$ (ILI LYUBOJ VELICHINE, MENXSHEJ~$K$. 
pREDPOLAGAETSYA, CHTO $N\ge1$.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg\ceil{N/2}$, $m\asg\floor{N/2}$.

\st[sRAVNENIE.] eSLI $K<K_i$, TO PEREJTI NA~\stp{3}; ESLI $K>K_i$, TO 
PEREJTI NA~\stp{4}; PRI $K=K_i$ ALGORITM OKANCHIVAETSYA UDACHNO.

\st[uMENXSHENIE $i$.] (mY OPREDELILI POLOZHENIE INTERVALA, GDE NUZHNO 
PRODOLZHATX POISK. oN SODERZHIT $m$ ILI $m-1$~ZAPISEJ; $i$ UKAZYVAET NA 
PERVYJ |LEMENT SPRAVA OT INTERVALA.) eSLI $m=0$, TO ALGORITM OKANCHIVAETSYA 
NEUDACHNO. v PROTIVNOM SLUCHAE USTANOVITX $i\asg i-\ceil{m/2}$; 
$m\asg\floor{m/2}$ I VERNUTXSYA NA~\stp{2}.

\st[uVELICHENIE $i$.] (sITUACIYA TA ZHE, CHTO I V SHAGE~\stp{3}, 
TOLXKO $i$~UKAZYVAET NA PERVYJ |LEMENT \emph{SLEVA} OT INTERVALA.) 
eSLI $m=0$, TO ALGORITM OKANCHIVAETSYA NEUDACHNO. v PROTIVNOM
SLUCHAE USTANOVITX $i\asg i+\ceil{m/2}$; $m\asg\floor{m/2}$ I VERNUTXSYA NA~\stp{2}.
\algend

nA RIS.~6 PREDSTAVLENO BINARNOE DEREVO, SOOTVETSTVUYUSHCHEE POISKU PRI $N=10$. 
pRI NEUDACHNOM POISKE KAK RAZ PERED OKONCHANIEM
%%490
RABOTY ALGORITMA MOZHET PROIZVODITXSYA LISHNEE SRAVNENIE; UZLY, 
OTVECHAYUSHCHIE |TIM SRAVNENIYAM, ZASHTRIHOVANY. dANNYJ PROCESS POISKA MOZHNO 
NAZVATX \emph{ODNORODNYM}, TAK KAK RAZNOSTX MEZHDU CHISLOM V UZLE 
UROVNYA~$\ell$ I CHISLOM V UZLE-PREDSHESTVENNIKE UROVNYA~$\ell-1$ ESTX 
POSTOYANNAYA VELICHINA~$\delta$ DLYA VSEH UZLOV UROVNYA~$\ell$.
oBOSNOVATX PRAVILXNOSTX ALGORITMA~U MOZHNO SLEDUYUSHCHIM OBRAZOM. pREDPOLOZHIM, 
CHTO POISK NUZHNO PROIZVESTI V INTERVALE
\picture{rIS. 6. bINARNOE DEREVO DLYA "ODNORODNOGO" BINARNOGO POISKA ($N=10$).}
DLINY~$n-1$; SRAVNENIE SO SREDNIM |LEMENTOM (ESLI $n$ CHETNO) ILI S ODNIM 
IZ DVUH SREDNIH (ESLI $n$ NECHETNO) VYDELYAET DVA INTERVALA 
DLINY~$\floor{n/2}-1$ I~$\ceil{n/2}-1$. pOSLE POVTORENIYA |TOJ PROCEDURY 
$k$~RAZ MY POLUCHIM $2^k$~INTERVALOV S MINIMALXNOJ DLINOJ~$\floor{n/2^k}-1$ 
I MAKSIMALXNOJ DLINOJ~$\ceil{n/2^k}-1$. sLEDOVATELXNO, NA KAZHDOM |TAPE 
DLINY DVUH INTERVALOV RAZLICHAYUTSYA SAMOE BOLXSHEE NA~1, CHTO DELAET VOZMOZHNYM 
VYBOR PODHODYASHCHEGO "SREDNEGO" |LEMENTA BEZ ZAPOMINANIYA POSLEDOVATELXNOSTI 
TOCHNYH ZNACHENIJ DLIN.

vAZHNOE PREIMUSHCHESTVO ALGORITMA~U SOSTOIT V TOM, CHTO NAM SOVSEM NE NUZHNO 
SOHRANYATX ZNACHENIE~$m$; NUZHNO LISHX SSYLATXSYA NA KOROTENXKUYU TABLICU 
ZNACHENIJ~$\delta$ DLYA KAZHDOGO UROVNYA. tAKIM OBRAZOM, ALGORITM SVODITSYA K 
SLEDUYUSHCHEJ PROCEDURE, ODINAKOVO HOROSHEJ I DLYA DVOICHNYH, I DLYA DESYATICHNYH evm.

\alg C.(oDNORODNYJ BINARNYJ POISK.) aLGORITM ANALOGICHEN ALGORITMU~U, NO 
VMESTO VYCHISLENIJ, OTNOSYASHCHIHSYA K~$m$, ISPOLXZUET VSPOMOGATELXNUYU TABLICU VELICHIN
$$
|DELTA|[j]=\floor{{N+2^{j-1}\over 2^j}}=\left({N\over 2^j}\right)
\hbox{ OKRUGLENNOE}; \qquad 1\le j \le \floor{\log_2 N}+2.
\eqno(6)
$$
\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg|DELTA| [1]$, $j\asg2$.
%%491
\st[sRAVNENIE:] eSLI $K<K_i$, TO PEREJTI NA \stp{3}; ESLI $K>K_i$, TO 
PEREJTI NA~\stp{4}. pRI $K=K_i$ ALGORITM OKANCHIVAETSYA UDACHNO.

\st[uMENXSHENIE $i$.] eSLI $|DELTA|[j]=0$, TO ALGORITM OKANCHIVAETSYA 
NEUDACHNO. v PROTIVNOM SLUCHAE USTANOVITX $i\asg i-|DELTA|[j]$,  $j\asg j+1$ 
I VERNUTXSYA NA~\stp{2}.

\st[uVELICHENIE~$i$.] eSLI $|DELTA|[j]=0$, ALGORITM OKANCHIVAETSYA NEUDACHNO. 
v PROTIVNOM SLUCHAE USTANOVITX $i\asg i+|DELTA|[j]$, $j\asg j+1$ I 
VERNUTXSYA NA~\stp{2}. 
\algend

v UPR.~8 BUDET POKAZANO, CHTO ALGORITM SSYLAETSYA NA VSPOMOGATELXNYJ 
KLYUCH~$K_0=-\infty$ LISHX PRI CHETNYH~$N$.

\prog C.(oDNORODNYJ BINARNYJ POISK.) eTA PROGRAMMA NA BAZE ALGORITMA~C 
PRODELYVAET TU ZHE RABOTU, CHTO I PROGRAMMA~B. iSPOLXZUYUTSYA $|rA|\equiv K$, 
$|rI1|\equiv i$, $|rI2|\equiv j$, 
$|rI3|\equiv |DELTA| [j]$.
\code
START  & ENT1 & N+1/2  & 1     & C1. nACHALXNAYA USTANOVKA.
       & ENT2 & 2      & 1     & $j\asg 2$.
       & LDA  & k      & 1     &
       & JMP  & 2F     & 1     &
3H     & JE   & SUCCESS& C1    & pEREHOD, ESLI $K=K_i$.
       & J3Z  & FAILURE& C1-S  & pEREHOD, ESLI $|DELTA|[j]=0$.
       & DEC1 & 0,3    & C1-S-A& C3.  uMENXSHENIE~$i$.
5H     & INC2 & 1      & C-1   & $j\asg j+1$.
2H     & LD3  & DELTA,2& C     & C2. sRAVNENIE.
       & smra & KEY.1  & C     &
       & JLE  & 3B     & C     & pEREHOD, ESLI $K\le K_i$.
       & INC1 & 0,3    & C2    & C4. uVELICHENIE $i$.
       & J3NZ & 5B     & C2    & pEREHOD, ESLI $|DELTA|[j]\ne0$.
FAILURE& EQU  & *      & 1-S   & vYHOD, ESLI NET V TABLICE.
\endcode
\progend

pRI UDACHNOM POISKE |TOT ALGORITM SOOTVETSTVUET BINARNOMU DEREVU S TOJ ZHE 
DLINOJ VNUTRENNEGO PUTI, CHTO I ALGORITM~v, PO|TOMU SREDNEE CHISLO 
SRAVNENIJ~$C_N$ DAETSYA FORMULOJ~(4). pRI NEUDACHNOM POISKE ALGORITM~C 
VSEGDA SOVERSHAET ROVNO $\floor{\log_2N}+1$~SRAVNENIJ. pOLNOE VREMYA RABOTY 
PROGRAMMY~C NE VPOLNE SIMMETRICHNO PO OTNOSHENIYU K LEVYM I PRAVYM VETVYAM, 
TAK KAK $C1$ IMEET VES, BOLXSHIJ CHEM $C2$, NO V UPR.~9 BUDET POKAZANO, 
CHTO SLUCHAJ $K>K_i$ VSTRECHAETSYA PRIMERNO TAK ZHE CHASTO, KAK I~$K<K_i$;
SLEDOVATELXNO, PROGRAMMA~C TREBUET PRIBLIZITELXNO
$$
\matrix{
(8.5\log_2N-6)u \hfill& \hbox{NA UDACHNYJ POISK};\cr
(8.5\floor{\log_2N}+12)u &\hbox{NA NEUDACHNYJ POISK.}\cr
}
\eqno(7)
$$
%%492
eTO BOLEE CHEM V DVA RAZA BYSTREE PROGRAMMY~B, PRICHEM NE ISPOLXZUYUTSYA 
SPECIALXNYE SVOJSTVA DVOICHNYH evm, V TO VREMYA KAK V FORMULE~(5) 
PREDPOLAGAETSYA, CHTO \MIX{} IMEET KOMANDU "DVOICHNYJ SDVIG VPRAVO".

dRUGAYA MODIFIKACIYA BINARNOGO POISKA, PREDLOZHENNAYA V 1971~G. l.~e.~shEROM, 
NA NEKOTORYH evm DOPUSKAET ESHCHE BOLEE BYSTRUYU REALIZACIYU, TAK KAK ONA 
ODNORODNA POSLE PERVOGO
\picture{rIS. 7. bINARNOE DEREVO DLYA POCHTA ODNORODNOGO POISKA shERA ($N=10$).}
SHAGA I NE TREBUET VSPOMOGATELXNOJ TABLICY. sNACHALA MY SRAVNIVAEM $K$ 
I~$K_i$, GDE $i=2^k$, $k=\floor{\log_2 N}$. eSLI $K<K_i$, MY ISPOLXZUEM 
ODNORODNYJ POISK S POSLEDOVATELXNOSTXYU $\delta=2^{k-1}$, $2^{k-2}$,~\dots, 
$1$, $0$. s DRUGOJ STORONY, PRI $K>K_i$ I~$N>2^k$ USTANAVLIVAEM 
$i=i'=N+1-2^\ell$, GDE $\ell=\floor{\log_2(N-2^k)}+1$, I, DELAYA VID, CHTO 
PERVYM SRAVNENIEM BYLO $K>K_{i'}$, ISPOLXZUEM ODNORODNYJ POISK S 
$\delta=2^{\ell-1}$, $2^{\ell-2}$,~\dots, $1$, $0$.

rISUNOK~7 ILLYUSTRIRUET METOD shERA PRI $N=10$. v METODE shERA NIKOGDA NE 
TREBUETSYA BOLEE $\floor{\log_2 N}+1$~SRAVNENIJ; SLEDOVATELXNO, ON DAET 
ODNO IZ LUCHSHIH SREDNIH CHISEL SRAVNENIYA, NESMOTRYA NA TO CHTO INOGDA PROHODIT 
CHEREZ NESKOLXKO POSLEDOVATELXNYH IZBYTOCHNYH SHAGOV (SR. S UPR.~12).

eSHCHE ODNA MODIFIKACIYA BINARNOGO POISKA, ULUCHSHAYUSHCHAYA VSE RASSMOTRENNYE METODY 
PRI OCHENX BOLXSHIH $N$, OBSUZHDAETSYA V UPR.~23. v UPR.~24 IZLOZHEN ESHCHE BOLEE 
BYSTRYJ METOD!

\section fIBONACHCHIEV POISK. pRI RASSMOTRENII MNOGOFAZNOGO 
SLIYANIYA (P.~5.4.2) MY VIDELI, CHTO CHISLA fIBONACHCHI MOGUT IGRATX ROLX,
 ANALOGICHNUYU STEPENYAM~$2$. pOHOZHEE YAVLENIE IMEET MESTO I V SLUCHAE POISKA,
 KOGDA S POMOSHCHXYU CHISEL fIBONACHCHI SOZDAYUTSYA METODY, SPOSOBNYE SOPERNICHATX S 
BINARNYM POISKOM. pREDLAGAEMYJ METOD DLYA NEKOTORYH evm PREDPOCHTITELXNEE 
BINARNOGO, TAK KAK ON VKLYUCHAET LISHX SLOZHENIE I VYCHITANIE; NET 
NEOBHODIMOSTI V DELENII NA~$2$. sLEDUET OTLICHATX PROCEDURU, KOTORUYU MY SOBI-
%%493
RAEMSYA OBSUZHDATX, OT IZVESTNOJ CHISLENNOJ PROCEDURY "FIBONACHCHIEVA POISKA",
 KOTORAYA ISPOLXZUETSYA DLYA NAHOZHDENIYA MAKSIMUMA ODNOVERSHINNOJ FUNKCII 
[SR.~S~Fibonacci Quarterly, 4 (1966), 265--269]; SHOZHESTX NAZVANIJ VEDET K 
NEKOTOROJ PUTANICE.

nA PERVYJ VZGLYAD FIBONACHCHIEV POISK KAZHETSYA VESXMA TAINSTVENNYM; ESLI 
PROSTO VZYATX PROGRAMMU I POPYTATXSYA OB�YASNITX EE RABOTU, TO SOZDASTSYA 
VPECHATLENIE, CHTO ONA RABOTAET S POMOSHCHXYU MAGII. nO TUMAN TAINSTVENNOSTI 
RASSEETSYA, KAK TOLXKO MY POSTROIM
\picture{rIS. 8.   dEREVO fIBONACHCHI PORYADKA 6.}
SOOTVETSTVUYUSHCHEE DEREVO POISKA. pO|TOMU IZUCHENIE RASSMATRIVAEMOGO METODA 
NACHNEM S RASSKAZA O "FIBONACHCHIEVYH DEREVXYAH".

nA RIS.~8 IZOBRAZHENO DEREVO fIBONACHCHI PORYADKA~$6$. zAMETXTE, CHTO ONO 
NESKOLXKO BOLXSHE NAPOMINAET REALXNYJ KUST, CHEM RASSMATRIVAVSHIESYA RANEE 
DEREVXYA, VOZMOZHNO, POTOMU, CHTO MNOGIE PRIRODNYE PROCESSY UDOVLETVORYAYUT 
ZAKONU fIBONACHCHI. vOOBSHCHE FIBONACHCHIEVO DEREVO PORYADKA~$k$ IMEET 
$F_{k+1}-1$~VNUTRENNIH (KRUGLYH) UZLOV I~$F_{k+1}$~VNESHNIH (KVADRATNYH) 
UZLOV; ONO STROITSYA SLEDUYUSHCHIM OBRAZOM:

{\medskip\narrower
\item{eSLI}~$k=0$ ILI~$k=1$, DEREVO SVODITSYA PROSTO K~\leaf{0}.

\item{eSLI}~$k\ge2$, KORNEM YAVLYAETSYA~\node{F_k}; LEVOE PODDEREVO ESTX 
DEREVO fIBONACHCHI PORYADKA~$k-1$; PRAVOE PODDEREVO ESTX DEREVO fIBONACHCHI 
PORYADKA~$k-2$ S CHISLAMI V UZLAH, UVELICHENNYMI NA~$F_k$.

\medskip}

\noindent zAMETIM, CHTO, ZA ISKLYUCHENIEM VNESHNIH UZLOV, CHISLA, 
SOOTVETSTVUYUSHCHIE PREEMNIKAM KAZHDOGO VNUTRENNEGO UZLA, OTLICHAYUTSYA OT CHISLA 
V |TOM UZLE NA ODNU I TU ZHE VELICHINU, A IMENNO NA CHISLO fIBONACHCHI. tAK, 
$5=8-F_4$, $11=8+F_4$ (RIS.~8). eSLI RAZNOSTX BYLA RAVNA~$F_j$, TO NA 
SLEDUYUSHCHEM UROVNE SOOTVETSTVUYUSHCHAYA
%%494
RAZNOSTX SOSTAVIT DLYA LEVOJ VETVI $F_{j-1}$, A DLYA PRAVOJ~$F_{j-2}$. tAK,
 NAPRIMER, $3=5-F_3$, a~$10=11-F_2$.

eTI NABLYUDENIYA V SOVOKUPNOSTI S PODHODYASHCHIM MEHANIZMOM RASPOZNAVANIYA 
VNESHNIH UZLOV DAYUT

\alg F.(fIBONACHCHIEV POISK.) aLGORITM PREDNAZNACHAETSYA DLYA POISKA 
ARGUMENTA~$K$ V TABLICE ZAPISEJ $R_1$, $R_2$,~\dots, $R_N$, RASPOLOZHENNYH 
V PORYADKE VOZRASTANIYA KLYUCHEJ $K_1<K_2<\ldots<K_N$.

dLYA UDOBSTVA OPISANIYA PREDPOLAGAETSYA, CHTO $N+1$ ESTX 
CHISLO fIBONACHCHI~$F_{k+1}$. pODHODYASHCHEJ NACHALXNOJ USTANOVKOJ DANNYJ METOD 
MOZHNO SDELATX PRIGODNYM DLYA LYUBOGO~$N$ (SM.~UPR.~14).

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $i\asg F_k$, $p\asg F_{k-1}$, 
$q\asg F_{k-2}$. (v |TOM ALGORITME $p$ I~$q$ OBOZNACHAYUT POSLEDOVATELXNYE 
CHISLA fIBONACHCHI.)

\st[sRAVNENIE.] eSLI $K<K_i$, TO PEREJTI NA~\stp{3}; ESLI $K>K_i$, TO 
PEREJTI NA~\stp{4}; ESLI $K=K_i$, ALGORITM ZAKANCHIVAETSYA UDACHNO.

\st[uMENXSHENIE~$i$.] eSLI~$q=0$, ALGORITM ZAKANCHIVAETSYA NEUDACHNO. 
eSLI~$q\ne 0$, TO USTANOVITX $i\asg i-q$, ZAMENITX $(p, q)$ NA~$(q, p-q)$ 
I VERNUTXSYA NA~\stp{2}.

\st[uVELICHENIE~$i$.] eSLI~$p=1$,  ALGORITM ZAKANCHIVAETSYA NEUDACHNO. 
eSLI~$p\ne1$, USTANOVITX $i\asg i+q$, $p\asg p-q$, $q\asg q-p$ I VERNUTXSYA NA~\stp{2}.
\algend

v PRIVODIMOJ NIZHE REALIZACII ALGORITMA~F DLYA MASHINY \MIX\ SKOROSTX 
UVELICHIVAETSYA ZA SCHET DUBLIROVANIYA VNUTRENNEGO CIKLA, V ODNOM IZ 
|KZEMPLYAROV KOTOROGO $p$~HRANITSYA V~|rI2|, A~$q$---V~|rI3|, V DRUGOM ZHE 
REGISTRY MENYAYUTSYA ROLYAMI; |TO UPROSHCHAET SHAG~F3. nA SAMOM DELE PROGRAMMA 
HRANIT V REGISTRAH $p-1$ I~$q-1$, CHTO UPROSHCHAET PROVERKU "$p=1$?" V SHAGE~F4.

\prog F.(fIBONACHCHIEV POISK.) zNACHENIYA REGISTROV: $|rA|\equiv K$,
 $|rI1|\equiv i$, $(|rI2|, |rI3|)\equiv p-l$, $(|rI3|, |rI2|)\equiv q-l$.
\code
START & LDA & K          & 1   & F1. nACHALXNAYA USTANOVKA.
      & ENT1& $F_k$      & 1   & $i\asg F_k$.
      & ENT2& $F_{k-1}-1$& 1   & $p\asg F_{k-1}$.
      & ENT3& $F_{k-2}-1$& 1   & $q\asg F_{k-2}$.
      & JMP & F2A        & 1   &   nA F2.
\twocols
F4A & INC1 &1,3    & F4B &INC1 &1,2    & C2-S-A & F4. uVELICHENIE $i$. $i\asg i+q$.
    & DEC2 &1,3    &     &DEC3 &1,2    & G2-S-A & $p\asg p-q$.
    & DEC3 &1,2    &     &DEC2 &1,3    & G2-S-A & $q\asg q-p$.
F2A & CMPA &KEY, 1 & F2v &CMPA &KEY,1  & G      & F2. sRAVNENIE.
    & JL   &F3A    &     &JL   &F3B    & G      & nA Fz, ESLI $K<K_i$.
    & JE   &SUCCESS&     &JE   &SUCCESS& G2     & vYHOD,  ESLI $K=K_i$.
%%495
    & J2NZ &F4A    &     &J3NZ &F4B    & C2-S   & nA F4, ESLI $p\ne1$.
    & JMP  &FAILURE&     &JMP  &FAILURE& A      & vYHOD,  ESLI NET V TABLICE.
F3A & DEC1 &1,3    & F3B &DEC1 &1,2    & C1     & F3. uMENXSHENIE~$i$. $i\asg i-q$.
    & DEC2 &1,3    &     &DEC3 &1,2    & C1     & $p\asg p-q$.
    & J3NN &F2B    &     &J2NN &F2A    & C1     & sMENA REGISTROV, ESLI~$q>0$.
    & JMP  &FAILURE&     &JMP  &FAILURE& 1-S-A  & vYHOD,  ESLI NET V TABLICE.
\endtwocols
\endcode
\progend

v UPR.~18 ANALIZIRUETSYA VREMYA RABOTY |TOJ PROGRAMMY. rISUNOK~8 POKAZYVAET, 
A ANALIZ DOKAZYVAET, CHTO VLEVO MY IDEM NESKOLXKO CHASHCHE, CHEM VPRAVO. chEREZ 
$C$, $C1$ I~$C2-S$ OBOZNACHIM CHISLO VYPOLNENIJ SHAGOV F2, F3 I~F4 
SOOTVETSTVENNO. iMEEM
$$
\eqalign{
 C&=(\ave \phi k/sqrt{5}+O(1), \max k-1), \cr
C1&=(\ave k/\sqrt{5}+O(1), \max k-1),\cr
C2-S&=(\ave \phi^{-1} k/\sqrt{5}+O(1), \max \floor{k/2}).\cr
}
\eqno(8)
$$
zNACHIT, LEVAYA VETVX VYBIRAETSYA PRIMERNO V $\phi=1.618$~RAZA CHASHCHE PRAVOJ 
(|TO MOZHNO BYLO PREDVIDETX, TAK KAK KAZHDAYA PROBA DELIT RASSMATRIVAEMYJ 
INTERVAL NA DVE CHASTI, PRICHEM LEVAYA CHASTX PRIMERNO V $\phi$~RAZ DLINNEE 
PRAVOJ). sREDNEE VREMYA RABOTY PROGRAMMY F SOSTAVLYAET PRIMERNO
$$
\eqalign{
(6\phi k/\sqrt{5}-(2+22\phi)/5)u &\approx (6.252\log_2 N-4.6)u 
\rem {DLYA UDACHNOGO POISKA;}\cr
(6\phi k/\sqrt{5}+(58/(27\phi))/5)u&\approx (6.252\log_2 N+5.8)u
\rem{DLYA NEUDACHNOGO POISKA.}\cr
}
\eqno(9)
$$
eTO NESKOLXKO LUCHSHE, CHEM~(7), HOTYA V NAIHUDSHEM SLUCHAE PROGRAMMA~F 
RABOTAET PRIMERNO $(8.6\log_2 N)u$, T.E. CHUTX-CHUTX MEDLENNEE PROGRAMMY~s.

\section iNTERPOLYACIONNYJ POISK. zABUDEM NA MINUTU O 
VYCHISLITELXNYH MASHINAH I PROANALIZIRUEM, KAK PROIZVODIT POISK 
CHELOVEK. iNOGDA POVSEDNEVNAYA ZHIZNX PODSKAZYVAET PUTX K SOZDANIYU HOROSHIH 
ALGORITMOV.

pREDSTAVXTE, CHTO VY ISHCHETE SLOVO V SLOVARE. mALOVEROYATNO, CHTO VY SNACHALA 
ZAGLYANETE V SEREDINU SLOVARYA, ZATEM OTSTUPITE OT NACHALA NA~$1/4$ ILI~$3/4$ 
I~T.~D., KAK V BINARNOM POISKE, I UZH SOVSEM NEVEROYATNO, CHTO VY 
VOSPOLXZUETESX FIBONACHCHIEVYM POISKOM!

eSLI NUZHNOE SLOVO NACHINAETSYA S BUKVY~A, VY, PO-VIDIMOMU, NACHNETE POISK 
GDE-TO V NACHALE SLOVARYA. vO MNOGIH SLOVARYAH
%%496
IMEYUTSYA "POBUKVENNYE VYSECHKI" DLYA BOLXSHOGO PALXCA, KOTORYE POKAZYVAYUT 
STRANICU, GDE NACHINAYUTSYA SLOVA NA DANNUYU BUKVU. tAKUYU PALXCEVUYU TEHNIKU 
LEGKO PRISPOSOBITX K evm, CHTO USKORIT POISK; SOOTVETSTVUYUSHCHIE ALGORITMY 
ISSLEDUYUTSYA V \S~6.3.

kOGDA NAJDENA OTPRAVNAYA TOCHKA DLYA POISKA, VASHI DALXNEJSHIE DEJSTVIYA MALO 
POHOZHI NA RASSMOTRENNYE METODY. eSLI VY ZAMETITE, CHTO NUZHNOE SLOVO DOLZHNO 
NAHODITXSYA GORAZDO DALXSHE OTKRYTOJ STRANICY, VY PROPUSTITE PORYADOCHNOE IH 
KOLICHESTVO, PREZHDE CHEM SDELATX SLEDUYUSHCHUYU POPYTKU. eTO V KORNE OTLICHAETSYA 
OT PREDYDUSHCHIH ALGORITMOV, KOTORYE NE DELAYUT RAZLICHIYA MEZHDU "MNOGO 
BOLXSHE" I "CHUTX BOLXSHE".

mY PRIHODIM K TAKOMU ALGORITMU, NAZYVAEMOMU "INTERPOLYACIONNYM POISKOM": 
ESLI IZVESTNO, CHTO $K$ LEZHIT MEZHDU~$K_l$ I~$K_u$, TO SLEDUYUSHCHUYU PROBU 
DELAEM PRIMERNO NA RASSTOYANII $(u-l)(K-K_l)/(K_u-K_l)$ OT~$l$, PREDPOLAGAYA,
CHTO KLYUCHI YAVLYAYUTSYA CHISLAMI, VOZRASTAYUSHCHIMI PRIBLIZITELXNO KAK ARIFMETICHESKAYA 
PROGRESSIYA.

 iNTERPOLYACIONNYJ POISK ASIMPTOTICHESKI PREDPOCHTITELXNEE BINARNOGO; PO 
SUSHCHESTVU, ODIN SHAG BINARNOGO POISKA UMENXSHAET
KOLICHESTVO "PODOZREVAEMYH" ZAPISEJ S~$n$ DO~${1\over2}n$, A ODIN SHAG
INTERPOLYACIONNOGO (ESLI KLYUCHI V TABLICE RASPREDELENY SLUCHAJNYM 
OBRAZOM)---S~$n$ DO~$\sqrt{n}$. mOZHNO POKAZATX, CHTO INTERPOLYACIONNYJ POISK 
TREBUET V SREDNEM OKOLO $\log_2 \log_2 N$~SHAGOV (UPR.~22).

k SOZHALENIYU, |KSPERIMENTY NA evm POKAZALI, CHTO INTERPOLYACIONNYJ POISK 
UMENXSHAET CHISLO SRAVNENIJ NE NASTOLXKO, CHTOBY KOMPENSIROVATX VOZNIKAYUSHCHIJ 
DOPOLNITELXNYJ RASHOD VREMENI, KOGDA TABLICA, V KOTOROJ PROIZVODITSYA POISK,
 HRANITSYA VO VNUTRENNEJ ("BYSTROJ") PAMYATI. rAZNOSTX MEZHDU $\log_2 
\log_2 N$ I~$\log_2 N$ STANOVITSYA SUSHCHESTVENNOJ LISHX DLYA VESXMA BOLXSHIH~$N$,
 A TIPICHNYE FAJLY NEDOSTATOCHNO SLUCHAJNY. iNTERPOLYACIYA USPESHNA DO 
NEKOTOROJ STEPENI LISHX V PRIMENENII K POISKU NA \emph{VNESHNIH} 
ZAPOMINAYUSHCHIH USTROJSTVAH. (zAMETIM, CHTO RUCHNOJ PROSMOTR SLOVARYA ESTX, V 
SUSHCHNOSTI, NE VNUTRENNIJ, A VNESHNIJ POISK; |TO YAVLYAETSYA TEMOJ POSLEDUYUSHCHIH 
RASSMOTRENIJ.)

\section iSTORIYA I BIBLIOGRAFIYA. pERVYM IZVESTNYM PRIMEROM DLINNOGO 
PERECHNYA |LEMENTOV, UPORYADOCHENNYH DLYA OBLEGCHENIYA POISKA, YAVLYAETSYA 
ZNAMENITAYA VAVILONSKAYA TABLICA OBRATNYH VELICHIN Inakibit-Anu, DATIRUEMAYA 
PRIMERNO 200~G. DO~N.|. eTA GLINYANAYA PLASTINKA, OCHEVIDNO, OTKRYVALA SERIYU 
IZ TREH TABLICHEK, SODERZHASHCHIH BOLEE 500 MNOGOZNACHNYH SHESTIDESYATERICHNYH 
CHISEL I OBRATNYH IM VELICHIN, OTSORTIROVANNYH V 
LEKSIKOGRAFICHESKOM PORYADKE. nAPRIMER, VSTRECHAETSYA TAKAYA POSLEDOVATELXNOSTX:
%%497
\ctable{
\bskip$#$\bskip&&\bskip$#$\bskip\cr
01&13&09&34&29&08&08&53&20&\qquad&49&12&27\cr
01&13&14&31&52&30&  &  &  &      &49&09&07&12\cr
01&13&43&40&48&  &  &  &  &      &48&49&41&15\cr
01&13&48&40&30&  &  &  &  &      & 48&46&22&59&25&25&55&33&20\cr
01&14&04&26&40&  &  &  &  &      &48&36\cr
}
sORTIROVKA 500 PODOBNYH CHISEL SREDSTVAMI TEH VREMEN KAZHETSYA FENOMENALXNOJ. 
[sM. TAKZHE D.~e.~Knuth, {\sl CACM\/}, {\bf 15} (1972), 671--677, GDE 
SODERZHITSYA MNOGO DOPOLNITELXNYH SVEDENIJ.]

dOVOLXNO ESTESTVENNO RASPOLAGATX PO PORYADKU CHISLA, NO OTNOSHENIE PORYADKA 
MEZHDU BUKVAMI ILI SLOVAMI NE PREDSTAVLYAETSYA SAMO SOBOJ OCHEVIDNYM. oDNAKO 
POSLEDOVATELXNOSTI DLYA SRAVNIVANIYA BUKV PRISUTSTVOVALI UZHE V NAIBOLEE 
DREVNIH ALFAVITAH. nAPRIMER, MNOGIE BIBLEJSKIE PSALMY SODERZHAT STIHI, 
SLEDUYUSHCHIE DRUG ZA DRUGOM V STROGO ALFAVITNOM PORYADKE: PERVYJ 
STIH NACHINAETSYA S~ALEFA, VTOROJ S~BETA I~T.~D.; |TO OBLEGCHALO 
ZAPOMINANIE. iNOGDA STANDARTNAYA POSLEDOVATELXNOSTX BUKV ISPOLXZOVALASX 
SEMITAMI I GREKAMI DLYA OBOZNACHENIYA CHISEL; NAPRIMER, $\alpha$, $\beta$, 
$\gamma$ OBOZNACHALI 1, 2, 3 SOOTVETSTVENNO.

oDNAKO ISPOLXZOVANIE ALFAVITNOGO PORYADKA DLYA SLOV CELIKOM BYLO, VEROYATNO, 
GORAZDO BOLEE POZDNIM IZOBRETENIEM; VESHCHI, OCHEVIDNYE SEJCHAS DAZHE DLYA 
REBENKA, KOGDA-TO TREBOVALOSX OB�YASNYATX VZROSLYM! nEKOTORYE DOKUMENTY, 
DATIRUEMYE PRIMERNO 300~G. DO~N.|., NAJDENNYE NA OSTROVAH eGEJSKOGO MORYA,
 SODERZHAT SPISKI CHLENOV NESKOLXKIH RELIGIOZNYH OBSHCHIN; ONI UPORYADOCHENY, NO 
TOLXKO PO PERVOJ BUKVE, T.~E. PREDSTAVLYAYUT SOBOJ REZULXTAT LISHX PERVOGO 
PROHODA SLEVA NAPRAVO PORAZRYADNOJ SORTIROVKI. gRECHESKIE PAPIRUSY 
134--135~G. N.~|. SODERZHAT FRAGMENTY SCHETOV, V KOTORYH FAMILII 
NALOGOPLATELXSHCHIKOV UPORYADOCHENY PO PERVYM DVUM BUKVAM. aPOLLONIJ sOFIST%
\note{1}{oDIN IZ GRAMMATIKOV DREVNOSTI, RODOM IZ aLEKSANDRII.---{\sl pRIM. PEREV.\/}}
ISPOLXZOVAL ALFAVITNOE UPORYADOCHENIE PO PERVYM DVUM, A CHASTO I PO 
POSLEDUYUSHCHIM BUKVAM V SVOEM "sLOVARE GOMEROVSKIH SLOV" (I~VEK N.~|.). 
iZVESTNO NESKOLXKO PRIMEROV BOLEE SOVERSHENNOGO ALFAVITNOGO UPORYADOCHENIYA, 
SKAZHEM VYDAYUSHCHIESYA "kOMMENTARII K gIPPOKRATU" gALENA%
\note{2}{rIMSKIJ VRACH I ESTESTVOISPYTATELX, KLASSIK ANTICHNOJ 
MEDICINY.---{\sl pRIM. PEREV.\/}}
 (OKOLO 200~G.), NO |TO BYLO OCHENX REDKIM YAVLENIEM. tAK, V HRONIKE sV.~iSIDORA%
\note{3}{iSIDOR sEVILXSKIJ---ISPANSKIJ EPISKOP, VYDAYUSHCHIJSYA UCHENYJ I 
PISATELX.---{\sl pRIM. PEREV.\/}}
 "Etymologiarum" (OKOLO 630~G., KNIGA~X) SLOVA UPORYADOCHENY LISHX PO 
PERVOJ BUKVE, A V NAIBOLEE RANNEM IZ IZVESTNYH DVUYAZYCHNYH SLOVAREJ "Corpus 
Glossary" (OKOLO 725~G.) --- TOLXKO PO DVUM PERVYM. dVE POSLEDNIE RABOTY 
BYLI, VEROYATNO, KRUPNEJSHIMI NECHISLOVYMI FAJLAMI DANNYH, SKOMPILIROVANNYMI 
V SREDNIE VEKA.

%% 498

tOLXKO V KNIGE dZHOVANNI gENU|ZSKOGO "Catholicon" (1286~G.) MY NAHODIM 
PODROBNOE OPISANIE PRAVILXNOGO ALFAVITNOGO PORYADKA. v PREDISLOVII dZHOVANNI 
OB�YASNYAET, CHTO
\ctable{
\hfill\it # \bskip & PREDSHESTVUET \it #\hfill\cr
amo & bibo \cr
abeo & adeo \cr
amatus & amor \cr
imprudens & impudens\cr
iusticia & iustus\cr
polisintheton & polissenus \cr
}
(T.~E. PRIVODIT PRIMERY SITUACIJ, KOGDA PORYADOK OPREDELYAETSYA
PO $1$, $2$,~\dots, $6\hbox{-J}$~BUKVAM) "I DALEE ANALOGICHNO". oN ZAMECHAET,
 .CHTO OTKRYTIE |TOGO PRAVILA POTREBOVALO ZNACHITELXNYH.USILIJ.
"ya PROSHU vAS, UVAZHAEMYJ CHITATELX, NE PREZIRATX |TU MOYU BOLXSHUYU RABOTU I 
|TOT PORYADOK KAK NECHTO NICHEGO NE STOYASHCHEE".
rAZVITIE ALFAVITNOGO PORYADKA DO MOMENTA IZOBRETENIYA KNIGOPECHATANIYA 
PODROBNO IZUCHIL l.~u.~dEJLI ({\sl Collection Latomus,\/}
{\bf 90} (1967), 100~pp.). oN OBNARUZHIL NESKOLXKO INTERESNYH
STARINNYH RUKOPISEJ, KOTORYE, NESOMNENNO, ISPOLXZOVALISX
KAK CHERNOVIKI PRI SORTIROVKE SLOV PO PERVOJ BUKVE (SM. STR.~87--90 EGO 
MONOGRAFII).

pERVYJ SLOVARX ANGLIJSKOGO YAZYKA rOBERTA kODRI "Table
Alphabeticall" (London, 1604) SODERZHIT SLEDUYUSHCHIE INSTRUKCII:

{\narrower

eSLI SLOVO, KOTOROE TEBE NUZHNO NAJTI, NACHINAETSYA S~(a), SMOTRI V NACHALO 
|TOJ KNIGI, A ESLI S~(v)---TO V KONEC. oPYATX ESLI SLOVO NACHINAETSYA S~(ca), 
SMOTRI V NACHALO BUKVY~(c), A ESLI S~(cu) TO V KONEC. i TAK DO KONCA SLOVA.

}
\noindent iNTERESNO ZAMETITX, CHTO kODRI VO VREMYA PODGOTOVKI SLOVARYA,
 VEROYATNO, SAM UCHILSYA RASSTAVLYATX SLOVA V ALFAVITNOM PORYADKE;
NA NESKOLXKIH PERVYH STRANICAH VSTRECHAETSYA MNOGO NEPRAVILXNO STOYASHCHIH SLOV, 
ZATO DALXSHE CHISLO OSHIBOK SUSHCHESTVENNO UMENXSHAETSYA.

bINARNYJ POISK VPERVYE UPOMYANUT dZHONOM mOCHLI V DISKUSSII, KOTORAYA BYLA, 
POZHALUJ, PERVYM OPUBLIKOVANNYM OBSUZHDENIEM METODOV NECHISLENNOGO 
PROGRAMMIROVANIYA [SM. Theory and techniques for the design of electronic 
digital computers, ed. by G.~W.~Patterson, 3 (1946); 22.8--22.9]. v 
TECHENIE 50-H~GODOV METOD STANOVITSYA "HOROSHO IZVESTNYM", NO, KAZHETSYA, NIKTO 
NE RAZRABATYVAL DETALI ALGORITMA DLYA~$N\ne 2^n-1$. [sM. A.~D.~Booth, {\sl 
Nature,\/} {\bf 176} (1955), 565;  A.~I.~Dumey, {\sl Computers and 
Automation, \/} {\bf 5} (December, 1956), 7, GDE BINARNYJ POISK IMEET 
NAZVANIE "dVADCATX VOPROSOV"; D.~D.~McCracken, Digital Computer 
Programming (Wiley, 1957), 201--203; M.~Halpern, {\sl CACM\/} {\bf 1, 
2} (February, 1958), 1--3.]

%%499

pO-VIDIMOMU, ALGORITM BINARNOGO POISKA, PRIGODNYJ DLYA VSEH~$N$, VPERVYE 
OPUBLIKOVAN bOTTENBRUKOM [{\sl JACM,\/} {\bf 9} (1962), 214]. oN 
PREDSTAVIL INTERESNUYU MODIFIKACIYU ALGORITMA~B, KOGDA PROVERKI NA RAVENSTVO 
OTODVIGAYUTSYA V KONEC ALGORITMA. iSPOLXZUYA V SHAGE~B2 $i\asg\ceil{(l+u)/2}$ 
VMESTO~$\floor{(l+u)/2}$, ON USTANAVLIVAET $l\asg i$ PRI~$K\ge K_i$; TOGDA 
$u-l$ UMENXSHAETSYA POSLE KAZHDOGO SHAGA. v KONCE, KOGDA $l=u$, IMEEM $K_l\le 
K<K_{l+1}$, I MOZHNO PROVERITX, BYL LI POISK UDACHNYM, PROIZVEDYA ESHCHE 
ODNO SRAVNENIE. (oN PREDPOLAGAL, CHTO PERVONACHALXNO~$K\ge K_1$.) eTA IDEYA 
POZVOLYAET NESKOLXKO USKORITX VNUTRENNIJ CIKL NA MNOGIH zvm; TO ZHE VERNO I 
DLYA VSEH OBSUZHDAVSHIHSYA V DANNOM PUNKTE ALGORITMOV, ODNAKO TAKOE IZMENENIE 
OPRAVDANO LISHX DLYA BOLXSHIH~$N$ (SM. UPR.~23).

k.~e.~aJVERSON [A Programming Language (Wiley, 1962), 141] PRIVEL 
PROCEDURU ALGORITMA~B, NO BEZ RASSMOTRENIYA VOZMOZHNOSTI NEUDACHNOGO POISKA.
 d.~kNUT ({\sl CACM,\/} {\bf 6} (1963), 556--558) PREDSTAVIL ALGORITM~B 
KAK PRIMER ISPOLXZOVANIYA AVTOMATICHESKOJ SISTEMY POSTROENIYA BLOK-SHEM. 
oDNORODNYJ BINARNYJ POISK (ALGORITM~C) PREDLOZHIL AVTORU V~1971~G. 
a.~k.~chANDRA (sTANDFORDSKIJ UNIVERSITET).

fIBONACHCHIEV POISK IZOBRETEN d.~fERGYUSONOM [{\sl CACM,\/} {\bf 3} (1960), 
648], NO EGO BLOK-SHEMA I ANALIZ BYLI NEKORREKTNY. dEREVO fIBONACHCHI (BEZ 
METOK) POYAVILOSX GORAZDO RANXSHE KAK KURXEZ V PERVOM IZDANII POPULYARNOJ 
KNIGI gUGO shTEJNGAUZA "mATEMATICHESKIJ KALEJDOSKOP" (m., gOSTEHIZDAT, 1949) 
NA STR.~34;
ONO BYLO NARISOVANO KORNEM VNIZ I VYGLYADELO, KAK OBYCHNOE DEREVO; PRAVYE 
VETVI BYLI SDELANY V DVA RAZA DLINNEE LEVYH, TAK CHTO VSE LISTXYA OKAZALISX 
NA ODNOM UROVNE.

iNTERPOLYACIONNYJ POISK PREDLOZHEN u.~u.~pETERSONOM 
[{\sl IBM J.~Res.~\& Devel.,\/} {\bf 1} (1957), 131--132]. oN DAL 
TEORETICHESKUYU OCENKU SREDNEGO 
CHISLA SRAVNENIJ DLYA SLUCHAYA, KOGDA KLYUCHI SLUCHAJNO VYBIRAYUTSYA IZ RAVNOMERNO 
RASPREDELENNOJ POSLEDOVATELXNOSTI, ODNAKO |TI OCENKI RASHODYATSYA S 
|KSPERIMENTALXNYMI DANNYMI.

\excercises
\rex[21] dOKAZHITE, CHTO ESLI~$u<l$ V SHAGE~B2 BINARNOGO POISKA, TO 
$u=l-1$ I~$K_u<K<K_l$. (bUDEM SCHITATX, CHTO $K_0=-\infty$ 
I~$K_{N+1}=\infty$, HOTYA ALGORITM NE ISPOLXZUET |TI DOBAVOCHNYE KLYUCHI, T.~E.
 ONI NE DOLZHNY PRISUTSTVOVATX V TABLICE.)

\rex[22] bUDET LI ALGORITM~B RABOTATX PRAVILXNO, ESLI (a)~ZAMENITX V 
SHAGE~B5 "$l\asg i+1$" NA~"$l\asg i$"? (b) zAMENITX V SHAGE~B4 "$u\asg i-1$" 
NA "$u\asg i$"? (c) vNESTI OBA IZMENENIYA?

%% 500
\ex[15] kAKOJ METOD POISKA SOOTVETSTVUET DEREVU
\picture{rIS. STR. 500}
kAKOVO SREDNEE CHISLO SRAVNENIJ PRI UDACHNOM POISKE? PRI NEUDACHNOM?

\ex[20] eSLI POISK, PROIZVODIMYJ PROGRAMMOJ~S IZ \S~6.1 
(POSLEDOVATELXNYJ POISK), TREBUET 638~EDINIC VREMENI, TO SKOLXKO BUDET 
RABOTATX PROGRAMMA~B (BINARNYJ POISK)?

\ex[m24] pRI KAKIH $N$ PROGRAMMA~B V SREDNEM \emph{MEDLENNEE} 
POSLEDOVATELXNOGO POISKA (PROGRAMMA $6.1Q'$), ESLI PREDPOLAGAETSYA, CHTO 
POISK UDACHEN?

\ex[28] (k.~e.~aJVERSON) v SILU UPR.~5 LUCHSHE VSEGO BYLO BY IMETX 
NEKIJ "GIBRIDNYJ" METOD, PEREHODYASHCHIJ OT BINARNOGO POISKA K 
POSLEDOVATELXNOMU, KOGDA DLINA OSTAYUSHCHEGOSYA INTERVALA MENXSHE NEKOTOROJ 
RAZUMNO VYBRANNOJ VELICHINY. nAPISHITE |FFEKTIVNUYU PROGRAMMU DLYA \MIX{} I 
OPREDELITE NAILUCHSHIJ MOMENT SMENY METODOV POISKA.

\rex[M22] bUDET LI ALGORITM~U RABOTATX PRAVILXNO, ESLI MY IZMENIM SHAG~U1 
TAK, CHTO (a) KAK $i$, TAK I~$m$ USTANAVLIVAYUTSYA RAVNYMI $\floor{N/2}$; (b) 
KAK $i$, TAK I~$m$ USTANAVLIVAYUTSYA RAVNYMI~$\ceil{N/2}$? [\emph{uKAZANIE:} 
PREDPOLOZHIM, CHTO PERVYJ SHAG VYGLYADEL BY TAK: "uSTANOVITX $i\asg 0$, $m\asg 
N$ (ILI~$N+1$), PEREJTI NA~U4".]

\ex[m20] (a)~chEMU RAVNA SUMMA~$\sum_{0\le j\le \floor{\log_2N}+2} 
|DELTA|[j]$ PRIRASHCHENIJ V ALGORITME~C? (b)~kAKOVY MINIMALXNOE I 
MAKSIMALXNOE ZNACHENIYA~$i$, KOTORYE MOGUT POYAVITXSYA V SHAGE~C2?

\ex[m26] pROVEDITE CHASTOTNYJ ANALIZ DLYA PROGRAMMY~C I NAJDITE 
TOCHNUYU ZAVISIMOSTX SREDNIH ZNACHENIJ $C1$, $C2$ I~$A$ OT~$N$ I~$S$.

\ex[20] sUSHCHESTVUYUT LI $N>1$, PRI KOTORYH ALGORITMY~v I~s 
ABSOLYUTNO |KVIVALENTNY V TOM SMYSLE, CHTO ONI SOVERSHAYUT ODINAKOVYE, 
POSLEDOVATELXNOSTI SRAVNENIJ PRI VSEH ARGUMENTAH POISKA?

\ex[21] oB�YASNITE, KAK NAPISATX \MIX-PROGRAMMU DLYA ALGORITMA~C, SODERZHASHCHUYU 
PRIMERNO $7\log_2 N$~KOMAND, VREMYA RABOTY KOTOROJ SOSTAVIT 
PRIBLIZITELXNO $4.5\log_2 N$~EDINIC?

\ex[20] nARISUJTE DEREVO BINARNOGO POISKA, SOOTVETSTVUYUSHCHEE METODU shERA PRI~$N=12$.

\ex[m24] zATABULIRUJTE SREDNIE CHISLA SRAVNENIJ V METODE shERA DLYA $1\le 
N<16$, RASSMATRIVAYA KAK UDACHNYE, TAK I NEUDACHNYE POISKI.

\ex[21] oB�YASNITE, KAK PRISPOSOBITX ALGORITM~F DLYA RABOTY S LYUBYM~$N\ge 1$.

\ex[21] nA RIS.~9 IZOBRAZHENA DIAGRAMMA RAZMNOZHENIYA KROLIKOV V ISHODNOJ 
ZADACHE fIBONACHCHI (SR.~S~P.~1.2.8). sUSHCHESTVUET LI PROSTAYA SVYAZX MEZHDU |TOJ 
DIAGRAMMOJ I FIBONACHCHIEVYM DEREVOM RESHENIJ?

\ex[m19] pRI KAKIH ZNACHENIYAH~$k$ FIBONACHCHIEVO DEREVO PORYADKA~$k$ 
OPREDELYAET OPTIMALXNUYU PROCEDURU POISKA, T.~E. TAKUYU, PRI KOTOROJ 
SREDNEE CHISLO SRAVNENIJ MINIMALXNO?

\ex[m21] iZ UPR.~1.2.8-34 (ILI UPR.~5.4.2-10) MY ZNAEM, CHTO LYUBOE 
NATURALXNOE CHISLO~$n$ EDINSTVENNYM OBRAZOM PREDSTAVLYAETSYA V VIDE SUMMU 
CHISEL fIBONACHCHI: $n=F_{a_1}+F_{a_2}+\cdots+F_{a_r}$, GDE $r\ge 1$, $a_j\ge 
a_{j+1}+2$  PRI~$1\le j<r$ I~$a_r\ge2$. dOKAZHITE, CHTO V FIBONACHCHIEVOM 
DEREVE PORYADKA~$k$ PUTX OT KORNYA DO UZLA~\node{$n$} IMEET DLINU~$k+1-r-a_r$.

%% 501

\picture{rIS. 9. pARY KROLIKOV, RAZMNOZHAYUSHCHIESYA PO PRAVILU fIBONACHCHI.}

\ex[m30] pROVEDITE CHASTOTNYJ ANALIZ DLYA PROGRAMMY~F I NAJDITE TOCHNYE 
FORMULY DLYA SREDNIH ZNACHENIJ $C1$, $C2$ I~$A$ KAK FUNKCIJ OT~$k$, $F_k$,
 $F_{k+1}$ I~$S$.

\ex[m42] pROVEDITE DETALXNYJ ANALIZ SREDNEGO VREMENI RABOTY ALGORITMA, 
PREDLOZHENNOGO V UPR.~14.

\ex[m22] chISLO SRAVNENIJ, TREBUYUSHCHIHSYA PRI BINARNOM POISKE, PRIBLIZHENNO 
RAVNO~$\log_2N$, PRI FIBONACHCHIEVOM---$(\phi/\sqrt{5})\log_\phi N$. cELX 
|TOGO UPRAZHNENIYA---POKAZATX, CHTO |TI FORMULY YAVLYAYUTSYA CHASTNYMI SLUCHAYAMI 
BOLEE OBSHCHEGO REZULXTATA.

pUSTX $p$ I~$q$---POLOZHITELXNYE CHISLA I~$p+q=1$. rASSMOTRIM ALGORITM POISKA 
PO TABLICE IZ $N$~ZAPISEJ S VOZRASTAYUSHCHIMI KLYUCHAMI, KOTORYJ, NACHINAYA SO 
SRAVNENIYA ARGUMENTA S $(pN)\hbox{-M}$~KLYUCHOM, POVTORYAET |TU PROCEDURU 
DLYA MENXSHIH BLOKOV. (dLYA BINARNOGO POISKA $p=q=1/2$; DLYA 
FIBONACHCHIEVA $p=1/\phi$, $q=1/\phi^2$.)

oBOZNACHIM SREDNEE CHISLO SRAVNENIJ, TREBUEMYH DLYA POISKA V 
TABLICE RAZMERA~$N$, CHEREZ $C(N)$; ONO PRIBLIZHENNO UDOVLETVORYAET SOOTNOSHENIYAM
$$
C(1)=0, \quad C(N)=1+pC(pN)+qC(qN) \rem{ DLYA $N>1$.}
$$
eTO PROISHODIT POTOMU, CHTO POSLE PERVOGO SRAVNENIYA POISK PRIMERNO S 
VEROYATNOSTXYU~$p$ SVODITSYA K POISKU SREDI $pN$~|LEMENTOV I S 
VEROYATNOSTXYU $q$---K POISKU SREDI $qN$~|LEMENTOV. pRI BOLXSHIH~$N$ MOZHNO 
PRENEBRECHX |FFEKTOM NIZSHEGO PORYADKA, SVYAZANNYM S TEM, CHTO CHISLA~$pN$ 
I~$qN$ NE CELYE.
\medskip
\item{a)} pOKAZHITE, CHTO $C(N)=\log_b N$ TOCHNO UDOVLETVORYAET UKAZANNYM 
SOOTNOSHENIYAM PRI NEKOTOROM~$b$. dLYA BINARNOGO I FIBONACHCHIEVA POISKOV 
VELICHINA~$b$ POLUCHAETSYA IZ VYVEDENNYH RANEE FORMUL.

\item{b)} nEKTO RASSUZHDAL TAK: "s VEROYATNOSTXYU~$p$ DLINA RASSMATRIVAEMOGO  
INTERVALA DELITSYA NA~$1/p$, S VEROYATNOSTXYU~$q$---NA~$1/q$. 
sLEDOVATELXNO INTERVAL DELITSYA V SREDNEM NA~$p(1/p)+q (1/q)=2$, TAK CHTO 
ALGORITM V TOCHNOSTI TAK ZHE HOROSH, KAK I BINARNYJ POISK, NEZAVISIMO OT~$p$ 
I~$q$". eSTX LI OSHIBKA V |TIH RASSUZHDENIYAH?
\medskip

\ex[20] nARISUJTE BINARNOE DEREVO, SOOTVETSTVUYUSHCHEE INTERPOLYACIONNOMU 
POISKU PRI~$N=10$.

\ex[m43] (e.~k.~yaO I~f.~f.~yaO.) pOKAZHITE,, CHTO DOLZHNYM OBRAZOM OFORMLENNYJ 
INTERPOLYACIONNYJ POISK V SREDNEM TREBUET (ASIMPTOTICHESKI) $\log_2\log_2 
N$~SRAVNENIJ, ESLI $N$~OTSORTIROVANNYH KLYUCHEJ IMEYUT 
NEZAVISIMYE RAVNOMERNYE RASPREDELENIYA. bOLEE TOGO, VSE ALGORITMY POISKA PO TAKIM
TABLICAM DOLZHNY SOVERSHATX V SREDNEM $\log_2 \log_2  N$~SRAVNENIJ (OCENKA ASIMPTOTICHESKAYA).

\rex[25] aLGORITM BINARNOGO POISKA g.~bOTTENBRUKA, UPOMYANUTYJ V 
KONCE PUNKTA, "OTKLADYVAET" PROVERKI NA RAVENSTVO DO SAMOGO KONCA POISKA. (vO
%%502
VREMYA RABOTY ALGORITMA MY ZNAEM, CHTO $K_l\le K<K_{u+1}$, PROVERKA NA 
RAVENSTVO PROVODITSYA LISHX PRI~$l=u$.) tAKOJ TRYUK SDELAL BY PROGRAMMU~B 
CHUTX BYSTREE PRI BOLXSHIH~$N$, TAK KAK MY IZBAVILISX BY OT KOMANDY "|JF|," 
VO VNUTRENNEM CIKLE. (oDNAKO |TA IDEYA PRAKTICHESKI NEREALXNA, TAK KAK 
$\log_2  N$ OBYCHNO MAL;
LISHX PRI~$N>2^{36}$ KOMPENSIRUETSYA NEOBHODIMOSTX DOPOLNITELXNOJ ITERACII!)

pOKAZHITE, CHTO \emph{LYUBOJ} ALGORITM POISKA, SOOTVETSTVUYUSHCHIJ BINARNOMU 
DEREVU I RAZVETVLYAYUSHCHIJSYA PO TREM NAPRAVLENIYAM ($<$, $=$, ILI~$>$), MOZHNO 
PEREDELATX V ALGORITM, RAZVETVLYAYUSHCHIJSYA VO VNUTRENNIH UZLAH LISHX PO DVUM 
NAPRAVLENIYAM ($<$ ILI~$\ge$). v CHASTNOSTI, MODIFICIRUJTE TAKIM SPOSOBOM ALGORITM~C. 

\rex[23] pOLNOE BINARNOE DEREVO YAVLYAETSYA UDOBNYM SPOSOBOM PREDSTAVLENIYA 
V POSLEDOVATELXNYH YACHEJKAH DEREVA S MINIMALXNOJ DLINOJ PUTI. (sR. S 
P.~2.3.4.5.) pRIDUMAJTE |FFEKTIVNYJ METOD POISKA, OSNOVANNYJ NA 
TAKOM PREDSTAVLENII. [\emph{uKAZANIE:} MOZHNO LI V BINARNOM POISKE 
ISPOLXZOVATX UMNOZHENIE NA~$2$ VMESTO DELENIYA NA~$2$?]

\rex[m25] pREDPOLOZHIM, CHTO U BINARNOGO DEREVA IMEETSYA $a_k$~VNUTRENNIH I 
$b_k$~VNESHNIH UZLOV NA UROVNE~$k$, $k=0$, $1$,~\dots. (kORENX NAHODITSYA NA 
NULEVOM UROVNE.) tAK, DLYA RIS.~8 IMEEM $(a_0, a_1,~\ldots, a_6)=(1, 2, 4, 4,
 1, 0)$ I $(b_0, b_1,~\ldots, b_6)=(0, 0, 0, 4, 7, 2)$. (a)~pOKAZHITE, CHTO 
SUSHCHESTVUET PROSTOE ALGEBRAICHESKOE SOOTNOSHENIE, SVYAZYVAYUSHCHEE PROIZVODYASHCHIE 
FUNKCII $A(z)=\sum_{k}a_kz^k$ I~$B(z)=\sum_k b_kz^k$. (b)~rASPREDELENIE 
VEROYATNOSTEJ PRI UDACHNOM POISKE PO BINARNOMU DEREVU IMEET PROIZVODYASHCHUYU 
FUNKCIYU $g(z)=zA(z)/N$, A PRI NEUDACHNOM POISKE PROIZVODYASHCHAYA FUNKCIYA ESTX 
$h(z)=B(z)/(N+1)$. (v OBOZNACHENIYAH P.~6.2.1 $C_N=\mean(g)$, 
$C'_N=\mean(h)$, A SOOTNOSHENIE~(2) SVYAZYVAET |TI VELICHINY.) nAJDITE 
ZAVISIMOSTX MEZHDU $\var(g)$ I~$\var(h)$.

\ex[22] pOKAZHITE, CHTO DEREVO fIBONACHCHI SVYAZANO S SORTIROVKOJ MNOGOFAZNYM 
SLIYANIEM NA TREH LENTAH.

\ex[M30] (X.~s.~sTOUN I dZH.~lINI.) rASSMOTRIM PROCESS POISKA, OSNOVANNYJ 
TOLXKO NA SRAVNENIYAH KLYUCHEJ I ISPOLXZUYUSHCHIJ ODNOVREMENNO $k$~PROCESSOROV. 
pRI KAZHDOM SHAGE POISKA OPREDELYAYUTSYA $k$~INDEKSOV $i_1$, $i_2$,~\dots, 
$i_k$  I MY SOVERSHAEM $k$~ODNOVREMENNYH SRAVNENIJ: ESLI~$K=K_j$ DLYA 
NEKOTOROGO~$j$, POISK KONCHAETSYA UDACHNO, V PROTIVNOM SLUCHAE PEREHODIM K 
SLEDUYUSHCHEMU SHAGU POISKA, OSNOVYVAYASX NA $2^k$~VOZMOZHNYH ISHODAH~$K<K_{i_j}$ 
ILI~$K>K_{i_j}$, $1\le j\le k$.

pOKAZHITE, CHTO TAKOJ PROCESS PRI~$N\to\infty$ DOLZHEN SOVERSHATX V SREDNEM 
PO KRAJNEJ MERE $\log_{k+1}N$~SHAGOV. (pREDPOLAGAETSYA, CHTO VSE KLYUCHI V 
TABLICE, TAKZHE KAK I ARGUMENT POISKA, RAVNOVEROYATNY.) (zNACHIT, PO 
SRAVNENIYU S ODNOPROCESSORNYM BINARNYM POISKOM MY VYIGRYVAEM V SKOROSTI 
NE V $k$~RAZ, KAK MOZHNO BYLO BY OZHIDATX, A LISHX V $\log_2(k+1)$~RAZ. v 
|TOM SMYSLE VYGODNEE KAZHDYJ PROCESSOR ISPOLXZOVATX DLYA OTDELXNOGO POISKA, 
A NE OB�EDINYATX IH.)

\subsubchap{pOISK PO BINARNOMU DEREVU} %% 6.2.2

v PREDYDUSHCHEM PUNKTE MY VIDELI, CHTO ISPOLXZOVANIE NEYAVNOJ  STRUKTURY 
BINARNOGO DEREVA OBLEGCHAET PONIMANIE BINARNOGO I FIBONACHCHIEVA POISKOV. 
rASSMOTRENIE SOOTVETSTVUYUSHCHIH DEREVXEV POZVOLILO ZAKLYUCHITX, CHTO PRI 
DANNOM~$N$ SREDI VSEH METODOV POISKA PUTEM SRAVNENIYA KLYUCHEJ BINARNYJ POISK 
SOVERSHAET MINIMALXNOE CHISLO SRAVNENIJ. nO METODY PREDYDUSHCHEGO 
PUNKTA PREDNAZNACHENY GLAVNYM OBRAZOM DLYA TABLIC FIKSIROVANNOGO RAZMERA, 
TAK KAK POSLEDOVATELXNOE RASPOLOZHENIE ZAPISEJ DELAET VSTAVKI I UDALENIYA 
DOVOLXNO TRUDOEMKIMI. eSLI TABLICA
%%503
DINAMICHESKI IZMENYAETSYA, TO |KONOMIYA OT ISPOLXZOVANIYA BINARNOGO POISKA NE 
POKROET ZATRAT NA PODDERZHANIE UPORYADOCHENNOGO RASPOLOZHENIYA KLYUCHEJ.

\emph{yaVNOE} ISPOLXZOVANIE STRUKTURY BINARNOGO DEREVA POZVOLYAET BYSTRO 
VSTAVLYATX I UDALYATX ZAPISI I PROIZVODITX |FFEKTIVNYJ POISK PO TABLICE. v 
REZULXTATE MY POLUCHAEM METOD, POLEZNYJ KAK DLYA POISKA, TAK I DLYA 
SORTIROVKI. tAKAYA GIBKOSTX DOSTIGAETSYA
\picture{rIS. 10.  bINARNOE DEREVO POISKA.}
PUTEM DOBAVLENIYA V KAZHDUYU ZAPISX DVUH POLEJ DLYA HRANENIYA SSYLOK.

mETODY POISKA PO RASTUSHCHIM TABLICAM, CHASTO NAZYVAYUT \emph{ALGORITMAMI 
TABLIC SIMVOLOV}, TAK KAK ASSEMBLERY, KOMPILYATORY I DRUGIE SISTEMNYE 
PROGRAMMY OBYCHNO ISPOLXZUYUT IH DLYA HRANENIYA OPREDELYAEMYH POLXZOVATELEM 
SIMVOLOV. nAPRIMER, KLYUCHOM ZAPISI V KOMPILYATORE MOZHET SLUZHITX 
SIMVOLICHESKIJ IDENTIFIKATOR, OBOZNACHAYUSHCHIJ PEREMENNUYU V NEKOTOROJ PROGRAMME 
NA fORTRANE ILI aLGOLE, A OSTALXNYE POLYA ZAPISI MOGUT SODERZHATX 
INFORMACIYU O TIPE PEREMENNOJ I EE RASPOLOZHENII V PAMYATI. iLI ZHE KLYUCHOM 
MOZHET BYTX SIMVOL PROGRAMMY DLYA \MIX, A OSTAVSHAYASYA CHASTX ZAPISI MOZHET 
SODERZHATX |KVIVALENT |TOGO SIMVOLA. pROGRAMMY POISKA S VSTAVKOJ PO DEREVU, 
KOTORYE BUDUT OPISANY V |TOM PUNKTE, OTLICHNO PODHODYAT DLYA ISPOLXZOVANIYA V 
KACHESTVE ALGORITMOV TABLIC SIMVOLOV, OSOBENNO ESLI ZHELATELXNO 
RASPECHATYVATX SIMVOLY V ALFAVITNOM PORYADKE. dRUGIE ALGORITMY, 
TABLIC SIMVOLOV OPISANY V \S~6.3 I~6.4.

%%504

nA RIS.~10 IZOBRAZHENO BINARNOE DEREVO POISKA, SODERZHASHCHEE NAZVANIYA 
ODINNADCATI ZNAKOV ZODIAKA%
\note{1}{zNAKI ZODIAKA, UPORYADOCHENNYE PO MESYACAM: kOZEROG, vODOLEJ, rYBY,
 oVEN, tELEC, bLIZNECY, rAK, lEV, dEVA, vESY, sKORPION, sTRELEC,---{\sl pRIM. PEREV.\/}}.
 eSLI TEPERX, OTPRAVLYAYASX OT KORNYA DEREVA, MY BUDEM ISKATX DVENADCATOE 
NAZVANIE, |SAGITTARIUS|, TO UVIDIM, CHTO ONO BOLXSHE, CHEM |CAPRICORN|, 
PO|TOMU NUZHNO IDTI VPRAVO; ONO BOLXSHE, CHEM |PISCES|,---SNOVA IDEM VPRAVO; 
ONO MENXSHE, CHEM |TAURUS|,---IDEM VLEVO; ONO MENXSHE, CHEM |SCORPIO|,--- I MY 
POPADAEM VO VNESHNIJ UZEL~\leaf{8}. pOISK BYL NEUDACHNYM; TEPERX PO 
OKONCHANII POISKA MY MOZHEM \emph{VSTAVITX} |SAGITTARIUS|, "PODVYAZYVAYA" EGO 
K DEREVU VMESTO VNESHNEGO UZLA~\leaf{8}. tAKIM OBRAZOM, TABLICA MOZHET RASTI 
BEZ PEREMESHCHENIYA SUSHCHESTVUYUSHCHIH ZAPISEJ. rISUNOK~10 POLUCHEN POSLEDOVATELXNOJ 
VSTAVKOJ, NACHINAYA S PUSTOGO DEREVA, KLYUCHEJ |CAPRICORN|, |AQUARIUS|, 
|PISCES|, |ARIES|, |TAURUS|, |GEMINI|, |CANCER|, |LEO|, |VIRGO|, |LIBRA|,
 |SCORPIO| V UKAZANNOM PORYADKE.

nA RIS.~10 VSE KLYUCHI LEVOGO PODDEREVA KORNYA PREDSHESTVUYUT PO ALFAVITU 
SLOVU |CAPRICORN|, A V PRAVOM PODDEREVE STOYAT POSLE NEGO. aNALOGICHNOE 
UTVERZHDENIE SPRAVEDLIVO DLYA LEVOGO I PRAVOGO PODDEREVXEV LYUBOGO UZLA. 
oTSYUDA SLEDUET, CHTO PRI OBHODE DEREVA V \emph{SIMMETRICHNOM PORYADKE} KLYUCHI 
RASPOLAGAYUTSYA STROGO V ALFAVITNOM PORYADKE:
$$
\displaylines{
|AQUARIUS|, |ARIES|, |CANCER|, |CAPRICORN|, |GEMINI|, \cr
|LEO|, \ldots, |VIRGO|,\cr
}
$$
TAK KAK SIMMETRICHNYJ PORYADOK OSNOVAN NA PROHOZHDENII SNACHALA LEVOGO 
PODDEREVA KAZHDOGO UZLA, ZATEM SAMOGO UZLA, A ZATEM EGO PRAVOGO PODDEREVA 
(SR. S P.~2.3.1).

nIZHE DAETSYA PODROBNOE OPISANIE PROCESSA POISKA S VSTAVKOJ.

\alg t.(pOISK S VSTAVKOJ PO DEREVU.) dANA TABLICA ZAPISEJ, OBRAZUYUSHCHIH 
BINARNOE DEREVO. pROIZVODITSYA POISK ZADANNOGO ARGUMENTA~$K$. eSLI EGO 
NET V TABLICE, TO V PODHODYASHCHEM MESTE V DEREVO VSTAVLYAETSYA NOVYJ UZEL, 
SODERZHASHCHIJ~$K$.

pREDPOLAGAETSYA, CHTO UZLY DEREVA SODERZHAT PO KRAJNEJ MERE SLEDUYUSHCHIE POLYA:
$$
\eqalign{
|KEY|(|P|)&=\hbox{KLYUCH, HRANYASHCHIJSYA V UZLE $|NODE|(|P|)$};\cr
|LLINK|(|P|)&=\hbox{UKAZATELX NA LEVOE PODDEREVO UZLA~$|NODE|(|P|)$};\cr
|RLINK|(|P|)&=\hbox{UKAZATELX NA PRAVOE PODDEREVO UZLA~$|NODE|(|P|)$}.\cr
}
$$
pUSTYE PODDEREVXYA (VNESHNIE UZLY NA RIS.~10) PREDSTAVLYAYUTSYA PUSTYMI 
UKAZATELYAMI~$\NULL$. pEREMENNAYA~|ROOT| UKAZYVAET NA KORENX DEREVA. dLYA 
UDOBSTVA PREDPOLAGAETSYA, CHTO DEREVO NE PUSTO
%%505
($|ROOT|\ne\NULL$), TAK KAK PRI~$|ROOT|=\NULL$ OPERACII STANOVYATSYA 
TRIVIALXNYMI.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|P|\asg |ROOT|$. (uKAZATELX~|P| BUDET 
PRODVIGATXSYA VNIZ PO DEREVU.)

\st[sRAVNENIE.] eSLI~$K<|KEY|(|P|)$, TO PEREJTI NA~\stp{3}; 
ESLI $K>|KEY|(|P|)$, TO PEREJTI NA~\stp{4}; ESLI $K=|KEY|(|P|)$, 
POISK ZAVERSHEN UDACHNO.

\st[shAG VLEVO.] eSLI~$|LLINK|(|P|)\ne\NULL$, USTANOVITX 
$|P|\asg|LLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}. v PROTIVNOM SLUCHAE PEREJTI NA~\stp{5}.

\st[shAG VPRAVO.] eSLI~$|RLINK|(|P|)\ne\NULL$, USTANOVITX 
$|P|\asg|RLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}.

\st[vSTAVKA V DEREVO.] (pOISK NEUDACHEN; TEPERX MY POMESTIM $K$ V DEREVO.) 
vYPOLNITX $|Q|\Asg|AVAIL|$; |Q| TEPERX UKAZYVAET NA NOVYJ UZEL. uSTANOVITX 
$|KEY|(|Q|)\asg K$, $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$. (nA SAMOM 
DELE NUZHNO PROIZVESTI NACHALXNUYU USTANOVKU I DRUGIH POLEJ NOVOGO UZLA.) 
eSLI $K$ BYLO MENXSHE $|KEY|(|P|)$, USTANOVITX $|LLINK|(|P|)\asg|Q|$; V 
PROTIVNOM  SLUCHAE USTANOVITX $|RLINK|(|P|)\asg|Q|$. (v |TOT MOMENT MY 
MOGLI BY PRISVOITX $|P|\asg|Q|$ I UDACHNO ZAVERSHITX RABOTU ALGORITMA.)
\algend

aLGORITM SAM PODSKAZYVAET REALIZACIYU NA YAZYKE~\MIXAL. pREDPOLOZHIM, 
NAPRIMER, CHTO UZLY DEREVA IMEYUT SLEDUYUSHCHUYU STRUKTURU:
\picture{rIS. STR. 505}
vOZMOZHNO, DALEE RASPOLOZHENY DOPOLNITELXNYE SLOVA |INFO|. kAK I V GL.~2, 
|AVAIL| ESTX SPISOK SVOBODNOJ PAMYATI. iTAK, POLUCHAETSYA SLEDUYUSHCHAYA PROGRAMMA 
DLYA \MIX.

\prog t.(pOISK S VSTAVKOJ PO DEREVU.) $|rA|\equiv K$, $|rI1|\equiv|P|$,
 $|rI2|\equiv Q$.
\code
LLINK & EQU  &2:3
RLINK & EQU  &4:5
START & LDA  &k           & 1    & t1. nACHALXNAYA USTANOVKA.
      & LD1  &ROOT        & 1    & $|P|\asg|ROOT|$.
      & JMP  &2F          & 1
4H    & LD2  &0,1(RLINK)  & C2   & T4. shAG VPRAVO. $|Q|\asg|RLlNK|(|P|)$.
      & J2Z  &5F          & C2   & nA T5, ESLI $|Q|=\NULL$.
1H    & ENT1 &0,2         & C-l  & $|P|\asg|Q|$.
2H    & CMPA &1,1         & C    & T2. sRAVNENIE.
      & JG   & 4v         & C    & nA T4, ESLI $K>|KEY|(|P|)$.
      & JE   &SUCCESS     & C1   & vYHOD, ESLI $K=|KEY|(|P|)$.
      & LD2  &0,1 (LLINK) & C1-S & Tz. shAG VLEVO. $|Q|\asg|LLINK|(|P|)$.
%%506
     & J2NZ & 1B         & C1-S  & nA T2, ESLI $|Q|\ne\NULL$.
5n   & LD2  & AVAIL      & 1-S   & T5 vSTAVKI V DEREVO.
     & J2Z  & OVERFLOW   & 1-S
     & LDX  & 0,2(RLINK) & 1-S
     & STX  & AVAIL      & 1-S   & $|Q|\Asg|AVAIL|$.
     & STA  & 1,2        & 1-S   & $|KEY|(|Q|)\asg|K|$.
     & STZ  & 0,2        & 1-S   & $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$.
     & JL   & 1F         & 1-S   & $K$ BYL MENXSHE $|KEY|(|P|)$?
     & ST2  & 0,1(RLINK) & A     & $|RLINK|(|P|)\asg|Q|$.
     & JMP  & *+2        & A
1H   & ST2  & 0,1(LLINK) & 1-S-A & $|LLINK|(|P|)\asg|Q|$.
DONE & EQU  & *          & 1-S   & vYHOD POSLE VSTAVKI. 
\endcode
\progend
pERVYE 13~STROK PROGRAMMY OSUSHCHESTVLYAYUT POISK, POSLEDNIE 11~STROK---VSTAVKU. 
vREMYA RABOTY POISKOVOJ FAZY RAVNO $(7C+C1-3S+4)u$, GDE
$$
\eqalign{
C &=\hbox{CHISLO PROIZVEDENNYH SRAVNENIJ};\cr
Cl& =\hbox{CHISLO SLUCHAEV, KOGDA $K\le|KEY|(|P|)$};\cr
S& =\hbox{ 1 PRI UDACHNOM POISKE I 0 V PROTIVNOM SLUCHAE}.\cr
}
$$
v SREDNEM IMEEM $C1={1\over2}(C+S)$; DEJSTVITELXNO, $C1+C2=C$ 
I $C1-S\approx C2$. pO|TOMU VREMYA POISKA PRIMERNO RAVNO $(7.5C-2.5S+4)u$.
\picture{rIS 11. pOISK S VSTAVKOJ PO DEREVU.}
pROGRAMMY BINARNOGO POISKA, ISPOLXZUYUSHCHIE NEYAVNYE DEREVXYA, RABOTAYUT DOLXSHE! 
(sR. S PROGRAMMOJ~6.2.1s.) pRODUBLIROVAV KOMANDY, KAK. I V 
PROGRAMME~6.2.1F, MOZHNO IZBAVITXSYA OT STROKI~08 V PROGRAMME~t, UMENXSHIV 
TEM SAMYM VREMYA POISKA DO~$(6.5C-2.5S+5)u$. eSLI POISK NEUDACHEN, 
FAZA VSTAVKI ZAJMET ESHCHE VREMYA $14u$ ILI~$15u$.

aLGORITM~t LEGKO PRISPOSOBITX K RABOTE S KLYUCHAMI I ZAPISYAMI 
\emph{PEREMENNOJ DLINY}. nAPRIMER, ESLI MY RASPREDELYAEM
%%507
IMEYUSHCHEESYA V NALICHII PROSTRANSTVO POSLEDOVATELXNO, SPOSOBOM "POSLEDNIM 
VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA" (LIFO), TO LEGKO SMOZHEM SOZDAVATX UZLY 
RAZLICHNOGO RAZMERA; PERVOE SLOVO DEREVA~(1) MOZHET UKAZYVATX DLINU. tAKOE 
|FFEKTIVNOE ISPOLXZOVANIE PAMYATI DELAET ALGORITMY TABLIC SIMVOLOV, 
OSNOVANNYE NA DREVOVIDNOJ STRUKTURE, OSOBENNO PRIVLEKATELXNYMI DLYA 
RAZRABOTCHIKOV KOMPILYATOROV, ASSEMBLEROV I ZAGRUZCHIKOV.

\qsection a KAK NASCHET NAIHUDSHEGO SLUCHAYA? mNOGIE PROGRAMMISTY SNACHALA 
SKEPTICHESKI VOSPRINIMAYUT ALGORITM~T. eSLI BY KLYUCHI RIS.~10 POSTUPALI V 
ALFAVITNOM PORYADKE |AQUARIUS|,~\dots, |VIRGO|, a NE V KALENDARNOM 
|CAPRICORN|,~\dots, |SCORPIO|, TO ALGORITM VYSTROIL BY VYROZHDENNOE DEREVO, 
KOTOROE, V SUSHCHNOSTI, OPREDELYAET \emph{POSLEDOVATELXNYJ} POISK. (vSE POLYA 
|LLINK| RAVNYALISX BY ~$\NULL$.) aNALOGICHNO, ESLI KLYUCHI POSTUPAYUT V 
NEOBYCHNOM PORYADKE:
$$
\displaylines{
|AQUARIUS|, |VIRGO|, |ARIES|, |TAURUS|, |CANCER|, |SCORPIO|,\cr
|CAPRICORN|, |PISCES|, |GEMINI|, |LIBRA|, |LEO|,\cr
}
$$
MY POLUCHIM ZIGZAGOOBRAZNOE DEREVO, CHTO NICHUTX NE LUCHSHE. (pOSTROJTE |TO DEREVO!)

s DRUGOJ STORONY, DLYA UDACHNOGO POISKA PO DEREVU RIS.~10
TREBUETSYA V SREDNEM VSEGO LISHX $3{2\over11}$~SRAVNENIJ, CHTO NEMNOGIM
BOLXSHE OPTIMALXNOGO SREDNEGO CHISLA SRAVNENIJ~3, KOTOROE DOSTIGAETSYA PRI 
POISKE PO NAILUCHSHEMU IZ VOZMOZHNYH BINARNYH DEREVXEV.

dLYA DOSTATOCHNO HOROSHO SBALANSIROVANNOGO DEREVA VREMYA POISKA PRIMERNO, 
PROPORCIONALXNO~$\log_2N$, A DLYA VYROZHDENNOGO DEREVA---$N$. v UPR.~2.3.4.5-5 
DOKAZYVAETSYA, CHTO, ESLI SCHITATX VSE BINARNYE DEREVXYA IZ $N$~UZLOV 
RAVNOVEROYATNYMI, SREDNEE VREMYA POISKA PRIBLIZITELXNO 
PROPORCIONALXNO~$\sqrt{N}$. chEGO ZHE NAM OZHIDATX OT ALGORITMA~T?

k SCHASTXYU, MOZHNO DOKAZATX, CHTO POISK PO DEREVU TREBUET LISHX OKOLO $2\ln N 
\approx 1.386\log_2 N$ SRAVNENIJ, ESLI KLYUCHI DOBAVLYAYUTSYA K DEREVU V 
SLUCHAJNOM PORYADKE; HOROSHO SBALANSIROVANNYE DEREVXYA---PRAVILO, A VYROZHDENNYE---ISKLYUCHENIE.

dOKAZATX |TOT FAKT UDIVITELXNO PROSTO. pREDPOLOZHIM, CHTO KAZHDAYA IZ 
$N!$~PERESTANOVOK $N$~KLYUCHEJ S RAVNOJ VEROYATNOSTXYU ISPOLXZUETSYA DLYA 
POSTROENIYA DEREVA PUTEM VSTAVOK. chISLO SRAVNENIJ, NUZHNYH DLYA 
NAHOZHDENIYA KLYUCHA, ROVNO NA EDINICU BOLXSHE CHISLA SRAVNENIJ, POTREBOVAVSHIHSYA 
PRI VSTAVKE EGO V DEREVO. sLEDOVATELXNO, ESLI CHEREZ $C_N$ OBOZNACHITX 
SREDNEE CHISLO SRAVNENIJ PRI UDACHNOM POISKE, A CHEREZ $C'_N$---PRI NEUDACHNOM,
 MY POLUCHIM
$$
C_N=1+{C'_0+C'_1+\cdots+C'_{N-1}\over N}.
\eqno(2)
$$
%%508
nO SOGLASNO SOOTNOSHENIYU MEZHDU DLINAMI VNUTRENNEGO I VNESHNEGO PUTEJ (6.2.1-2)
$$
C_N=\left(1+{1\over N}\right)C'_N-1.
\eqno(3)
$$
pODSTAVLYAYA $C_N$ IZ~(3) V~(2), IMEEM
$$
(N+1)C'_N=2N+C'_0+C'_1+\cdots+C'_{N-1}.
\eqno(4)
$$
iZ |TOGO REKURRENTNOGO SOOTNOSHENIYA $C'_N$ NAHODITSYA LEGKO. vYCHITANIE RAVENSTVA
$$
NC'_{N-1}=2(N-1)+C'_0+C'_1+\cdots+C'_{N-2}
$$
DAET
$$
\eqalign{
(N+1)C'_N-NC'_{N-1}&=2+C'_{N-1},\cr
C'_N&=C'_{N-1}+2/(N+1).\cr
}
$$
tAK KAK $C'_0=0$, TO
$$
C'_N=2H_{N+1}-2.
\eqno(5)
$$
pRIMENIV~(3), POSLE UPROSHCHENIJ POLUCHAEM
$$
C_N=2\left(1+{1\over N}\right) H_N-3.
\eqno(3)
$$
uPRAZHNENIYA 6--8 DAYUT BOLEE DETALXNUYU INFORMACIYU: MOZHNO NAJTI NE TOLXKO 
SREDNIE ZNACHENIYA~$C_N$ I~$C'_N$, NO I IH VEROYATNOSTNYE RASPREDELENIYA.

\section sORTIROVKA VSTAVKOJ V DEREVO. aLGORITM~T PREDNAZNACHALSYA 
DLYA POISKA, NO EGO MOZHNO PRINYATX ZA OSNOVU ALGORITMA 
VNUTRENNEJ \emph{SORTIROVKI}, TAK KAK ON YAVLYAETSYA ESTESTVENNYM OBOBSHCHENIEM 
ALGORITMA VSTAVOK V SPISOK~5.2.1L. uMELO ZAPROGRAMMIROVANNYJ, ON BUDET 
RABOTATX LISHX NEMNOGO MEDLENNEE LUCHSHIH ALGORITMOV, OBSUZHDAVSHIHSYA V GL.~5. 
kOGDA POSTROENIE DEREVA ZAVERSHENO, OSTAETSYA SIMMETRICHNO OBOJTI EGO 
(ALGORITM~2.3.1T)---MY "POSETIM" ZAPISI V OTSORTIROVANNOM PORYADKE.

oDNAKO NEOBHODIMO BYTX OSTOROZHNYM. yaSNO, CHTO V SHAGE~T2 PRI $K=|KEY|(|P|)$ 
NADO DEJSTVOVATX PO-DRUGOMU, TAK KAK MY SORTIRUEM, A NE ISHCHEM. mOZHNO, 
NAPRIMER, REAGIROVATX NA $K=|KEY|(|P|)$ TAK ZHE, KAK I NA $K>|KEY|(|P|)$; 
|TO DAST PRAVILXNYJ METOD SORTIROVKI. (zAMETIM, VPROCHEM, CHTO RAVNYE KLYUCHI 
NE OBYAZATELXNO DOLZHNY NAHODITXSYA V SMEZHNYH UZLAH, LISHX BY ONI PROHODILISX 
POSLEDOVATELXNO PRI SIMMETRICHNOM OBHODE.) pRI BOLXSHOM KOLICHESTVE 
POVTORYAYUSHCHIHSYA KLYUCHEJ |TOT METOD PRIVEDET K VESXMA NESBALANSIROVANNOMU 
DEREVU, I SORTIROVKA ZAMEDLITSYA. dRUGIM METODOM YAVLYAETSYA HRANENIE V KAZHDOM 
UZLE SPISKA ZAPISEJ S ODNIM I TEM ZHE KLYUCHOM; POTREBUETSYA 
DOPOLNITELXNOE POLE DLYA SSYLKI, NO |TO USKORIT SORTIROVKU V SLUCHAE, 
KOGDA VSTRECHAETSYA MNOGO ODINAKOVYH KLYUCHEJ.

%%509

tAKIM OBRAZOM, ALGORITM~T, PRIMENYAEMYJ TOLXKO DLYA SORTIROVKI, NEPLOH, NO 
ESTX I LUCHSHIE. eSLI ZHE NUZHNO SOCHETATX POISK I SORTIROVKU, ISPOLXZOVANIE 
DREVOVIDNOJ STRUKTURY SLEDUET NASTOYATELXNO REKOMENDOVATX.

iNTERESNO OTMETITX TESNUYU SVYAZX MEZHDU ANALIZOM SORTIROVKI VSTAVKOJ V 
DEREVO I ANALIZOM OBMENNOJ SORTIROVKI S RAZDELENIEM ("BYSTROJ 
SORTIROVKI"), HOTYA NA PERVYJ VZGLYAD |TI METODY SOVERSHENNO RAZLICHNY. pRI 
VSTAVKE V PERVONACHALXNO PUSTOE DEREVO $N$~KLYUCHEJ V SREDNEM SOVERSHAETSYA 
TO ZHE CHISLO SRAVNENIJ, CHTO I V ALGORITME~5.2.2Q (ZA NEBOLXSHIMI 
ISKLYUCHENIYAMI). nAPRIMER, PRI VSTAVKE V DEREVO KAZHDYJ KLYUCH SRAVNIVAETSYA S 
$K_1$, A KAZHDYJ KLYUCH, MENXSHIJ $K_1$, SRAVNIVAETSYA S PERVYM KLYUCHOM, MENXSHIM 
$K_1$, I T. D.; PRI BYSTROJ SORTIROVKE KAZHDYJ KLYUCH SRAVNIVAETSYA S PERVYM 
RAZDELYAYUSHCHIM |LEMENTOM~$K$, A ZATEM KAZHDYJ KLYUCH, MENXSHIJ $K$, 
SRAVNIVAETSYA S OPREDELENNYM, MENXSHIM $K$ |LEMENTOM I T.~D. sREDNEE CHISLO 
SRAVNENIJ V OBOIH SLUCHAYAH RAVNO $NC_N$. (pRAVDA, NA SAMOM DELE, CHTOBY 
USKORITX VNUTRENNIJ CIKL, ALGORITM~5.2.2Q SOVERSHAET NESKOLXKO BOLXSHE SRAVNENIJ.)

\section uDALENIYA. iNOGDA BYVAET NUZHNO ZASTAVITX evm ZABYTX ODIN 
IZ |LEMENTOV TABLICY. lEGKO UDALITX "LIST" (UZEL, OBA PODDEREVA KOTOROGO 
PUSTY) ILI UZEL, V KOTOROM $|LLINK|=\NULL$ ILI~$|RLINK|=\NULL$. nO ESLI 
OBE SSYLKI NE PUSTY, NADO DEJSTVOVATX OSOBYM OBRAZOM---VEDX NELXZYA V ODNOM 
MESTE HRANITX DVA UKAZATELYA.

v KACHESTVE PRIMERA SNOVA RASSMOTRIM RIS.~10. kAK UDALITX |CAPRICORN|? vOT 
ODNO IZ RESHENIJ: UDALITX \emph{SLEDUYUSHCHIJ} BLIZHAJSHIJ UZEL, LEVAYA SSYLKA 
KOTOROGO PUSTA, I ZATEM VERNUTX EGO NA MESTO UZLA, KOTORYJ DEJSTVITELXNO 
TREBUETSYA UDALITX. nAPRIMER, NA RIS.~10 SNACHALA UDALYAETSYA |GEMINI|, 
ZATEM |CAPRICORN| ZAMENYAETSYA NA |GEMINI|. tAKAYA OPERACIYA SOHRANYAET PORYADOK 
|LEMENTOV TABLICY. aLGORITM~D REALIZUET |TU IDEYU.

\alg D.(uDALENIE IZ DEREVA.) chEREZ |Q| OBOZNACHIM PEREMENNUYU, UKAZYVAYUSHCHUYU 
NA UZEL BINARNOGO DEREVA POISKA, KOTOROE PREDSTAVLENO KAK V ALGORITME~T. 
dANNYJ ALGORITM UDALYAET |TOT UZEL, OSTAVLYAYA BINARNOE DEREVO POISKA. (nA 
SAMOM DELE MY IMEEM ILI $|Q|\equiv|ROOT|$, ILI $|Q|\equiv|LLINK|(|P|)$, 
ILI $|Q|\equiv|RLINK|(|P|)$ DLYA NEKOTOROGO UZLA~|P|. aLGORITM IZMENYAET V 
PAMYATI ZNACHENIE~|Q| V SOOTVETSTVII S OSUSHCHESTVL�NNYM UDALENIEM.)

\st[sSYLKA |RLINK|  PUSTA?] uSTANOVITX $|T|\asg |Q|$. eSLI 
$|RLINK|(|T|)=\NULL$, USTANOVITX $|Q|\asg|LLINK|(|T|)$ I PEREJTI NA~\stp{4}.

\st [nAJTI PREEMNIKA.] uSTANOVITX $|R|\asg|RLINK|(|T|)$. eSLI
$|LLINK|(|R|)=\NULL$, USTANOVITX $|LLINK|(|R|)\asg|LLINK|(|T|)$, 
$|Q|\asg|R|$ I PEREJTI NA~\stp{4}.
%%510
\st[nAJTI PUSTUYU SSYLKU |LLINK|.] uSTANOVITX $|S|\asg|LLINK|(|R|)$. eSLI 
$|LLINK|(|S|)\ne\NULL$, USTANOVITX $|R|\asg|S|$ I POVTORYATX SHAG DO TEH POR,
 POKA NE POLUCHIM $|LLINK|(|S|)=\NULL$. (tEPERX |S| UKAZYVAET NA 
SLEDUYUSHCHIJ POSLE |Q| |LEMENT PRI SIMMETRICHNOM OBHODE.) nAKONEC, USTANOVITX  
$|LLINK|(|S|)\asg|LLINK|(|T|)$, $|LLINK|(|R|)\asg|RLINK|(|S|)$, 
$|RLINK|(|S|)\asg|RLINK|(|T|)$, $|Q|\asg|S|$.

\st[oSVOBODITX UZEL.] vYPOLNITX $|AVAIL|\Asg|T|$ (T.~E. VERNUTX UZEL V PUL 
SVOBODNOJ PAMYATI).
\algend

chITATELX MOZHET ISPYTATX |TOT ALGORITM, UDALYAYA UZLY |AQUARIUS|, |CANCER| 
I~|CAPRICORN| DEREVA RIS.~10; KAZHDYJ SLUCHAJ IMEET SVOI OSOBENNOSTI. 
vNIMATELXNYJ CHITATELX, VEROYATNO, ZAMETIL, CHTO OTDELXNO NE VYDELEN SLUCHAJ 
$|RLINK|(|T|)\ne\NULL$, $|LLINK|(|T|)=\NULL$; MY OBSUDIM |TO NESKOLXKO 
POZZHE, TAK KAK ALGORITM V TOM VIDE, V KOTOROM ON PREDSTAVLEN ZDESX, 
OBLADAET VESXMA INTERESNYMI SVOJSTVAMI.

pOSKOLXKU V ALGORITME~D NET NIKAKOJ SIMMETRII MEZHDU PRAVYM I LEVYM, TO 
KAZHETSYA, CHTO DLINNAYA POSLEDOVATELXNOSTX SLUCHAJNYH UDALENIJ I VSTAVOK 
RAZBALANSIRUET DEREVO, I VYVEDENNYE OCENKI |FFEKTIVNOSTI POTERYAYUT SILU. 
nO V DEJSTVITELXNOSTI VYROZHDENIYA VOVSE NE PROIZOJDET!

\proclaim {tEOREMA n (t.~n.~hIBBARD, 1962)}. pOSLE UDALENIYA POSREDSTVOM 
ALGORITMA~D SLUCHAJNOGO UZLA SLUCHAJNOGO DEREVA VNOVX POLUCHAETSYA SLUCHAJNOE DEREVO.

[nE LYUBYASHCHIE MATEMATIKU, PROPUSTITE, POZHALUJSTA, VPLOTX DO (10)!] tAKAYA 
FORMULIROVKA TEOREMY, RAZUMEETSYA, VESXMA TUMANNA. oPISHEM SITUACIYU BOLEE 
TOCHNO. pUSTX $\cJ$---DEREVO IZ $n$~|LEMENTOV, A $P(\cJ)$---VEROYATNOSTX 
POYAVLENIYA~$\cJ$, ESLI EGO KLYUCHI VSTAVLYAYUTSYA SLUCHAJNYM OBRAZOM S POMOSHCHXYU 
ALGORITMA~T. nEKOTORYE DEREVXYA POYAVLYAYUTSYA S BOLXSHEJ VEROYATNOSTXYU, CHEM 
DRUGIE. chEREZ $Q(\cJ)$ OBOZNACHIM VEROYATNOSTX POLUCHENIYA~$\cJ$ POSLE 
VSTAVKI V SLUCHAJNOM PORYADKE $n+1$~KLYUCHEJ (POSREDSTVOM ALGORITMA~T) I 
POSLEDUYUSHCHEGO UDALENIYA S POMOSHCHXYU ALGORITMA~D ODNOGO IZ |TIH |LEMENTOV, 
VYBRANNOGO SLUCHAJNO. pRI VYCHISLENII~$P(\cJ)$ PREDPOLAGAETSYA, CHTO VSE 
$n~$~PERESTANOVOK KLYUCHEJ RAVNOVEROYATNY;
PRI NAHOZHDENII $Q(\cJ)$ MY SCHITAEM, CHTO $(n+1)(n+1)!$~PERESTANOVOK 
KLYUCHEJ I VYBOROV KLYUCHA DLYA UDALENIYA RAVNOVEROYATNY. tEOREMA UTVERZHDAET, CHTO 
$P(\cJ)=Q(\cJ)$ DLYA VSEH~$\cJ$.

\proof pO USLOVIYU RAVNOVEROYATNY NE DEREVXYA, A PERESTANOVKI, PO|TOMU 
BUDEM DOKAZYVATX TEOREMU, RASSMATRIVAYA V KACHESTVE SLUCHAJNYH OB�EKTOV 
\emph{PERESTANOVKI}. oPREDELIM SNACHALA UDALENIE IZ PERESTANOVKI I ZATEM 
DOKAZHEM, CHTO "POSLE UDALENIYA IZ SLUCHAJNOJ PERESTANOVKI SLUCHAJNOGO 
|LEMENTA OSTAETSYA SLUCHAJNAYA PERESTANOVKA".

%%511

pUSTX $a_1$ $a_2$~\dots $a_{n+1}$---PERESTANOVKA MNOZHESTVA 
$\{\,1, 2,~\ldots, n+1\,\}$;
MY HOTIM OPREDELITX OPERACIYU UDALENIYA |LEMENTA~$a_i$, POLUCHIV V REZULXTATE 
PERESTANOVKU $b_1$ $b_2$~\dots $b_n$  MNOZHESTVA 
$\{\,1, 2,~\ldots, n\,\}$. eTA OPERACIYA DOLZHNA BYTX SOGLASOVANA S 
ALGORITMAMI~t I~D, T.~E. ESLI OTPRAVITXSYA OT DEREVA, POSTROENNOGO 
POSLEDOVATELXNYMI VSTAVKAMI $a_1$, $a_2$,~\dots, $a_{n+1}$, I 
UDALITX~$a_i$  S PERENUMERACIEJ KLYUCHEJ CHISLAMI OT~1 DO~$n$, TO POLUCHITSYA 
DEREVO, KOTOROE MOGLO BYTX POSTROENO POSLEDOVATELXNYMI VSTAVKAMI $b_1$ 
$b_2$~\dots $b_n$.

k SCHASTXYU, OPREDELITX TAKUYU OPERACIYU NETRUDNO. vOZMOZHNY DVA SLUCHAYA:

\medskip{
\narrower
\noindent{\sl sLUCHAJ 1:\/}
 $a_i=n+1$ ILI~$a_i+1=a_j$ DLYA NEKOTOROGO $j<i$. (eTO, V SUSHCHNOSTI, ESTX 
USLOVIE "$|RLINK|(a_i)=\NULL$".) uDALYAEM~$a_i$ IZ POSLEDOVATELXNOSTI I 
VYCHITAEM EDINICU IZ VSEH |LEMENTOV, BOLXSHIH~$a_i$.

\smallskip
\noindent{\sl sLUCHAJ 2:\/}
 $a_i+1=a_j$ DLYA NEKOTOROGO $j>i$. zAMENYAEM $a_i$ NA~$a_j$, UDALYAEM $a_j$ 
S PERVONACHALXNOJ POZICII I VYCHITAEM, EDINICU IZ VSEH |LEMENTOV, BOLXSHIH~$a_i$.

}\medskip

nAPRIMER, RASSMOTRIM PERESTANOVKU 4~6~1~3~5~2. eSLI POMETITX |LEMENT, 
KOTORYJ NUZHNO UDALITX, ZAKLYUCHIV EGO V KRUZHOK, TO POLUCHITSYA
{\def\r#1{\roundit{$#1$}}
$$
\matrix{
\r4 & 6 & 1 & 3 & 5 & 2 & = & 4 & 5 & 1 & 3 & 2 \cr
    4&\r6&1 & 3 & 5 & 2 & = & 4 & 1 & 3 & 5 & 2 \cr
    4& 6 &\r1&3 & 5 & 2 & = & 3 & 5 & 1 & 2 & 4 \cr
}
\qquad
\matrix{
4 & 6 & 1 &\r3& 5 & 2  & = & 3 & 5 & 1 & 4 & 2 \cr
4 & 6 & 1 & 3 &\r5& 2  & = & 4 & 5 & 1 & 3 & 2 \cr
4 & 6 & 1 &3  & 5 &\r2 & = & 3 & 5 & 1 & 2 & 4 \cr
}
$$
}
pOSKOLXKU VSEGO MOZHNO SDELATX $(n+1)(n+1)!$ RAZLICHNYH UDALENIJ, TEOREMA 
BUDET USTANOVLENA, ESLI MY POKAZHEM, CHTO KAZHDUYU PERESTANOVKU MNOZHESTVA 
$\{\, 1, 2,~\dots, n\,\}$ MOZHNO POLUCHITX KAK REZULXTAT PRIMENENIYA ROVNO $(n+1)^2$~UDALENIJ.

rASSMOTRIM PERESTANOVKU $b_1$ $b_2$~\dots $b_n$ MNOZHESTVA 
$\{\, 1, 2,~\dots, n\,\}$. oPREDELIM $(n+1)^2$~UDALENIJ, NO ODNOMU DLYA 
KAZHDOJ PARY $i, j$ ($1\le i,j\le n+1$).

eSLI $i<j$, ISKOMYM UDALENIEM BUDET
$$
b'_1\ldots b'_{i-1} \roundit{b_i} b'_{i+1}\ldots b'_{j-1} (b_i+1) 
b'_j\ldots b'_n.
\eqno(7)
$$
zDESX I DALEE $b'_k$ OBOZNACHAET $b_k$ ILI~$b_k+1$ V ZAVISIMOSTI OTTOGO, 
MENXSHE $b_k$ POMECHENNOGO |LEMENTA ILI NET. eTO UDALENIE SOOTVETSTVUET {\sl SLUCHAYU~2.\/}

eSLI $i>j$, ISKOMYM UDALENIEM BUDET
$$
b'_1\ldots b'_{i-1} \roundit{b_j} b'_i \ldots b'_n,
\eqno(8)
$$
CHTO SOOTVETSTVUET {\sl SLUCHAYU~1.\/}

%% 512

nAKONEC, PRI $i=j$ IMEEM DRUGIE UDALENIYA:
\picture{rIS. STR. 512}
KOTORYE TOZHE OPISYVAYUTSYA {\sl SLUCHAEM~1.\/}

pOLOZHIV $n=4$, RASSMOTRIM V KACHESTVE PRIMERA 25~UDALENIJ, PRIVODYASHCHIH K 
PERESTANOVKE 3~1~4~2:
{\def\r#1{\node{#1}}
\ctable{\hfill$#$\hfill\bskip\bskip&&\hfill$#$\hfill\bskip\bskip\cr
   & i=1 & i=2 & i=3 & i=4 & i=5\cr
j=1&\r5~3~1~4~2 &4~\r3~1~5~2 &4~1~\r3~5~2 &4~1~5~\r3~2 &4~1~5~2~\r3\cr
j=2&\r3~4~1~5~2 &3~\r5~1~4~2 &4~2~\r1~5~3 &4~2~5~\r1~3 &4~2~5~3~\r1\cr
j=3&\r3~1~4~5~2 &4~\r1~2~5~3 &3~1~\r5~4~2 &3~1~5~\r4~2 &3~1~5~2~\r4\cr
j=4&\r3~1~5~4~2 &4~\r1~5~2~3 &3~1~\r4~5~2 &3~1~4~\r5~2 &4~1~5~3~\r2\cr
j=5&\r3~1~5~2~4 &4~\r1~5~3~2 &3~1~\r4~2~5 &4~1~5~\r2~3 &3~1~4~2~\r5\cr
}}

pOMECHENNYJ |LEMENT VSEGDA STOIT V $i\hbox{-J}$ POZICII, I DLYA 
FIKSIROVANNOGO~$i$ MY POSTROILI $(n+1)$ RAZLICHNYH UDALENIJ, PO ODNOMU 
DLYA KAZHDOGO~$j$; SLEDOVATELXNO, DLYA KAZHDOJ PERESTANOVKI $b_1$ $b_2$~\dots 
$b_n$ POSTROENO $(n+1)^2$ RAZLICHNYH UDALENIJ. dLYA ZAVERSHENIYA DOKAZATELXSTVA 
ZAMETIM, CHTO VSEGO IMEETSYA $(n+1)^2!$~UDALENIJ.
\proofend

dOKAZATELXSTVO TEOREMY~H NE TOLXKO OPISYVAET SITUACIYU POSLE UDALENIJ, NO I 
POMOGAET PRI ANALIZE SREDNEGO VREMENI UDALENIYA. uPRAZHNENIE~12 POKAZYVAET, 
CHTO PRI UDALENII SLUCHAJNOGO |LEMENTA IZ SLUCHAJNOJ TABLICY SHAG~D2 
VYPOLNYAETSYA V SREDNEM CHUTX REZHE, CHEM V POLOVINE SLUCHAEV.

rASSMOTRIM TEPERX, SKOLXKO RAZ PROHODITSYA CIKL V SHAGE~D3. pREDPOLOZHIM, CHTO 
UDALYAETSYA UZEL, RASPOLOZHENNYJ NA UROVNE~$l$, A \emph{VNESHNIJ} UZEL, 
NEPOSREDSTVENNO SLEDUYUSHCHIJ ZA NIM PRI SIMMETRICHNOM OBHODE, NAHODITSYA NA 
UROVNE~$k$. nAPRIMER, PRI UDALENII UZLA |CAPRICORN| (RIS.~10) IMEEM 
$l=0$ I~$k=3$, TAK KAK UZEL~\leaf{4} RASPOLOZHEN NA UROVNE~3. eSLI $k=l+1$, 
TO $|RLINK|(|T|)=\NULL$  V SHAGE~D1; ESLI $k>l+1$, MY BUDEM PRISVAIVATX 
$|S|\asg |LLINK|(|R|)$ (SHAG~D3) ROVNO $k-l-2$~RAZ. sREDNEE ZNACHENIE~$l$ RAVNO
$$
(\hbox{DLINA VNUTRENNEGO PUTI})/N;
$$
SREDNEE ZNACHENIE~$k$ RAVNO
$$
(\hbox{DLINA VNESHNEGO PUTI})/N
-(\hbox{RASSTOYANIE DO SAMOGO LEVOGO VNESHNEGO UZLA})/N.
$$
rASSTOYANIE DO SAMOGO LEVOGO VNESHNEGO UZLA RAVNO KOLICHESTVU TAKIH~$a_i$ IZ 
VSTAVLYAEMOJ POSLEDOVATELXNOSTI, CHTO $a_i<a_j$, $1\le j<i$ (VKLYUCHAYA~$a_1$); 
SREDNEE ZNACHENIE |TOJ VELICHINY, SOGLASNO P.~1.2.10,
%%513
ESTX~$H_N$. tAK KAK DLINA VNESHNEGO PUTI NA $2N$ BOLXSHE DLINY VNUTRENNEGO, 
SREDNEE ZNACHENIE~$k-l-2$ RAVNO~$-H_N/N$. dOBAVLYAYA SYUDA SREDNEE KOLICHESTVO 
SLUCHAEV, KOGDA $k-l-2$ ESTX~$-1$, POLUCHAEM, CHTO PRI SLUCHAJNOM UDALENII 
\emph{OPERACIYA $|S|\asg|LLINK|(|R|)$ V SHAGE~D3 VYPOLNYAETSYA V SREDNEM LISHX
$$
{1\over2}+{{1\over2}-H_N\over N}
\eqno(10)
$$
RAZ.} eTO USPOKAIVAET, TAK KAK V NAIHUDSHEM SLUCHAE UDALENIYA MOGUT 
PROIZVODITXSYA DOVOLXNO MEDLENNO (SM. UPR.~11).

vYSHE OTMECHALOSX, CHTO V ALGORITME~D NET PROVERKI $|LLINK|(|T|)=\NULL$, HOTYA 
UDALITX TAKUYU VERSHINU LEGKO. mOZHNO DOBAVITX NOVYJ SHAG MEZHDU~D1 I~D2:
\medskip
D$1{1\over2}$.~[sSYLKA |LLINK| PUSTA?] eSLI $|LLINK|(|T|)=\NULL$, 
USTANOVITX $|Q|\asg|RLINK|(|T|)$ I PEREJTI NA~D4.
\medskip
\noindent uPRAZHNENIE~14 POKAZYVAET, CHTO DEREVO POSLE RABOTY ALGORITMA~D 
S DOPOLNITELXNYM SHAGOM IMEET NE TOLXKO NE BOLXSHUYU, A INOGDA DAZHE MENXSHUYU 
DLINU PUTI, CHEM POSLE RABOTY OBYCHNOGO ALGORITMA~D. tAK CHTO 
POSLEDOVATELXNOSTX VSTAVOK I UDALENIJ S POMOSHCHXYU MODIFIKACII ALGORITMA~D 
PRIVODIT K DEREVXYAM, KOTORYE V DEJSTVITELXNOSTI \emph{LUCHSHE}, CHEM 
PREDSKAZYVAET TEORIYA SLUCHAJNYH DEREVXEV; SREDNEE VREMYA POISKA S VSTAVKOJ 
IMEET TENDENCIYU K UMENXSHENIYU.

\section chASTOTA OBRASHCHENIJ. dO SIH POR PREDPOLAGALOSX, CHTO VSE KLYUCHI S 
RAVNOJ VEROYATNOSTXYU MOGUT BYTX ARGUMENTAMI POISKA. rASSMOTRIM TEPERX 
BOLEE OBSHCHIJ SLUCHAJ, KOGDA S VEROYATNOSTXYU~$p_k$ OTYSKIVAETSYA |LEMENT, 
$k\hbox{-M}$ VSTAVLENNYJ V TABLICU, PRICHEM $p_1+\cdots+p_N=1$. pRI 
SOHRANENII PREDPOLOZHENIYA O SLUCHAJNOM PORYADKE (FORMA DEREVA OSTAETSYA 
SLUCHAJNOJ) MODIFIKACIYA VYRAZHENIYA~(2) POKAZYVAET, CHTO SREDNEE CHISLO 
SRAVNENIJ V PROCESSE UDACHNOGO POISKA SOSTAVLYAET
$$
1+\sum_{1\le k\le N} p_k(2H_k-2)=2\sum_{1\le k\le N} p_kH_k-1.
\eqno(11)
$$
(sR. S~(5).)

nAPRIMER, ESLI VEROYATNOSTI PODCHINYAYUTSYA ZAKONU zIPFA (6.1-8), SREDNEE CHISLO 
SRAVNENIJ SVODITSYA K
$$
H_N-1+H^{(2)}_N/H_N
\eqno(12)
$$
(PREDPOLAGAETSYA, CHTO MY VSTAVLYAEM KLYUCHI V PORYADKE UMENXSHENIYA .VAZHNOSTI; SM.
 UPR.~18). fORMULA~(6) PREDSKAZYVAET PRIMERNO V DVA RAZA BOLXSHUYU VELICHINU; 
PRI BINARNOM POISKE MY TAKZHE PROIZVELI BY BOLXSHE SRAVNENIJ.
%%514
nAPRIMER, NA RIS.~12 IZOBRAZHENO DEREVO, POLUCHENNOE POSLEDOVATELXNYMI 
VSTAVKAMI V PORYADKE UBYVANIYA CHASTOT 31~NAIBOLEE UPOTREBITELXNOGO 
ANGLIJSKOGO SLOVA. oTNOSITELXNAYA CHASTOTA POMESHCHENA POD KAZHDYM SLOVOM. [sR. 
n.~F.~Gaines, Cryptanalysis (New York: Dover, 1956), 226.] sREDNEE CHISLO 
SRAVNENIJ PRI
\picture{rIS. 12 31 NAIBOLEE UPOTREBITELXNOE ANGLIJSKOE SLOVO; VSTAVKI V 
PORYADKE UMENXSHENIYA CHASTOT.}
UDACHNOM POISKE PO TAKOMU DEREVU RAVNO~$4.042$; SOOTVETSTVUYUSHCHIJ BINARNYJ 
POISK, ISPOLXZUYUSHCHIJ ALGORITM~6.2.1v ILI~C, POTREBOVAL BY $4.393$~SRAVNENIYA.

\section oPTIMALXNYE BINARNYE DEREVXYA POISKA. uMESTNO SPROSITX, KAKOE 
DEREVO YAVLYAETSYA NAILUCHSHIM DLYA POISKA PO TABLICE, ESLI KLYUCHI ZAPRASHIVAYUTSYA 
S DANNYMI CHASTOTAMI? nAPRIMER, OPTIMALXNOE DEREVO DLYA 31~NAIBOLEE 
UPOTREBITELXNOGO ANGLIJSKOGO SLOVA IZOBRAZHENO NA RIS.~13; V SREDNEM NA 
UDACHNYJ POISK TREBUETSYA 3.437 SRAVNENIYA.

iSSLEDUEM PROBLEMU NAHOZHDENIYA OPTIMALXNOGO DEREVA. v SLUCHAE $N=3$ I PRI 
SOOTVETSTVENNYH VEROYATNOSTYAH $p$, $q$, $m$ KLYUCHEJ
%%515
%%515
\picture{rIS. 13 oPTIMALXNOE DEREVO POISKA DLYA 31 NAIBOLEE 
UPOTREBITELXNOGO ANGLIJSKOGO SLOVA.}
%%516
$K_1<K_2<K_3$ VOZMOZHNY PYATX DEREVXEV:
\picture{rIS. STR. 516}
nA RIS.~14 POKAZANY DIAPAZONY VELICHIN $p$, $q$, $r$, DLYA KOTORYH KAZHDOE IZ 
DEREVXEV OPTIMALXNO; SBALANSIROVANNOE DEREVO YAVLYAETSYA NAILUCHSHIM PRIMERNO 
V 45\% SLUCHAEV, ESLI $p$, $q$, $r$ SLUCHAJNY (SM. UPR.~21).

\picture{rIS. 14.             zDESX $(p, q, r)$ SUTX OTNOSITELXNYE CHASTOTY 
$(k_1, k_2, k_3)$, |TOT RISUNOK POKAZYVAET; KAKOE IZ PYATI DEREVXEV (13) 
YAVLYAETSYA NAILUCHSHIM. tOT FAKT, CHTO $p+q+r=1$, DELAET RISUNOK DVUMERNYM, 
NESMOTRYA NA NALICHIE TREH KOORDINAT.
}

k SOZHALENIYU, PRI BOLXSHIH $N$ SUSHCHESTVUET
$$
\perm{2N}{N}/(N+1)\approx 4^N/(\sqrt{\pi}N^{3/2})
$$
BINARNYH DEREVXEV, TAK CHTO MY NE V SOSTOYANII VSE IH PEREBRATX I VYBRATX 
NAILUCHSHEE. pO|TOMU, CHTOBY PRIDUMATX BOLEE
%%517
UDACHNYJ SPOSOB OTYSKIVATX OPTIMALXNYE BINARNYE DEREVXYA POISKA, NUZHNO BLIZHE 
POZNAKOMITXSYA S IH SVOJSTVAMI.

dO SIH POR MY IZUCHALI LISHX VEROYATNOSTI PRI UDACHNOM POISKE; OKAZYVAETSYA, 
SLUCHAJ NEUDACHI STOLX ZHE VAZHEN. nAPRIMER, 31 SLOVO (RIS.~13) SOSTAVLYAET 
LISHX OKOLO 36\% TIPICHNOGO ANGLIJSKOGO TEKSTA; OSTALXNYE 64\%, NESOMNENNO, 
POVLIYAYUT NA STRUKTURU OPTIMALXNOGO DEREVA POISKA.

sLEDOVATELXNO, POSTAVIM ZADACHU TAKIM OBRAZOM: DANO $2n+1$~CHISEL $p_1$, 
$p_2$,~\dots, $p_n$ I~$q_0$, $q_1$,~\dots, $q_n$, GDE
$$
\eqalign{
p_i&=\hbox{ VEROYATNOSTX TOGO, CHTO ARGUMENTOM POISKA YAVLYAETSYA $K_i$};\cr
q_i&=\hbox{ VEROYATNOSTX TOGO, CHTO ARGUMENT POISKA LEZHIT MEZHDU $K_i$ I~$K_{i+1}$}.\cr
}
$$
(pO OPREDELENIYU $q_0$ ESTX VEROYATNOSTX TOGO, CHTO ARGUMENT POISKA MENXSHE 
$K_1$, a $q_n$ ESTX VEROYATNOSTX TOGO, CHTO ARGUMENT POISKA BOLXSHE~$K_n$.) 
tAKIM OBRAZOM, 
$p_1+p_2+\cdots+p_n+q_0+q_1+\cdots+q_n=1$, I MY HOTIM NAJTI BINARNOE 
DEREVO, MINIMIZIRUYUSHCHEE MATEMATICHESKOE OZHIDANIE CHISLA SRAVNENIJ PRI POISKE, 
A IMENNO
$$
\sum_{1\le j\le n} p_i(\hbox{UROVENX (\node{$j$})}+1)
+\sum_{0\le k\le n} q_k(\hbox{UROVENX (\leaf{$k$})}),
\eqno(14)
$$
GDE \node{j} ESTX $j\hbox{-J}$~VNUTRENNIJ UZEL PRI SIMMETRICHNOM OBHODE, a 
\leaf{$k$} ESTX $(k+1)\hbox{-J}$~VNESHNIJ UZEL; KORENX NAHODITSYA NA NULEVOM 
UROVNE. tAK, MATEMATICHESKOE OZHIDANIE CHISLA SRAVNENIJ DLYA BINARNOGO DEREVA
\picture{ rIS. STR. 517.}
RAVNO $2q_0+2p_1+3q_1+3p_2+3q_2+p_3+q_3$. nAZOVEM |TO \dfn{CENOJ} DEREVA; 
SKAZHEM, CHTO DEREVO S MINIMALXNOJ CENOJ \emph{OPTIMALXNO}. pRI TAKOM 
OPREDELENII NET NUZHDY TREBOVATX, CHTOBY $p$ I~$q$ DAVALI V SUMME EDINICU, 
MOZHNO ISKATX DEREVO S MINIMALXNOJ CENOJ DLYA DANNOJ POSLEDOVATELXNOSTI 
"VESOV" ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$).

v P.~2.3.4.5 MY IZUCHILI PROCEDURU hAFFM|NA DLYA POSTROENIYA DEREVXEV S 
MINIMALXNOJ VZVESHENNOJ DLINOJ PUTI, NO |TOT METOD TREBUET, CHTOBY VSE $p$ 
RAVNYALISX NULYU, A V POROZHDENNOM IM DEREVE VNESHNIE UZLY, IMEYUSHCHIE VESA 
($q_0$,~\dots, $q_n$), OBYCHNO NE
%%518
RASPOLAGAYUTSYA V NUZHNOM SIMMETRICHNOM PORYADKE SLEVA NAPRAVO. zNACHIT, 
NEOBHODIMO DEJSTVOVATX INACHE.

vOSPOLXZUEMSYA SLEDUYUSHCHIM PRINCIPOM: \emph{LYUBOE PODDEREVO OPTIMALXNOGO 
DEREVA OPTIMALXNO}. nAPRIMER, ESLI~(15) ESTX OPTIMALXNOE DEREVO DLYA 
VESOV $(p_1, p_2, p_3; q_0, q_1, q_2, q_3)$, TO LEVOE PODDEREVO KORNYA 
DOLZHNO BYTX OPTIMALXNYM DLYA 
$(p_1, p_2; q_0, q_1, q_2)$, T.~E. LYUBOE ULUCHSHENIE PODDEREVA VEDET K 
ULUCHSHENIYU VSEGO DEREVA.

eTOT PRINCIP PODSKAZYVAET VYCHISLITELXNUYU PROCEDURU, S POMOSHCHXYU KOTOROJ 
SISTEMATICHESKI NAHODYATSYA VS� BOLXSHIE I BOLXSHIE OPTIMALXNYE PODDEREVXYA. mY 
VOSPOLXZOVALISX ABSOLYUTNO TOJ ZHE IDEEJ V P.~5.4.9 DLYA POSTROENIYA SHEM 
OPTIMALXNOGO SLIYANIYA; OBSHCHIJ PODHOD, IZVESTNYJ POD NAZVANIEM 
"DINAMICHESKOE PROGRAMMIROVANIE", BUDET IZUCHEN V GL.~7.

chEREZ $c(i, j)$ OBOZNACHIM CENU OPTIMALXNOGO PODDEREVA S VESAMI $(p_{i+1},
~\ldots, p_j, q_i,~\ldots, q_j)$, I PUSTX 
$w(i,j)=p_{i+1}+\cdots+p_j+q_i+\cdots+q_j$ BUDET SUMMOJ |TIH VESOV; $c(i, 
j)$ I~$w(i,j)$ OPREDELYAYUTSYA DLYA $0\le i\le j\le n$. tAK KAK MINIMALXNO 
VOZMOZHNAYA CENA DEREVA S KORNEM~\node{$k$} RAVNA 
$w(i,j)+c(i, k-1)+c(k,j)$, IMEEM
$$
\eqalign{
c(i,i)&=0;\cr
c(i,j)&=w(i,j)+\min_{i\le k <j} (c(i,k-1)+c(k,j)) \rem{ PRI $i<j$.}\cr
}
\eqno(16)
$$
eSLI $i<j$, TO CHEREZ $R(i, j)$ OBOZNACHIM MNOZHESTVO VSEH~$k$, PRI KOTORYH 
DOSTIGAETSYA MINIMUM V~(16); |TO MNOZHESTVO OPREDELYAET VOZMOZHNYE KORNI 
OPTIMALXNYH PODDEREVXEV.

sOOTNOSHENIYA~(16) POZVOLYAYUT NAJTI ZNACHENIYA~$c(i, j)$ DLYA
$j-i=1$, 2, 3,~\dots, $n$; SUSHCHESTVUET PRIMERNO ${1\over2}n^2$ TAKIH 
ZNACHENIJ, A OPERACIYA MINIMIZACII VYPOLNYAETSYA DLYA PRIBLIZITELXNO 
${1\over6}n^3$ VELICHIN~$k$. eTO ZNACHIT, CHTO OPTIMALXNOE DEREVO MOZHNO NAJTI 
ZA $O(n^3)$~EDINIC VREMENI, ISPOLXZUYA $O(n^2)$~YACHEEK PAMYATI.

v OCENKE VREMENI RABOTY POKAZATELX STEPENI PRI~$n$ MOZHNO UMENXSHITX, ESLI 
VOSPOLXZOVATXSYA SVOJSTVOM "MONOTONNOSTI". pUSTX $r(i,j)$ OBOZNACHAET 
|LEMENT IZ~$R(i,j)$; NET NUZHDY NAHODITX VSE MNOZHESTVO~$R(i,j)$, NAM 
DOSTATOCHNO ODNOGO PREDSTAVITELYA. v SILU REZULXTATA UPR.~27 POSLE 
NAHOZHDENIYA $r(i,j-1)$ I~$r(i+1, j)$ |LEMENT~$r(i, j)$ MOZHNO ISKATX V PREDELAH
$$
r(i, j-1)\le r(i,j) \le r(i+1, j)
\eqno(17)
$$
PRI USLOVII NEOTRICATELXNOSTI VESOV. tEPERX V~(16) VMESTO $i-j$ NUZHNO 
PROVERYATX LISHX $r(i+1, j)-r(i, j-1)+1$ ZNACHENIJ~$k$.
%%519
pOLNYJ OB�EM RABOTY, ESLI $j-i=d$, OCENIVAETSYA SUMMOJ
$$
\sum_{\scriptstyle d\le j\le n\atop\scriptstyle i=j-d}
(r(i+1,j)-r(i, j-1)+1)=
r(n-d+1,n)+r(0, d-1)+n-d+1<2n,
$$
PO|TOMU VREMYA VYPOLNENIYA UMENXSHAETSYA DO~$O(n^2)$.

pREDLOZHENNAYA PROCEDURA PODROBNO OPISANA NIZHE.

\alg K.(nAHOZHDENIE OPTIMALXNYH BINARNYH DEREVXEV POISKA.)
dANY NEOTRICATELXNYE VESA ($p_1$,~\dots, $p_n$; $q_0$, $q_1$,~\dots, 
$q_n$).  aLGORITM POZVOLYAET POSTROITX BINARNYE DEREVXYA~$t(i,j)$, 
IMEYUSHCHIE MINIMALXNUYU (V UKAZANNOM VYSHE SMYSLE) CENU DLYA VESOV 
($p_{i+1}$,~\dots, $p_j$; $q_i$,~\dots, $q_j$). vYCHISLYAYUTSYA TRI MASSIVA:
$$
\matrix{
c[i,j]\hbox{---CENA $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
r[i,j]\hbox{---KORENX $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
w[i,j]\hbox{---POLNYJ VES $t(i,j)$,\hfill} & 0\le i\le j\le n;\cr
}
$$
rEZULXTATY ALGORITMA OPREDELYAYUTSYA MASSIVOM~$r$: ESLI $i=j$, TO
$t(i,j)$ PUSTO; ESLI $i\ne j$, TO LEVYM PODDEREVOM YAVLYAETSYA
$t(i, r[i,j]-1)$, A PRAVYM---$t(r[i,j], j)$.

\st[nACHALXNAYA USTANOVKA.] dLYA $0\le i \le n$ USTANOVITX $c[i, i]\asg0$,
$w[i,i]\asg q_i$  I~$w[i,j]\asg w[i,j-1]+p_j+q_j$ PRI~$j=i+1$,~\dots, $n$. 
zATEM DLYA $1\le j \le n$ USTANOVITX $c[j-1,j]\asg w[j-1,j]$ I~$r[j-1,
j]\asg j$. (eTIM OPREDELYAYUTSYA VSE OPTIMALXNYE DEREVXYA, SOSTOYASHCHIE IZ ODNOGO UZLA.)

\st[cIKL PO $d$.] vYPOLNITX SHAG~\stp{3} DLYA $d=2$, 3,~\dots, $n$; 
POSLE |TOGO ALGORITM ZAVERSHAET RABOTU.

\st[cIKL PO $j$.] (k |TOMU, MOMENTU NAJDENY OPTIMALXNYE DEREVXYA S MENEE 
CHEM $d$~UZLAMI. shAG OPREDELYAET VSE OPTIMALXNYE DEREVXYA S $d$~UZLAMI.) 
vYPOLNITX SHAG~\stp{4} DLYA $j=d$, $d+1$,~\dots, $n$.

\st[nAJTI $c[i,j]$, $r[i,j]$.] uSTANOVITX $i\asg j-d$, ZATEM USTANOVITX
$$
c[i,j]\asg w[i,j]+\min_{r[i,j-1]\le k \le r[i+1, j]} (c[i,k-1]+c[k,j])
$$
I ZANESTI V $r[i,j]$ VELICHINU~$k$, PRI KOTOROJ DOSTIGAETSYA MINIMUM. (v 
UPR.~22 DOKAZYVAETSYA,  CHTO $r[i, j-1]\le r[i+1, j]$.)
\algend

kAK PRIMER RABOTY ALGORITMA~K RASSMOTRIM RIS.~15, SVYAZANNYJ 
SORAZRABOTKOJ UKAZATELYA KWIC ("key-word-in-context"---"KLYUCHEVOE SLOVO V 
KONTEKSTE"). zAGOLOVKI VSEH STATEJ PERVYH DESYATI TOMOV {\sl ACM Journal\/} 
BYLI OTSORTIROVANY TAKIM OBRAZOM, CHTOBY KAZHDOMU SLOVU KAZHDOGO ZAGOLOVKA 
SOOTVETSTVOVALA ODNA STROKA. pRAVDA, NEKOTORYE SLOVA VRODE "|THE|" I~"|EQUATION|"
%%520
\picture{  rIS 15. oPTIMALXNOE BINARNOE DEREVO POISKA DLYA PRIMENENIYA 
UKAZATELYA KWIC.}
%%521
BYLI PRIZNANY NEINFORMATIVNYMI I NE POPALI V UKAZATELX. eTI SPECIALXNYE 
SLOVA I CHASTOTY IH POYAVLENIJ PREDSTAVLENY NA RIS.~15 VNUTRENNIMI UZLAMI. 
zAMETIM, CHTO TAKOE NAZVANIE, KAK "On the solution of an equation for a 
certain new problem" ("o RESHENII URAVNENIYA DLYA NEKOTOROJ NOVOJ ZADACHI"), 
BYLO BY NASTOLXKO NEINFORMATIVNYM, CHTO VOOBSHCHE NE POPALO BY V UKAZATELX! 
iDEYA UKAZATELYA~KWIC PRINADLEZHIT g.~p.~lANU 
[{\sl Amer. Documentation,\/} {\bf 11} (1960), 288--295]. pOLNOSTXYU 
UKAZATELX~KWIC PRIVEDEN V RABOTE 
[W.~W.~Youden, {\sl JACM,\/} {\bf 10} (1963), 583--646].

pRI PODGOTOVKE UKAZATELYA~KWIC MOZHNO BYLO ISPOLXZOVATX BINARNOE DEREVO 
POISKA DLYA PROVERKI, NUZHNO LI VNOSITX TO ILI INOE SLOVO V UKAZATELX. 
chASTOTAM POYAVLENIYA SLOV, VKLYUCHENNYH V UKAZATELX, SOOTVETSTVUYUT VNESHNIE 
UZLY DEREVA RIS.~15;
TAK, V ZAGOLOVKAH STATEJ {\sl JACM\/} ZA~1954--1963~GG. VSTRETILISX ROVNO 
277~SLOV, RASPOLOZHENNYH PO ALFAVITU MEZHDU "|PROBLEMS|" I~"|SOLUTION|".

nA RIS.~15 IZOBRAZHENO OPTIMALXNOE DEREVO, POLUCHENNOE S POMOSHCHXYU ALGORITMA~K 
PRI~$n=35$. zNACHENIYA~$r[0,j]$, VYCHISLENNYE DLYA $j=1$, $2$,~\dots, $35$, 
RAVNY (1, 1, 2, 3, 3, 3, 3, 8, 8, 8,  8, 8, 8, 11, 11,~\dots, 11, 21, 21, 
21, 21, 21, 21); ZNACHENIYA~$r[i, 35]$ DLYA~$i=0$, 1,~\dots, 34 RAVNY (21, 21,
~\dots, 21, 25, 25, 25, 25, 25, 25, 26, 26, 26, 30, 30, 30, 30, 30, 30, 30,
 33, 33, 33, 35, 35).

"pROMEZHUTOCHNYE CHASTOTY"~$q_j$ ZAMETNO VLIYAYUT NA OPTIMALXNUYU STRUKTURU 
DEREVA; NA RIS.~16~(a) PRIVEDENO OPTIMALXNOE DEREVO, KOTOROE POLUCHILOSX BY 
PRI NULEVYH~$q_j$. tAK ZHE VAZHNY I VNUTRENNIE CHASTOTY~$p_i$; NA RIS.~16~(b) 
IZOBRAZHENO OPTIMALXNOE DEREVO PRI NULEVYH~$p_i$. vERNEMSYA K POLNOMU 
NABORU CHASTOT. dEREVO RIS.~15 TREBUET V SREDNEM LISHX $4.75$~SRAVNENIYA, A 
DEREVXYA RIS.~16---SOOTVETSTVENNO~$5.29$ I~$5.32$. (pRYAMOJ BINARNYJ POISK V 
DANNOM SLUCHAE BYL BY LUCHSHE DEREVXEV RIS.~16.)

tAK KAK ALGORITM~K TREBUET $O(n^2)$~VREMENI I PROSTRANSTVA, EGO 
ISPOLXZOVANIE PRI BOLXSHIH~$n$ STANOVITSYA NERACIONALXNYM. kONECHNO, V |TOM 
SLUCHAE MOZHNO BY ISPOLXZOVATX DRUGIE METODY POISKA, I DALEE V |TOJ GLAVE 
ONI BUDUT OBSUZHDATXSYA. dAVAJTE PREDPOLOZHIM, CHTO NUZHNO NAJTI OPTIMALXNOE 
ILI POCHTI OPTIMALXNOE DEREVO, ESLI $n$ VELIKO.

mY VIDELI, CHTO IDEYA VSTAVKI KLYUCHEJ V PORYADKE UMENXSHENIYA CHASTOT V SREDNEM 
VEDET K DOVOLXNO HOROSHIM DEREVXYAM; NO DEREVO MOZHET POLUCHITXSYA I OCHENX 
PLOHIM (SM.~UPR.~20), TAK KAK NE ISPOLXZUYUTSYA VESA~$q_j$. dRUGOJ PODHOD 
SOSTOIT V VYBORE KORNYA~$k$ TAKIM OBRAZOM, CHTOBY MAKSIMALXNYJ VES 
POLUCHAYUSHCHEGOSYA PODDEREVA $\max(w(0, k-1), w(k, n))$ BYL KAK MOZHNO MENXSHE. 
eTOT PODHOD TAKZHE NEUDACHEN, IBO V KACHESTVE KORNYA MOZHET BYTX VYBRAN UZEL S 
OCHENX MALYM~$p_k$. oDNAKO pOL b|JER DOKAZAL, CHTO POLUCHIVSHEESYA DEREVO 
BUDET IMETX VZVESHENNUYU DLINU PUTI, BLIZKUYU K OPTIMALXNOJ.

%%522

u.~e.~uOLKER I~k.~k.~gOTLIB [Graph Theory and Computing (Academic Press, 
1972)] PREDLOZHILI BOLEE UDOVLETVORITELXNUYU PROCEDURU, SOCHETAYUSHCHUYU OBA 
RASSMOTRENNYH METODA: POPYTAJTESX URAVNYATX LEVOSTORONNIE I PRAVOSTORONNIE 
VESA, NO BUDXTE GOTOVY PEREDVINUTX KORENX NA NESKOLXKO SHAGOV VPRAVO ILI 
VLEVO DLYA NAHOZHDENIYA UZLA S OTNOSITELXNO BOLXSHIM VESOM~$p_k$. rISUNOK~17
\picture{rIS. 16. oPTIMALXNYE BINARNYE DEREVXYA POISKA, OSNOVANNYE NA 
POLOVINE DANNYH RIS.~15, (a) NE UCHITYVAYUTSYA VNESHNIE CHASTOTY; (b) NE 
UCHITYVAYUTSYA VNUTRENNIE CHASTOTY.}
POKAZYVAET, POCHEMU |TOT METOD RAZUMEN: ESLI MY IZOBRAZIM $c(0, k-1)+c(k, 
n)$ KAK FUNKCIYU OT~$k$ DLYA DANNYH KWIC (SM. RIS.~15), TO UVIDIM, CHTO 
REZULXTAT OCHENX CHUVSTVITELEN K VELICHINE~$p_k$.

%%523

tAKOJ METOD "SVERHU VNIZ" MOZHNO ISPOLXZOVATX PRI BOLXSHIH~$n$ DLYA VYBORA 
KORNYA I DLYA OBRABOTKI LEVYH I PRAVYH PODDEREVXEV. eSLI POLUCHITSYA 
DOSTATOCHNO MALENXKOE PODDEREVO, MOZHNO PRIMENITX ALGORITM~K. 
rEZULXTIRUYUSHCHIJ METOD DAET DOVOLXNO HOROSHIE DEREVXYA (SOGLASNO SOOBSHCHENIYAM),
 NA 2--3\% HUZHE OPTIMUMA, A TREBUET LISHX $O (n)$~EDINIC PROSTRANSTVA I 
$O(n \log n)$~EDINIC
\picture{rIS. 17. pOVEDENIE CENY KAK FUNKCII KORNYA~$k$ (SLEVA PO OSI  
ORDINAT OTLOZHEN MINIMUM SREDNEJ CENY).
}
VREMENI. nA SAMOM DELE m.~fREDM|N POKAZAL, CHTO DOSTATOCHNO $O(n)$~EDINIC 
VREMENI, ESLI ISPOLXZOVATX PODHODYASHCHIE STRUKTURY DANNYH [ACM. Symp. Theory 
of Comp., 7 (1975), 240--244].

\section *aLGORITM hU-tAKERA. v SPECIALXNOM SLUCHAE, KOGDA VSE~$p$ RAVNY 
NULYU, t.~ch.~hU I~e.~k.~tAKER OTKRYLI ZAMECHATELXNYJ SPOSOB POSTROENIYA 
OPTIMALXNYH DEREVXEV "SNIZU VVERH"; PRI ISPOLXZOVANII PODHODYASHCHIH 
STRUKTUR DANNYH IH METOD TREBUET $O(n)$~EDINIC PROSTRANSTVA I~$O(n\log 
n)$~EDINIC VREMENI I STROIT DEREVO, NE BLIZKOE K OPTIMALXNOMU, A 
\emph{DEJSTVITELXNO} OPTIMALXNOE. aLGORITM hU-tAKERA MOZHNO OPISATX TAK.

\noindent $\bullet$~{\bf faza 1.} kOMBINACIYA. nACHNITE S "RABOCHEJ 
POSLEDOVATELXNOSTI" VESOV, NAPISANNYH VNUTRI \emph{VNESHNIH} UZLOV
\picture{ rIS. STR. 523}
zATEM RAZ ZA RAZOM KOMBINIRUJTE DVA VESA~$q_i$ I~$q_j$ DLYA~$i<j$, POLUCHAYA 
EDINSTVENNYJ VES~$q_i+q_j$, ISKLYUCHITE $q_j$ IZ POSLEDOVATELXNOSTI I 
ZAMENITE UZEL, SODERZHASHCHIJ~$q_i$, NA \emph{VNUTRENNIJ} UZEL
\picture{ rIS. STR. 523}
%%524
kOMBINIROVATX NUZHNO EDINSTVENNUYU PARU VESOV~$(q_i, q_j)$, 
UDOVLETVORYAYUSHCHUYU SLEDUYUSHCHIM PRAVILAM:

{\medskip\narrower
\item{i)}~mEZHDU $q_i$ I~$q_j$ NET VNESHNIH UZLOV. (eTO NAIBOLEE VAZHNOE 
PRAVILO, OTLICHAYUSHCHEE DANNYJ ALGORITM OT METODA hAFFM|NA.)

\item{ii)}~sUMMA~$q_i+q_j$ MINIMALXNA SREDI VSEH~$(q_i, q_j)$,  
UDOVLETVORYAYUSHCHIH PRAVILU~(i).

\item{iii)}~iNDEKS~$i$ MINIMALEN SREDI VSEH~$(q_i, q_j)$, UDOVLETVORYAYUSHCHIH 
PRAVILAM (i), (ii).

\item{iv)}~iNDEKS~$j$ MINIMALEN SREDI VSEH~$(q_i, q_j)$, UDOVLETVORYAYUSHCHIH 
PRAVILAM (i)--(iii).
\medskip}

\noindent $\bullet$~{\bf faza 2.} pRISVAIVANIE UROVNEJ. kOGDA FAZA~1 
OKONCHENA, V RABOCHEJ POSLEDOVATELXNOSTI OSTAETSYA EDINSTVENNYJ 
UZEL. pOMETXTE EGO NOMEROM UROVNYA~0. zATEM PRODELAJTE SHAGI FAZY~1 V 
OBRATNOM PORYADKE, TAKIM OBRAZOM POMECHAYA UZLY NOMERAMI UROVNEJ, CHTO, ESLI 
(19)~IMEET UROVENX~$l$, UZLY~$q_i$ I~$q_j$, PORODIVSHIE~(19), POLUCHAYUT 
NOMER~$l+1$.

\noindent $\bullet$~{\bf faza 3.} rEKOMBINACIYA. tEPERX U NAS ESTX 
POSLEDOVATELXNOSTX VNESHNIH UZLOV I UROVNEJ
\picture{rIS. STR. 524}
vNUTRENNIE UZLY, ISPOLXZOVANNYE V FAZAH~1 I~2, TEPERX OTBROSXTE ZA 
NENADOBNOSTXYU---MY BUDEM SOZDAVATX NOVYE UZLY PUTEM KOMBINACII VESOV~$(q_i, 
q_j)$ PO SLEDUYUSHCHIM NOVYM PRAVILAM:

{\medskip\narrower
\item{$\hbox{i}'$)}~uZLY, SODERZHASHCHIE~$q_i$ I~$q_j$, DOLZHNY BYTX SOSEDNIMI V
RABOCHEJ POSLEDOVATELXNOSTI.

\item{$\hbox{ii}'$)}~oBA UROVNYA~$l_i$ I~$l_j$ DOLZHNY BYTX MAKSIMALXNYMI 
SREDI VSEH OSTAYUSHCHIHSYA.

\item{$\hbox{iii}'$')}~iNDEKS~$i$ DOLZHEN BYTX MINIMALXNYM SREDI VSEH~$(q_i,
 q_j)$, UDOVLETVORYAYUSHCHIH~($\hbox{i}'$) I~($\hbox{ii}'$).
\medskip}

\noindent nOVOMU UZLU~(19) PRISVAIVAETSYA UROVENX~$l_i-1$. bINARNOE 
DEREVO, FORMIRUEMOE V |TOJ FAZE, IMEET MINIMALXNUYU VZVESHENNUYU DLINU PUTI 
SREDI VSEH BINARNYH DEREVXEV, VNESHNIE UZLY KOTORYH IMEYUT VESA (SLEVA 
NAPRAVO) $q_0$, $q_1$,~\dots, $q_n$.

rISUNOK~18 ILLYUSTRIRUET RABOTU |TOGO ALGORITMA; VESAMI YAVLYAYUTSYA 
OTNOSITELXNYE CHASTOTY BUKV~\], |A|, |B|,~\dots, |Z| V ANGLIJSKOM TEKSTE. 
v TECHENIE FAZY~1 PERVYM FORMIRUETSYA UZEL~\node{6}, SODERZHASHCHIJ CHASTOTY 
BUKV~|J| I~|K|, ZATEM UZEL~\node{16} (KOMBINIRUEM |P| I~|Q|), ZATEM
\picture{rIS. STR. 524}
%% 525
\picture{rIS. 18.  aLGORITM hU-tAKERA, PRIMENENNYJ K DANNYM O CHASTOTAH 
BUKV; FAZY~1 I~2.}
%% 526
V |TOT MOMENT MY IMEEM RABOCHUYU POSLEDOVATELXNOSTX
\picture{rIS. STR. 526}
pRAVILO~(i) POZVOLYAET KOMBINIROVATX NESMEZHNYE VESA, TOLXKO ESLI ONI 
RAZDELENY VNUTRENNIMI UZLAMI; TAK CHTO MOZHNO SKOMBINIROVATX $57+57$, 
ZATEM $63 +51$, ZATEM $58+64$ I~T.~D.

nOMERA UROVNEJ, PRISVOENNYE VO VREMYA FAZY~2, IZOBRAZHENY NA RIS.~18 SPRAVA 
OT KAZHDOGO UZLA. v REZULXTATE REKOMBINACII (FAZA~3) MY POLUCHAEM DEREVO, 
POKAZANNOE NA RIS.~19; ZAMETXTE, CHTO DEREVXYA RIS.~18 I~19 SUSHCHESTVENNO 
RAZLICHNY: RIS.~18 NE SOHRANYAET UPORYADOCHENNOSTI SLEVA NAPRAVO. nO CENY U 
|TIH DEREVXEV ODINAKOVY, TAK KAK VNESHNIE UZLY RASPOLOZHENY NA ODINAKOVYH UROVNYAH.

rASSMOTRIM PROSTOJ PRIMER, GDE VESA RAVNY 4, 3, 2, 4; LEGKO POKAZATX, CHTO 
EDINSTVENNYM OPTIMALXNYM DEREVOM YAVLYAETSYA
\picture{rIS. STR. 526}
nA |TOM PRIMERE VIDNO, CHTO V OPTIMALXNOM DEREVE DVA NAIMENXSHIH VESA~2 
I~3 \emph{NE} VSEGDA SLEDUET KOMBINIROVATX V ODNO OPTIMALXNOE DEREVO, 
DAZHE ESLI ONI PRIPISANY SMEZHNYM UZLAM;
NUZHNA NEKOTORAYA REKOMBINACIONNAYA FAZA.

v NASHEJ KNIGE NE PRIVODITSYA DOKAZATELXSTVO SPRAVEDLIVOSTI ALGORITMA 
hU-tAKERA; PROSTYE DOKAZATELXSTVA NE IZVESTNY, I OCHENX VEROYATNO, CHTO ONI 
NIKOGDA NE BUDUT NAJDENY! chTOBY PROILLYUSTRIROVATX VNUTRENNE PRISUSHCHUYU 
DANNOJ SITUACII SLOZHNOSTX, ZAMETIM, CHTO FAZA~3 DOLZHNA SKOMBINIROVATX VSE 
UZLY V ODNO DEREVO, NO VOZMOZHNOSTX |TOGO NE OCHEVIDNA. nAPRIMER, 
 PREDPOLOZHIM, CHTO FAZY~1 I~2 PRIVELI K DEREVU
\picture{rIS. STR. 526}
%%527
\picture{rIS. 19. aLGORITM hU-tAKERA, PRIMENENNYJ K DANNYM O CHASTOTAH 
BUKV; FAZA 3.}
%% 528
(T.~E. BYLI POLUCHENY UZLY \node{$a$}, \node{$b$}, \node{$c$}, \node{$d$}, 
\node{$e$} V UKAZANNOM PORYADKE); |TO SOGLASUETSYA S PRAVILOM~(i). zATEM 
POSLE FORMIROVANIYA UZLOV
\picture{rIS. STR. 528}
MY NE SMOZHEM PRODOLZHITX FAZU~3, TAK KAK UZLY UROVNYA~3 NESMEZHNYE! 
pRAVILO~(i) SAMO PO SEBE NE GARANTIRUET BLAGOPOLUCHNOGO ZAVERSHENIYA FAZY~3,
 I NEOBHODIMO DOKAZYVATX, CHTO KONFIGURACIYA, PODOBNAYA~(22), 
\emph{NIKOGDA} NE POLUCHAETSYA NA FAZE~1.

pRI REALIZACII ALGORITMA hU-tAKERA MOZHNO HRANITX PRIORITETNYE OCHEREDI DLYA 
MNOZHESTVA VESOV V UZLAH, MEZHDU KOTORYMI NET VNESHNIH UZLOV. nAPRIMER, 
(20) MOZHNO BYLO BY PREDSTAVITX PRIORITETNYMI OCHEREDYAMI, SODERZHASHCHIMI 
SOOTVETSTVENNO 
\picture{rIS. STR. 528}
I INFORMACIEJ O TOM, KAKIE IZ UZLOV VNESHNIE, A TAKZHE UKAZANIEM NA 
PORYADOK SLEVA NAPRAVO (|TO NUZHNO DLYA PRIMENENIYA PRAVIL~(iii) I~(iv)). v 
DRUGOJ, "UPRAVLYAYUSHCHEJ" PRIORITETNOJ OCHEREDI MOZHNO ZAPOMINATX SUMMY DVUH 
NAIMENXSHIH |LEMENTOV OCHEREDEJ. sOZDANIE NOVOGO UZLA~$57+57$ VYZYVAET 
SLIYANIE TREH OCHEREDEJ. eSLI PRIORITETNYE OCHEREDI PREDSTAVLENY 
LEVOSTORONNIMI DEREVXYAMI (SM. P.~5.2.3), TO KAZHDYJ SHAG FAZY~1 TREBUET NE 
BOLEE $O(\log n)$~OPERACIJ; ZNACHIT, PRI~$n\to\infty$ DOSTATOCHNO $O(n \log 
n)$~OPERACIJ. kONECHNO, PRI NEBOLXSHIH~$n$ BOLEE |FFEKTIVNYM BUDET 
OTNOSITELXNO BOLEE PRYAMOLINEJNYJ $O(n^2)\hbox{-SPOSOB}$ REALIZACII.

oPTIMALXNOE BINARNOE DEREVO RIS.~19 POLEZNO NE TOLXKO DLYA POISKA, NO I DLYA 
TEORII KODIROVANIYA: ISPOLXZUYA 0 DLYA OBOZNACHENIYA LEVOJ VETVI DEREVA I~1 DLYA 
PRAVOJ, POLUCHAEM SLEDUYUSHCHIE KODY RAZLICHNOJ DLINY:
$$
\vcenter{
\halign{
|#| \bskip & $#$\hfill \bskip\bskip\bskip &&|#| \bskip & $#$\hfill \bskip\bskip\bskip\cr
\] & 000    & I & 1000    & R & 11001 \cr
A  & 0010   & J & 1001000 & S & 1101 \cr
v  & 001100 & K & 1001001 & T &  1110 \cr
C  & 001101 & L & 100101  & U & 111100\cr
D  & 00111  & M & 10011   & V &  111101 \cr
E  & 010    & N & 1010    & W & 111110 \cr
F  & 01100  & O & 1011    & X & 11111100\cr
G  & 01101  & P & 110000  & Y & 11111101\cr
H  & 0111   & Q & 110001  & Z & 1111111\cr
}
}
\eqno(24)
$$
%%529
tAKIM OBRAZOM, SOOBSHCHENIE VRODE "|RIGHT ON|" MOZHNO ZAKODIROVATX CEPOCHKOJ
$$
|110011000011010111111000010111010|.
$$
zAMETIM, CHTO PEREMENNAYA DLINA KODOV NE ZATRUDNYAET RASSHIFROVKU SLEVA 
NAPRAVO, TAK KAK STRUKTURA DEREVA PODSKAZYVAET, KOGDA KONCHAETSYA KOD ODNOJ 
BUKVY I NACHINAETSYA DRUGOJ. tAKOJ METOD KODIROVANIYA SOHRANYAET ALFAVITNYJ 
PORYADOK I ISPOLXZUET DLYA KODIROVANIYA ODNOJ BUKVY V SREDNEM OKOLO 4.2~BITOV.
 eTOT KOD MOZHNO ISPOLXZOVATX DLYA UPLOTNENIYA FAJLOV DANNYH BEZ NARUSHENIYA 
LEKSIKOGRAFICHESKOGO PORYADKA BUKVENNOJ INFORMACII. (chISLO~$4.2$ 
MINIMALXNO DLYA KODIROVANIYA S POMOSHCHXYU BINARNYH DEREVXEV, HOTYA EGO MOZHNO 
UMENXSHITX DO $4.1$~BITOV NA BUKVU, ESLI OTKAZATXSYA OT SOHRANENIYA 
ALFAVITNOGO PORYADKA. uMENXSHENIE S SOHRANENIEM ALFAVITNOGO PORYADKA 
DOSTIGAETSYA KODIROVANIEM NE OTDELXNYH BUKV, A PAR BUKV.)

iNTERESNAYA ASIMPTOTICHESKAYA OCENKA MINIMALXNOJ VZVESHENNOJ DLINY PUTI 
DEREVXEV POISKA VYVEDENA e.~n.~gILBERTOM I~e.~f.~mUROM:

\proclaim tEOREMA G. eSLI $p_1=p_2=\cdots=p_n=0$, TO VZVESHENNAYA DLINA PUTI 
OPTIMALXNOGO BINARNOGO DEREVA POISKA ZAKLYUCHENA MEZHDU
$$
\sum_{0\le i \le n} q_i \log_2 (Q/q_i) \hbox{\sl I\/} 
2Q+\sum_{0\le i \le n} q_i \log_2 (Q/q_i),
$$
GDE $Q= 2\sum_{0\le i\le n} q_i$.

\proof dLYA POLUCHENIYA NIZHNEJ OCENKI ISPOLXZUEM INDUKCIYU PO~$n$. pRI $n>0$ 
VZVESHENNAYA DLINA VNESHNEGO PUTI NE MENXSHE
$$
Q+\sum_{0\le i <k} q_i\log_2(Q_1/q_i)
+\sum_{k\le i\le n} q_i\log_2((Q-Q_1)/q_i)\ge
\sum_{0\le i\le n} q_i \log_2 (Q/q_i)+f(Q_1)
$$
DLYA NEKOTOROGO $k$, GDE
$$
Q_1=\sum_{0\le i<k} q_i
$$
 I
$$
f(Q_1)=Q+Q_1\log_2Q_1+(Q-Q_1)\log_2(Q-Q_1)-Q\log_2Q.
$$
fUNKCIYA~$f(Q_1)$ NEOTRICATELXNA I PRINIMAET NAIMENXSHEE ZNACHENIE~0 
PRI~$Q_1={1\over 2}Q$.

dLYA POLUCHENIYA VERHNEJ GRANICY MOZHEM SCHITATX, CHTO $Q=1$. pUSTX $e_0$,~\dots,
 $e_n$---CELYE CHISLA, TAKIE, CHTO $2^{-e_i}\le q_i < 2^{1-e_i}$,
%% 530
$0\le i\le n$. pOSTROIM KODY $C_i$ IZ NULEJ I EDINIC, ISPOLXZUYA $e_i+1$ 
STARSHIH ZNACHASHCHIH CIFR 
DROBI~$\sum_{0\le k<i} q_k+{1\over2}q_i$, VYRAZHENNOJ V DVOICHNOJ SISTEME. v 
UPR.~35 DOKAZYVAETSYA, CHTO $C_i$ NE YAVLYAETSYA NACHALXNOJ PODCEPOCHKOJ~$C_j$ 
PRI $i\ne j$; OTSYUDA SLEDUET, CHTO MY MOZHEM POSTROITX BINARNOE DEREVO 
POISKA, SOOTVETSTVUYUSHCHEE |TIM KODAM. vOZVRASHCHAYASX K PRIMERU RIS.~19, MOZHNO 
POKAZATX, CHTO $C_0=0001$, $C_1=00110$, $C_2=01000001$, $C_3=0100011$ I 
T.~D.; DEREVO NACHINAETSYA S
\picture{rIS. STR. 530}
(iZBYTOCHNYE BITY V KONCE KODOV CHASTO MOZHNO OTBROSITX.) vZVESHENNAYA DLINA 
PUTI BINARNOGO DEREVA, POSTROENNOGO TAKOJ PROCEDUROJ, BUDET
$$
\le \sum_{0\le i\le n} (e_i+1)q_i
<\sum_{0\le i\le n}q_i(2+\log_2(1/q_i)).\endmark
$$

mETODOM, ISPOLXZOVANNYM V PERVOJ CHASTI DOKAZATELXSTVA, LEGKO USTANOVITX, 
CHTO VZVESHENNAYA DLINA PUTI \emph{LYUBOGO} BINARNOGO
DEREVA NE MENXSHE, CHEM  $\sum_{0\le i\le n} q_i\log_2 (Q/q_i)$, NEZAVISIMO 
OT PORYADKA VESOV SLEVA NAPRAVO. (eTOT FUNDAMENTALXNYJ 
REZULXTAT PRINADLEZHIT kLODU shENNONU.) tAKIM OBRAZOM, SOHRANENIE PORYADKA 
VESOV SLEVA NAPRAVO UVELICHIVAET CENU OPTIMALXNOGO DEREVA NE BOLXSHE, CHEM NA 
CENU DVUH DOPOLNITELXNYH UROVNEJ, T.~E. NA UDVOENNUYU SUMMU VESOV.

\section iSTORIYA I BIBLIOGRAFIYA. rASSMOTRENNYE METODY POISKA PO DEREVU 
BYLI OTKRYTY NEZAVISIMO NESKOLXKIMI ISSLEDOVATELYAMI V NACHALE 50-H GODOV. v 
NEOPUBLIKOVANNOM DOKUMENTE, DATIROVANNOM AVGUSTOM 1952~G., a.~i.~dUMI 
OPISAL VSTAVKI V DEREVO V PROSTEJSHEM VIDE:

%%531
\noindent
"pUSTX IMEETSYA BARABAN, NA KOTOROM ZAPISANO $2^n$~|LEMENTOV, I KAZHDYJ IZ 
NIH IMEET BINARNYJ ADRES. pRIDERZHIVAJTESX TAKOJ PROGRAMMY:
\enumerate
\li pROCHITAJTE PERVYJ |LEMENT I POMESTITE EGO PO ADRESU $2^{n-1}$, T.~E. V 
SEREDINU MASSIVA PAMYATI.

\li pROCHITAJTE SLEDUYUSHCHIJ |LEMENT. sRAVNITE EGO S PERVYM.

\li eSLI ON BOLXSHE, POMESTITE EGO PO ADRESU~$2^{n-1}+2^{n-2}$.\goodbreak
eSLI ZHE ON MENXSHE, POMESTITE PO ADRESU~$2^{n-2}$.~\dots"
\enumend

dRUGAYA RANNYAYA FORMA VSTAVKI V DEREVO BYLA VVEDENA d.~dZH.~uILEROM; ON, V 
SUSHCHNOSTI, DOPUSKAL MNOGOPUTEVYE RAZVETVLENIYA, PODOBNYE TEM, KOTORYE 
BUDUT OBSUZHDATXSYA V P. 6.2.4;
METOD VSTAVKI V BINARNOE DEREVO BYL TAKZHE NEZAVISIMO PRIDUMAN 
k.~m.~bERNESOM-lI [{\sl Comp. J.,\/} {\bf 2} (1959), 5].

pERVYE OPUBLIKOVANNYE OPISANIYA VSTAVKI V DEREVO PRINADLEZHAT p.~f.~uINDLI 
[{\sl Comp. J.,\/} {\bf 3} (1960), 84--88], e.~d.~bUTU I~e.~kOLINU [{\sl 
Information and Control,\/} {\bf 3} (1960), 327--334] I~t.~n.~hIBBARDU 
[{\sl JACM,\/} {\bf 9} (1962), 13--28]. vEROYATNO, VSE AVTORY RAZVIVALI 
|TOT METOD NEZAVISIMO, I IH DOKAZATELXSTVA FORMULY~(6) SREDNEGO CHISLA 
SRAVNENIJ NESKOLXKO OTLICHAYUTSYA DRUG OT DRUGA. v POSLEDUYUSHCHIH RABOTAH ONI 
PRODOLZHALI ISSLEDOVATX RAZLICHNYE ASPEKTY |TOGO ALGORITMA: uINDLI PODROBNO 
RAZOBRAL SORTIROVKU VSTAVKOJ V DEREVO, bUT I~kOLIN OBSUZHDALI 
|FFEKT PREDVARITELXNOGO POSTROENIYA IZ PERVYH $2^n-1$~|LEMENTOV IDEALXNO 
SBALANSIROVANNOGO DEREVA (SM. UPR.~4), hIBBARD PREDLOZHIL IDEYU UDALENIYA I 
VYYAVIL SVYAZX MEZHDU ANALIZOM VSTAVKI V DEREVO I ANALIZOM BYSTROJ SORTIROVKI.

iDEYA \emph{OPTIMALXNYH} BINARNYH DEREVXEV POISKA BYLA VPERVYE RAZVITA DLYA 
CHASTNOGO SLUCHAYA $p_1=\cdots=p_n=0$ V SVYAZI S BINARNYM KODIROVANIEM BUKV. 
v OCHENX INTERESNOJ STATXE e.~gILBERTA I~e.~mURA 
[{\sl Bell System Tech.~J.,\/} {\bf 38} (1959), 933--968] 
OBSUZHDALASX |TA PROBLEMA I EE SVYAZX S 
DRUGIMI ZADACHAMI KODIROVANIYA. gILBERT I~mUR OTMETILI, CHTO OPTIMALXNOE 
DEREVO MOZHNO POSTROITX ZA $O(n^3)$~SHAGOV, ISPOLXZUYA METOD, PODOBNYJ 
ALGORITMU~K, NO BEZ SOOTNOSHENIYA~(17). k.~e.~aJVERSON [A Programming 
Language (Wiley, 1962), 142--144] NEZAVISIMO RASSMOTREL 
\emph{DRUGOJ} SLUCHAJ, KOGDA VSE~$q$ RAVNY~0. oN PREDPOLOZHIL, CHTO DEREVO 
BUDET OPTIMALXNYM, ESLI KORENX VYBRATX TAK, CHTOBY KAK MOZHNO LUCHSHE URAVNYATX 
VEROYATNOSTI LEVOGO I PRAVOGO PODDEREVXEV; MY VIDELI, CHTO, K SOZHALENIYU, |TA 
IDEYA NE RABOTAET. d.~e.~kNUT [{\sl Acta Informatica,\/} {\bf 1} (1971), 
14--25, 270] VPOSLEDSTVII RASSMOTREL SLUCHAJ LYUBYH VESOV $p$ I~$q$ I 
DOKAZAL, CHTO ALGORITM MOZHET BYTX SVEDEN K $O(n^2)$~SHAGAM; ON TAKZHE PRIVEL 
PRIMER PRIMENENIYA RASSMOTRENNYH METODOV K KOMPILYATORU, GDE KLYUCHAMI V 
DEREVE YAVLYAYUTSYA "REZERVIROVANNYE SLOVA" ALGOLOPODOBNOGO YAZYKA. 
t.~ch.~hU NESKOLXKO LET ZANIMALSYA SVOIM SOBSTVENNYM ALGORITMOM DLYA
%%532
SLUCHAYA~$p=0$; IZ-ZA SLOZHNOSTI ZADACHI BYLO TRUDNO NAJTI 
STROGOE DOKAZATELXSTVO SPRAVEDLIVOSTI |TOGO ALGORITMA, NO V KONCE KONCOV V 
1969~G. t.~ch.~hU I~e.~k.~tAKER SPRAVILISX S |TIM. 
[{\sl SIAM J.  Applied Math.,\/} {\bf 21} (1971), 514--532.]

\excercises
\ex[15] aLGORITM~T BYL SFORMULIROVAN LISHX DLYA NEPUSTYH DEREVXEV. kAKIE 
NUZHNO VNESTI IZMENENIYA, CHTOBY ON OBRABATYVAL I PUSTYE DEREVXYA?

\ex[20] iZMENITE ALGORITM~T TAK, CHTOBY ON RABOTAL S \emph{PRAVOPROSHITYMI} 
DEREVXYAMI (SR.~S P.~2.3.1; PO TAKIM DEREVXYAM PROSHCHE SOVERSHATX SIMMETRICHNYJ OBHOD).

\rex[20] v \S~6.1 MY VIDELI, CHTO NEBOLXSHOE IZMENENIE ALGORITMA 
POSLEDOVATELXNOGO POISKA~6.1S DELAET EGO BYSTREE (ALGORITM~6.1Q). mOZHNO LI 
PODOBNUYU HITROSTX ISPOLXZOVATX DLYA USKORENIYA RABOTY ALGORITMA~T?

\ex[m24] (e.~d.~bUT I~e.~kOLIN.) dANY $N$~KLYUCHEJ V SLUCHAJNOM PORYADKE;
PREDPOLOZHIM, CHTO MY ISPOLXZUEM PERVYE~$2^n-1$ DLYA POSTROENIYA 
IDEALXNO SBALANSIROVANNOGO DEREVA, POMESHCHAYA $2^k$~KLYUCHEJ NA UROVENX~$k$, 
$0\le k<n$. zATEM MY PRIMENYAEM ALGORITM~T DLYA VSTAVKI OSTAVSHIHSYA KLYUCHEJ. 
nAJDITE SREDNEE CHISLO SRAVNENIJ PRI UDACHNOM POISKE. [\emph{uKAZANIE:} 
VIDOIZMENITX~(2).]
 
\rex[m25] nAZVANIYA |CAPRICORN|, |AQUARIUS| I~T.~D. MOZHNO 
UPORYADOCHITX $11!=39916800$~SPOSOBAMI DLYA VSTAVKI V BINARNOE DEREVO POISKA. 
(a) sKOLXKO TAKIH PERESTANOVOK PRIVEDUT K RIS.~10? (b)~sKOLXKO 
PERESTANOVOK PRIVEDUT K VYROZHDENNOMU DEREVU, T.~E. VO VSEH UZLAH |LLINK| 
ILI~|RLINK| BUDUT RAVNYATXSYA~$\NULL$?

\ex[m26] oBOZNACHIM CHEREZ $P_{nk}$ KOLICHESTVO PERESTANOVOK $a_1$ 
$a_2$~\dots $a_n$ MNOZHESTVA $\{\, 1, 2,~\dots, n\,\}$, TAKIH, CHTO, ESLI 
ALGORITM~T ISPOLXZUETSYA DLYA POSLEDOVATELXNOJ VSTAVKI $a_1$, $a_2$,~\dots, 
$a_n$ V PERVONACHALXNO PUSTOE DEREVO, ROVNO $k$~SRAVNENIJ PROIZVODITSYA PRI 
VSTAVKE~$a_n$. [v |TOJ ZADACHE MY PRENEBREZHEM SRAVNENIYAMI, PROIZVODIMYMI 
PRI VSTAVKE $a_1$,~\dots, $a_{n-1}$. v PRINYATYH V TEKSTE OBOZNACHENIYAH 
$C'_{n-1}=\left(\sum kP_{nk}\right)/n!$, TAK KAK |TO ESTX SREDNEE CHISLO 
SRAVNENIJ, KOTORYE PROIZVODYATSYA PRI NEUDACHNOM POISKE PO DEREVU IZ 
$n-1$~|LEMENTOV.]

{\medskip\narrower
\item{a)}~dOKAZHITE, CHTO $P_{n+1,k}=2P_{n,k-1}+(n-1)P_{n,k}$. 
[\emph{uKAZANIE:} POSMOTRITE, OKAZYVAETSYA LI $a_{n+1}$ NIZHE~$a_n$.]

\item{b)}~nAJDITE PROSTUYU FORMULU DLYA PROIZVODYASHCHEJ 
FUNKCII~$G_n(z)=\sum_k P_{nk}z^k$ I ISPOLXZUJTE EE DLYA VYRAZHENIYA $P_{nk}$ 
CHEREZ CHISLA sTIRLINGA.

\item{c)}~chEMU RAVNA \emph{DISPERSIYA}~$C'_{n-1}$?

\medskip}

\ex[M30] (s.~r.~aRORA I~u.~t.~d|NT.) kAKOE SREDNEE CHISLO 
SRAVNENII POTREBUETSYA DLYA OTYSKANIYA $m\hbox{-GO}$ PO VELICHINE |LEMENTA 
POSLE VSTAVKI V PERVONACHALXNO PUSTOE DEREVO $n$~|LEMENTOV V SLUCHAJNOM PORYADKE?

\ex[m38] pUSTX $p(n, k)$ ESTX VEROYATNOSTX TOGO, CHTO POLNAYA DLINA 
VNUTRENNEGO PUTI DEREVA, POSTROENNOGO ALGORITMOM~T IZ $n$ SLUCHAJNO 
UPORYADOCHENNYH KLYUCHEJ, RAVNA~$k$ (DLINA VNUTRENNEGO PUTI DEREVA RAVNA CHISLU 
SRAVNENIJ, PROIZVODIMYH PRI SORTIROVKE VSTAVKOJ V DEREVO PO MERE EGO POSTROENIYA).
(A)~nAJDITE REKURRENTNOE SOOTNOSHENIE, OPREDELYAYUSHCHEE SOOTVETSTVUYUSHCHUYU 
PROIZVODYASHCHUYU FUNKCIYU. (b)~vYCHISLITE DISPERSIYU |TOGO RASPREDELENIYA. 
[zDESX MOGUT BYTX POLEZNY NEKOTORYE UPRAZHNENIYA P.~1.2.7!]

\ex[41] mY DOKAZALI, CHTO POISK S VSTAVKOJ PO DEREVU TREBUET LISHX OKOLO 
$2\ln N$~SRAVNENIJ, ESLI KLYUCHI VSTAVLYAYUTSYA V SLUCHAJNOM PORYADKE; NO V 
DEJSTVITELXNOSTI PORYADOK MOZHET NE BYTX SLUCHAJNYM. iSSLEDUJTE |MPIRICHESKI,
NASKOLXKO HOROSHO VSTAVKA V DEREVO OBSLUZHIVAET TABLICY 
SIMVOLOV KOMPILYATORA I/ILI ZAGRUZCHIKA. dADUT LI IDENTIFIKATORY TIPICHNOJ 
BOLXSHOJ PROGRAMMY DOSTATOCHNO HOROSHO SBALANSIROVANNOE BINARNOE DEREVO POISKA?

%%533

\rex[22] pREDPOLOZHIM, CHTO PROGRAMMISTA NE INTERESUET PORYADOK KLYUCHEJ V 
BINARNOM DEREVE POISKA, NO MOZHNO OZHIDATX, CHTO VVOD BUDET PROIZVODITXSYA NE 
V SLUCHAJNOM PORYADKE. oBSUDITE METODY, POZVOLYAYUSHCHIE TEM NE MENEE 
ISPOLXZOVATX POISK PO DEREVU, IMITIRUYA SLUCHAJNYJ PORYADOK VVODA.

\ex[20] nAJDITE MAKSIMALXNOE KOLICHESTVO PRISVAIVANII $|S|\asg 
|LLINK|(|R|)$ (V SHAGE~D3) PRI UDALENII UZLA IZ DEREVA RAZMERA~$N$.

\ex[m22] kAK CHASTO (V SREDNEM) V SHAGE~D1 PROISHODIT PEREDACHA UPRAVLENIYA 
NA~D4, ESLI UDALYAETSYA SLUCHAJNYJ UZEL IZ SLUCHAJNOGO DEREVA RAZMERA~$N$? 
(sM. DOKAZATELXSTVO TEOREMY~H.)

\rex[m23] bUDET LI SLUCHAJNYM DEREVO, POLUCHENNOE V REZULXTATE 
UDALENIYA KORNYA SLUCHAJNOGO DEREVA POSREDSTVOM ALGORITMA~D?

\rex[22] dOKAZHITE, CHTO DLINA PUTI DEREVA, POROZHDENNOGO ALGORITMOM D
S DOPOLNITELXNYM SHAGOM D$1{1\over2}$, NE BOLXSHE, CHEM DLINA PUTI DEREVA, 
POROZHDENNOGO NEMODIFICIROVANNYM ALGORITMOM. nAJDITE SLUCHAJ, KOGDA 
SHAG~D$1{1\over2}$ DEJSTVITELXNO UMENXSHAET DLINU PUTI.

\ex[m47] nAJDITE TOCHNOE IZMENENIE SREDNEGO VREMENI RABOTY ALGORITMA~t 
POSLE DLINNOJ POSLEDOVATELXNOSTI VSTAVOK I UDALENIJ, ESLI K ALGORITMU~D  
DOBAVLYAETSYA NOVYJ SHAG~D$1{1\over2}$.

\rex[25] yaVLYAETSYA LI OPERACIYA UDALENIYA \emph{KOMMUTATIVNOJ}? tO ESTX 
POLUCHITSYA LI ODNO I TO ZHE DEREVO, ESLI S POMOSHCHXYU ALGORITMA~D UDALITX 
UZLY $X$ I~$Y$; ESLI UDALITX $Y$ I~$X$?

\ex[25] pOKAZHITE, CHTO ESLI V ALGORITME~D POLNOSTXYU ZAMENITX PRAVOE NA 
LEVOE I OBRATNO, TO EGO LEGKO PRISPOSOBITX DLYA UDALENIYA DANNOGO UZLA IZ 
\emph{PRAVOPROSHITOGO} DEREVA S SOHRANENIEM NEOBHODIMYH NITEJ. (sR.~S~UPR.~2.)

\ex[M21]. pOKAZHITE, CHTO ZAKON zIPFA PRIVODIT K~(12).

\ex[m23] nAJDITE PRIBLIZHENNO SREDNEE CHISLO SRAVNENIJ~(11), 
ESLI VEROYATNOSTI~$p_k$ UDOVLETVORYAYUT ZAKONU "80-20", OPREDELYAEMOMU 
FORMULAMI (6.1-11) I~(6.1-12).

\ex[m20] pUSTX MY VSTAVLYAEM V DEREVO KLYUCHI V PORYADKE UMENXSHENIYA CHASTOT 
$p_1\ge p_2\ge\ldots\ge p_N$. mOZHET LI |TO DEREVO BYTX SUSHCHESTVENNO 
HUZHE OPTIMALXNOGO DEREVA POISKA?

\ex[m20] pUSTX $p$, $q$ I~$r$---SLUCHAJNO VYBRANNYE VEROYATNOSTI, 
PODCHINYAYUSHCHIESYA USLOVIYU~$p+q+r=1$. chEMU RAVNY VEROYATNOSTI TOGO, CHTO 
DEREVXYA I, II, III, IV ILI~V (SM.~(13)) YAVLYAYUTSYA OPTIMALXNYMI? 
(rASSMOTRITE OTNOSHENIYA PLOSHCHADEJ SOOTVETSTVUYUSHCHIH OBLASTEJ NA RIS.~14.)

\ex[m20] dOKAZHITE, CHTO PRI VYPOLNENII SHAGA~K4 ALGORITMA~K 
$r[i,j-1]\le r[i+1,j]$.

\rex[M23] nAJDITE (NE PRIBEGAYA K POMOSHCHI evm) OPTIMALXNOE BINARNOE DEREVO 
POISKA, ESLI $n=40$, $p_1=5$, $p_2=p_3=\cdots=p_{40}=1$, 
$q_0=q_1=\cdots=q_{40}=0$.

\ex[m25] pUSTX $p_n=q_n=0$, A VSE OSTALXNYE VESA NEOTRICATELXNY. dOKAZHITE, 
CHTO OPTIMALXNOE DEREVO DLYA ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) 
MOZHNO POLUCHITX ZAMENOJ
\picture{rIS. STR. 533}
V LYUBOM OPTIMALXNOM DLYA ($p_1$,~\dots, $p_{n-1}$; $q_0$,~\dots, $q_{n-1}$) 
DEREVE.

\ex[m20] pUSTX $A$ I~$B$---NEPUSTYE MNOZHESTVA DEJSTVITELXNYH CHISEL. pO 
OPREDELENIYU $A\le B$, ESLI VYPOLNYAETSYA SLEDUYUSHCHEE SVOJSTVO: ($a\in A$, 
$b\in B$, $b<a$) VLECHET ($a\in B$ I~$b\in A$). (a)~dOKAZHITE, CHTO |TO 
OTNOSHENIE NEPUSTYH MNOZHESTV TRANZITIVNO. (b)~dOKAZHITE ILI OPROVERGNITE, 
CHTO $A\le B$ TOGDA I TOLXKO TOGDA, KOGDA $A\le A \cup B \le B$.

%%534

\ex[m22] pUSTX ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$)---NEOTRICATELXNYE 
VESA I~$p_n+q_n=x$. dOKAZHITE, CHTO PRI $x$, IZMENYAYUSHCHEMSYA OT 0 DO~$\infty$, 
I PRI POSTOYANNYH ($p_1$,~\dots, $p_{n-1}$; $q_0$,~\dots, $q_{n-1}$) 
CENA~$c (0, n)$ OPTIMALXNOGO BINARNOGO DEREVA POISKA YAVLYAETSYA "VYPUKLOJ 
NEPRERYVNOJ KUSOCHNO LINEJNOJ" FUNKCIEJ~$x$ S CELYMI UGLOVYMI 
KO|FFICIENTAMI. dRUGIMI SLOVAMI, DOKAZHITE, CHTO SUSHCHESTVUYUT POLOZHITELXNYE 
CELYE CHISLA $l_0>l_1>\ldots>l_m$ I DEJSTVITELXNYE 
POSTOYANNYE$0=x_0<x_1<\ldots<x_m<x_{m+1}=\infty$ I~$y_0<y_1<\ldots<y_m$, 
TAKIE, CHTO $c (0, n)=y_h+l_hx$ PRI $x_h\le x\le x_{h+1}$, $0\le h\le m$.

\ex[M33] cELXYU DANNOGO UPRAZHNENIYA YAVLYAETSYA DOKAZATELXSTVO TOGO FAKTA, CHTO 
MNOZHESTVA KORNEJ~$R(i,j)$ OPTIMALXNYH BINARNYH DEREVXEV POISKA 
UDOVLETVORYAYUT PRI $j-i\ge2$ SOOTNOSHENIYU
$$
R(i, j-1)\le R(i,j)\le R(i+1, j),
$$
VVEDENNOMU V UPR.~25 (VESA ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) 
PREDPOLAGAYUTSYA NEOTRICATELXNYMI). dOKAZATELXSTVO PROVODITSYA INDUKCIEJ 
PO~$j-i$; NASHA ZADACHA---DOKAZATX, CHTO 
$R(0, n-1)\le R(0,n)$ PRI $n\ge2$, V PREDPOLOZHENII SPRAVEDLIVOSTI 
SOOTNOSHENIYA PRI $j-i<n$. 
[v SILU SIMMETRII OTSYUDA SLEDUET, CHTO $R(0, n)\le R(1, n)$.]

\medskip
\item{a)}~dOKAZHITE, CHTO $R(0, n-1)\le R(0, n)$, ESLI $p_n=q_n=0$. (sM.~UPR.~24.)

\item{b)}~pUSTX $p_n+q_n=x$. chEREZ $R_h$ OBOZNACHIM MNOZHESTVO~$R(0, n)$ 
OPTIMALXNYH KORNEJ, ESLI $x_h<x<x_{h+1}$, A CHEREZ $R'_h$---MNOZHESTVO 
OPTIMALXNYH KORNEJ PRI $x_h=x$  (SM.~OBOZNACHENIYA UPR.~26). dOKAZHITE, CHTO
$$
R'_0\le R_0\le R'_1\le R_1\le\ldots\le R'_m\le R_m.
$$
oTSYUDA, IZ CHASTI~(a) I UPR.~25 SLEDUET, CHTO $R(0, n-1)\le R(0, n)$ DLYA VSEH~$x$.
\medskip

[\emph{uKAZANIE.} rASSMOTRITE SLUCHAJ~$x=x_h$ I PREDPOLOZHITE, CHTO OBA |TI DEREVA
\picture{rIS. STR. 534}
OPTIMALXNY; $s<r$ I~$l\ge l'$. iSPOLXZUJTE PREDPOLOZHENIE INDUKCII DLYA 
DOKAZATELXSTVA TOGO, CHTO SUSHCHESTVUET OPTIMALXNOE DEREVO S KORNEM~\node{r} 
I UZLOM~\leaf{n} NA UROVNE~$l'$, A TAKZHE OPTIMALXNOE DEREVO S 
KORNEM~\node{s} I UZLOM~\leaf{n} NA UROVNE~$l$.]

\ex[24] iSPOLXZUJTE NEKOTORYJ MAKROYAZYK DLYA NAPISANIYA MAKROOPREDELENIYA 
"OPTIMALXNYJ BINARNYJ POISK", PARAMETROM KOTOROGO YAVLYAETSYA VLOZHENNAYA 
SPECIFIKACIYA OPTIMALXNOGO BINARNOGO DEREVA.

\ex[40] kAKOVO \emph{NAIHUDSHEE} VOZMOZHNOE BINARNOE DEREVO POISKA DLYA 
31~NAIBOLEE UPOTREBITELXNOGO ANGLIJSKOGO SLOVA? (chASTOTY SLOV DANY NA RIS.~12.)

\ex[M41] dOKAZHITE ILI OPROVERGNITE, CHTO CENA OPTIMALXNYH BINARNYH DEREVXEV 
POISKA UDOVLETVORYAET SOOTNOSHENIYU~$c(i,j)+c(i+1, j-1)\ge c(i, j-1)+c(i+1, j)$.

\ex[m20] (a)~eSLI VESA ($q_0$,~\dots, $q_5$) V~(22) RAVNY (2, 3, 1, 1, 3, 
2) SOOTVETSTVENNO, TO KAKOVA VZVESHENNAYA DLINA PUTI DEREVA? (b)~chEMU 
RAVNA VZVESHENNAYA DLINA PUTI OPTIMALXNOGO BINARNOGO DEREVA POISKA, 
IMEYUSHCHEGO TU ZHE POSLEDOVATELXNOSTX VESOV?

\rex[m22] (T.~ch.~hU I~e.~k.~tAKER.) dOKAZHITE, CHTO VESA~$q_i+q_j$ 
NOVYH UZLOV, POLUCHAEMYE NA FAZE~1 ALGORITMA hU-tAKERA, SOZDAYUTSYA V 
NEUBYVAYUSHCHEM PORYADKE.

\ex[m41] chTOBY NAJTI BINARNOE DEREVO POISKA, MINIMIZIRUYUSHCHEE VREMYA RABOTY 
PROGRAMMY~T, NUZHNO MINIMIZIROVATX NE PROSTO CHISLO SRAVNENIJ~$C$, A 
VELICHINU~$7C+C1$. pRIDUMAJTE ALGORITM DLYA NAHOZHDENIYA OPTIMALXNYH BINARNYH
%%535
DEREVXEV POISKA, ESLI LEVYE I PRAVYE VETVI DEREVA IMEYUT 
RAZLICHNYE CENY. [kSTATI, KOGDA CENA PRAVOJ VETVI V DVA RAZA BOLXSHE CENY 
LEVOJ VETVI, A CHASTOTY VSEH UZLOV RAVNY, OPTIMALXNYMI OKAZYVAYUTSYA 
FIBONACHCHIEVY DEREVXYA. sR.~S~L.~e.~Stanfel, 
{\sl JACM,\/} {\bf 17} (1970),  508--517.]

\ex[41] nAPISHITE PROGRAMMU DLYA ALGORITMA hU-tAKERA, 
TREBUYUSHCHUYU $O(n)$~EDINIC PAMYATI I~$O(n\log n)$~EDINIC VREMENI.

\ex[m23] pOKAZHITE, CHTO KODY, POSTROENNYE V DOKAZATELXSTVE TEOREMY~G,
 OBLADAYUT TEM SVOJSTVOM, CHTO $C_i$ NIKOGDA NE NACHINAETSYA S~$C_j$ PRI~$i\ne j$.

\ex[m40] (p.~dZH.~b|JER.) oBOBSHCHIV VERHNYUYU OCENKU V TEOREME~G, DOKAZHITE, 
CHTO CENA LYUBOGO OPTIMALXNOGO BINARNOGO DEREVA POISKA S NEOTRICATELXNYMI 
VESAMI NE PREVOSHODIT POLNOGO 
VESA~$S=\sum_{1le i\le n} p_i+\sum_{0\le i\le n} q_i$, UMNOZHENNOGO NA~$H+2$,
 GDE
$$
H=\sum_{1\le i\le n} (p_i/S)\log_2 (S/p_i)+\sum_{0\le i\le n} (q_i/S)\log_2(S/q_i);
$$
NA SAMOM DELE PROCEDURA VYBORA KORNEJ, MINIMIZIRUYUSHCHAYA MAKSIMALXNYJ 
VES PODDEREVA, POZVOLYAET POSTROITX DEREVO BINARNOGO POISKA, 
UDOVLETVORYAYUSHCHEE |TOJ OCENKE. pOKAZHITE DALEE, CHTO CENA OPTIMALXNOGO 
BINARNOGO DEREVA POISKA NE PREVYSHAET~$S$, UMNOZHENNOGO NA~$H-\log_2(2H/e)$.

\rex[m25] (t.~ch.~hU I~k.~ch.~tANX.) pUSTX $n+1=2^m+k$, GDE~$0\le k\le 2^m$.
sUSHCHESTVUET $\perm{2^m}{k}$ BINARNYH DEREVXEV, V KOTORYH VSE VNESHNIE UZLY 
RASPOLOZHENY NA UROVNYAH $m$ I~$m+1$. pOKAZHITE, CHTO SREDI VSEH |TIH 
DEREVXEV MY NAJDEM ODNO S MINIMALXNOJ VZVESHENNOJ DLINOJ PUTI DLYA 
POSLEDOVATELXNOSTI VESOV ($q_0$,~\dots, $q_n$), ESLI PRIMENIM ALGORITM 
hU-tAKERA K POSLEDOVATELXNOSTI ($M+q_0$,~\dots, $M+q_n$) DLYA DOSTATOCHNO 
BOLXSHOGO~$M$.

\ex[m35] (k.~ch.~tANX.) dOKAZHITE, CHTO SREDI VSEH MNOZHESTV 
VEROYATNOSTEJ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$), 
$p_1+\cdots+p_n+q_0+\cdots+q_n=1$ DEREVO S MINIMALXNOJ CENOJ NAIBOLEE 
DOROGO, ESLI $p_i=0$ DLYA VSEH~$i$, $q_j=0$ DLYA CHETNYH~$j$ 
I~$q_j=1/\floor{n/2}$ DLYA NECHETNYH~$j$. [\emph{uKAZANIE.} dLYA PROIZVOLXNYH 
VEROYATNOSTEJ ($p_1$,~\dots, $p_n$; $q_0$,~\dots, $q_n$) POLOZHIM $c_0=q_0$, 
$c_i=p_i+q_i$ PRI~$1\le i\le n$  I~$S(0)=\emptyset$, A DLYA~$1\le r\le 
\ceil{n/2}$ POLOZHIM $S(r)=S(r-1)\cup\{\,i,j\,\}$, GDE 
$c_i+c_j$~MINIMALXNO PO VSEM~$i<j$, TAKIM, CHTO $i, j\notin S(r-1)$ I~$k\in 
S(r-1)$ PRI VSEH~$i<k<j$. pOSTROIM BINARNOE DEREVO~$T$ S VNESHNIMI UZLAMI 
IZ $S(n+1-2^q)$ NA UROVNE~$q+1$ I S OSTALXNYMI VNESHNIMI UZLAMI NA 
UROVNE~$q$, GDE $q=\floor{\log_2 n}$. dOKAZHITE, CHTO CENA |TOGO 
DEREVA~$\le f(n)$, GDE~$f(n)$---CENA OPTIMALXNOGO DEREVA POISKA DLYA UKAZANNYH 
"NAIHUDSHIH" VEROYATNOSTEJ.]

\ex[m30] (ch.~k.~uON I~shI-kUO~chAN.) rASSMOTRIM SHEMU POSTROENIYA BINARNOGO 
DEREVA POISKA S POMOSHCHXYU ALGORITMA~T, NO S ODNIM OTLICHIEM:
KOGDA CHISLO UZLOV PRINIMAET VID~$2^n-1$, DEREVO PRIVODITSYA K IDEALXNO 
SBALANSIROVANYAOMU ODNORODNOMU VIDU S $2^k$~UZLAMI NA UROVNE~$k$, $0\le 
k<n$. dOKAZHITE, CHTO CHISLO SRAVNENIJ, PROIZVODIMYH VO VREMYA POSTROENIYA 
TAKOGO DEREVA, V SREDNEM SOSTAVLYAET~$M\log_2 N+O(N)$. (nETRUDNO POKAZATX, 
CHTO NA TAKIE REORGANIZACII DEREVA TREBUETSYA  $O(N)$~EDINIC VREMENI.)

\ex[M50] mOZHNO LI OBOBSHCHITX ALGORITM hU-tAKERA DLYA NAHOZHDENIYA OPTVKALXNYH 
DEREVXEV, ESLI KAZHDYJ UZEL IMEET STEPENX NE VYSHE~$t$? nAPRIMER, PRI 
$t=3$ DEREVO, OPTIMALXNOE DLYA POSLEDOVATELXNOSTI VESOV (1, 1, 100, 1, 1),  
VYGLYADIT TAK:
\picture{rIS. STR. 535}

%%536

\bye