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

v PERVUYU OCHEREDX NAS MOZHET INTERESOVATX CHISLO~$B_{nh}$ SBALANSIROVANNYH 
BINARNYH DEREVXEV S $n$~VNUTRENNIMI UZLAMI I VYSOTOJ~$h$. dLYA 
NEBOLXSHIH~$h$ IZ SOOTNOSHENIJ
$$
B_0(z)=1,\quad B_1(z)=z,\quad B_{h+1}(z)=zB_h(z)(B_h(z)+2B_{h-1}(z))
\eqno(5)
$$
NETRUDNO VYCHISLITX PROIZVODYASHCHUYU FUNKCIYU~$B_h(z)=\sum_{n\ge0}B_{nh}z^n$ 
(SM. UPR.~6). tAKIM OBRAZOM,
$$
\matrix{
B_2(z)=& 2z^2+z^3,&\cr
B_3(z)=&& 4z^4+6z^5+4z^6&+z_7\cr
B_4(z)=&&&16z^7&+32z^8+44z^9+\cdots+8z^{14}+z^{15},\cr
}
$$
I VOOBSHCHE $B_h(z)$ PRI $h\ge3$ IMEET VID
$$
2^{F_{h+1}-1}z^{F_{h+2}-1}+2^{F_{h+1}-2}L_{h-1}z^{F_{h+2}}
+\hbox{SLOZHNYE CHLENY}+2^{h-1}z^{2^h-2}+z^{2^h-1},
\eqno(6)
$$
GDE $L_k=F_{k+1}+F_{k-1}$. (eTA FORMULA OBOBSHCHAET TEOREMU~A.) chISLO VSEH 
SBALANSIROVANNYH DEREVXEV VYSOTY~$h$ RAVNO $B_h=B_h(1)$ I UDOVLETVORYAET 
REKURRENTNOMU SOOTNOSHENIYU
$$
B_0=B_1=1,\quad B_{h+1}=B^2_h+2B_hB_{h-1},
\eqno(7)
$$
TAK CHTO $B_2=3$, $B_3=3\cdot5$, $B_4=3^2\cdot5\cdot7$, 
$B_5=3^3\cdot5^2\cdot7\cdot23$; V OBSHCHEM SLUCHAE
$$
B_h=A_0^{F_h}\cdot A_1^{F_h-1}\ldots A_{h-1}^{F_1}\cdot A_h^{F_0},
\eqno(8)
$$
GDE $A_0=1$, $A_1=3$, $A_2=5$, $A_3=7$, $A_4=23$, $A_5=347$, \dots, 
$A_h=A_{h-1}B_{h-2}+2$. pOSLEDOVATELXNOSTI $A_h$ I $B_h$ RASTUT 
OCHENX BYSTRO, KAK "|KSPONENTA |KSPONENTY"; IZ UPR.~7 SLEDUET, 
CHTO SUSHCHESTVUET DEJSTVITELXNOE CHISLO $\theta\approx1.43684$, TAKOE, CHTO
$$
B_h=\floor{\theta^{2^h}}-\floor{\theta^{2^h-1}}+\floor{\theta^{2^h-2}}
-\cdots+(-1)^h\floor{\theta^{2^0}}.
\eqno(9)
$$
eSLI SCHITATX, CHTO VSE $B_h$~DEREVXEV RAVNOVEROYATNY, TO, KAK POKAZYVAET 
UPR.~8, SREDNEE CHISLO UZLOV V DEREVE VYSOTY~$h$ RAVNO
$$
B'_h(1)/B_h(1)\approx (0.70118)\cdot 2^h.
\eqno(10)
$$
eTO OZNACHAET, CHTO VYSOTA SBALANSIROVANNOGO DEREVA S $n$~UZLAMI OBYCHNO 
GORAZDO BLIZHE K~$\log_2 n$, CHEM K~$\log_\phi n$.

k SOZHALENIYU, POLUCHENNYE REZULXTATY NE IMEYUT OTNOSHENIYA K ALGORITMU~A, TAK 
KAK MEHANIZM |TOGO ALGORITMA DELAET NEKOTORYE DEREVXYA GORAZDO BOLEE 
VEROYATNYMI, CHEM DRUGIE. rASSMOTRIM, NAPRIMER, SLUCHAJ~$N=7$, KOGDA 
SUSHCHESTVUET 17~SBALANSIROVANNYH DEREVXEV. kLYUCHI MOZHNO VSTAVLYATX $7!=5040$ 
RAZLICHNYMI SPOSOBAMI, PRI |TOM IDEALXNO SBALANSIROVANNOE "SOVERSHENNOE"
%%546
DEREVO
\picture{RIS. NA STR. 546}
POLUCHAETSYA 2160~RAZ. v PROTIVOPOLOZHNOSTX |TOMU FIBONACHCHIEVO DEREVO
\picture{RIS. NA STR. 546}
VSTRECHAETSYA LISHX 144~RAZA, A POHOZHEE DEREVO
\picture{RIS. NA STR. 546}
VSTRECHAETSYA 216~RAZ. [zAMENIV LEVYE PODDEREVXYA V~(12) I~(13) PROIZVOLXNYMI 
SBALANSIROVANNYMI DEREVXYAMI S CHETYRXMYA UZLAMI I ZATEM ZERKALXNO OTRAZIV 
OTNOSITELXNO VERTIKALXNOJ OSI, POLUCHIM 16~RAZLICHNYH DEREVXEV; VOSEMX 
DEREVXEV, POLUCHENNYH IZ~(12), VSTRECHAYUTSYA PO 144~RAZA, A POLUCHENNYE 
IZ~(13)---PO 216~RAZ. dOVOLXNO STRANNO, CHTO (13) VSTRECHAETSYA CHASHCHE, CHEM (12).]

tOT FAKT, CHTO IDEALXNO SBALANSIROVANNYE DEREVXYA POLUCHAYUTSYA S TAKOJ 
VYSOKOJ VEROYATNOSTXYU---SOVMESTNO S FORMULOJ~(10), SOOTVETSTVUYUSHCHEJ SLUCHAYU 
RAVNYH VEROYATNOSTEJ,---DELAET CHREZVYCHAJNO PRAVDOPODOBNYM SOOTNOSHENIE: 
(SREDNEE CHISLO SRAVNENIJ PRI POISKE PO SBALANSIROVANNOMU DEREVU)%
$\approx\log_2 N+c$, GDE $c$---MALAYA KONSTANTA. dEJSTVITELXNO, |MPIRICHESKIE 
PROVERKI POKAZYVAYUT, CHTO SREDNEE CHISLO SRAVNENIJ, TREBUEMYH DLYA 
VSTAVKI $N\hbox{-GO}$ |LEMENTA, PRI NE SLISHKOM MALYH~$N$ PRIMERNO 
RAVNO~$1.01\log_2 N+0.1$

chTOBY IZUCHITX POVEDENIE ALGORITMA~A NA FAZAH VSTAVKI I BALANSIROVKI, MOZHNO 
KLASSIFICIROVATX VNESHNIE UZLY SBALANSIROVANNOGO DEREVA, KAK POKAZANO NA 
RIS.~23. pUTX, VEDUSHCHIJ IZ VNESHNEGO UZLA VVERH, OPISYVAETSYA 
POSLEDOVATELXNOSTXYU PLYUSOV I MINUSOV ("|+|" DLYA PRAVOJ SSYLKI, "|-|" DLYA 
LEVOJ); MY VYPISYVAEM EE, POKA NE DOSTIGNEM PERVOGO UZLA S NENULEVYM
%% 547
POKAZATELEM SBALANSIROVANNOSTI ILI (ESLI TAKIH UZLOV NET) POKA NE 
DOSTIGNEM KORNYA. zATEM MY PISHEM |A| ILI~|B| V SOOTVETSTVII S TEM, BUDET 
LI NOVOE DEREVO, POLUCHENNOE POSLE VSTAVKI NA DANNOE MESTO VNUTRENNEGO UZLA,
 SBALANSIROVANNYM ILI NET. tAK/PUTX IZ (3) VVERH KODIRUETSYA |++-B|, CHTO 
OZNACHAET "PRAVAYA SSYLKA, PRAVAYA SSYLKA, LEVAYA SSYLKA, 
NESBALANSIROVANO". eSLI KOD OKANCHIVAETSYA NA~|A|, POSLE VSTAVKI NOVOGO UZLA NE
\picture{
rIS. 23.kODY KLASSIFIKACII, OPREDELYAYUSHCHIE POVEDENIE ALGORITMA A POSLE VSTAVKI.
}
TREBUETSYA BALANSIROVKI; KOD, OKANCHIVAYUSHCHIJSYA NA~|++B| ILI~|--B|, 
TREBUET ODNOKRATNOGO POVOROTA, A KOD, OKANCHIVAYUSHCHIJSYA NA~|+-B| ILI~|-+B|, 
TREBUET DVUKRATNOGO POVOROTA. eSLI PUTX SOSTOIT IZ $k$~ZVENXEV, V SHAGE~A6 
KORREKTIRUETSYA ROVNO $k-1$~POKAZATELEJ SBALANSIROVANNOSTI. tAKIM OBRAZOM, 
OPISANNYE POSLEDOVATELXNOSTI DAYUT NEOBHODIMUYU INFORMACIYU O VREMENI RABOTY 
SHAGOV~A6--A10.

eMPIRICHESKIE PROVERKI SO SLUCHAJNYMI CHISLAMI V DIAPAZONE $100\le N\le2000$ 
DALI PRIBLIZHENNYE VEROYATNOSTI DLYA PUTEJ RAZLICHNYH VIDOV (TABL.~1); 
OCHEVIDNO, |TI VEROYATNOSTI BYSTRO PRIBLIZHAYUTSYA K PREDELXNYM ZNACHENIYAM 
PRI~$N\to\infty$. v TABL.~2 DANY SOOTVETSTVUYUSHCHIE TOCHNYE VEROYATNOSTI 
($N=10$; VSE $10!$~PERESTANOVOK SCHITALISX RAVNOVEROYATNYMI.)

iZ TABL.~1 MY VIDIM, CHTO VEROYATNOSTX SOBYTIYA~$k\le 2$ 
RAVNA $0.144+0.153+0.144+0.144=0.585$; TAKIM OBRAZOM, POCHTI V 60\%~SLUCHAEV 
SHAG~A6 TRIVIALEN. sREDNEE CHISLO IZMENENIJ KO|FFICIENTOV 
SBALANSIROVANNOSTI NA |TOM SHAGE (0 ZAMENYAETSYA NA~$\pm1$) PRIMERNO 
RAVNO~$1.8$. sREDNEE CHISLO IZMENENIJ KO|FFICIENTOV SBALANSIROVANNOSTI 
OT~$\pm1$ DO~$0$ V SHAGAH~A7--A10 RAVNO $0.535+2(0.233+0.232)\approx1.5$,  
T.~E.~VSTAVKA ODNOGO  NOVOGO UZLA DOBAVLYAET V SREDNEM 
$0.3$~NESBALANSIROVANNOGO UZLA. eTO SOGLASUETSYA S TEM FAKTOM, CHTO OKOLO 
68\% VSEH UZLOV V SLUCHAJNYH DEREVXYAH, POLUCHENNYH S POMOSHCHXYU ALGORITMA~A, OKAZALISX 
SBALANSIROVANNYMI.

%%548
{
\def\!#1{\overline{\mathstrut #1}}
\htable{tABLICA 1}{pRIBLIZHENNYE VEROYATNOSTI PRI VSTAVKE $N\hbox{-GO}$ |LEMENTA}%
{#&\hfill$#$&&\bskip\hfill$#$\hfill\cr
 & \hbox{dLINA PUTI} &  \hbox{ nET BALANSIROVKI} &  \hbox{ oDNOKRATNYJ POVOROT} & \hbox{dVUKRATNYJ POVOROT}\cr
\noalign{\hrule}
\mathstrut&1 & .144  &  .000  & .000  \cr
    &      2 & .153  &  .144  & .144  \cr
    &      3 & .093  &  .048  & .048  \cr
    &      4 & .058  &  .023  & .023  \cr
    &      5 & .036  &  .010  & .010  \cr
     &    >5 & .051  &  .008  & .007  \cr
ave&\!{2.78}&\!{.535}&\!{.233}&\!{.232}\cr
\noalign{\hrule}
}

\htable{tABLICA 2}{tOCHNYE VEROYATNOSTI PRI VSTAVKE $10\hbox{-GO}$ |LEMENTA}%
{#&\hfill$#$\hfill&&\bskip\hfill$#$\hfill\cr
 &\hbox{dLINA PUTI} &  \hbox{ nET BALANSIROVKI} &  \hbox{ oDNOKRATNYJ POVOROT} & \hbox{dVUKRATNYJ POVOROT}\cr
\noalign{\hrule}
\mathstrut& 1  & 1/7      &  0       & 0     \cr
   &        2  & 6/35     &  1/7     & 1/7   \cr
   &        3  & 4/21     &  2/35    & 2/35  \cr
   &        4  &  0       &  1/21    & 1/21  \cr
ave&\!{247/105}&\!{53/105}&\!{26/105}&\!{26/105}\cr
\noalign{\hrule}
}
}

pRIBLIZHENNAYA MODELX POVEDENIYA ALGORITMA~A BYLA PREDLOZHENA k.~k.~fOSTEROM 
[Proc. ACM Nat. Conf., {\bf 20}, (1965), 192--205]. mODELX |TA NE VPOLNE 
KORREKTNA, NO DOSTATOCHNO BLIZKA K ISTINE, CHTOBY OTRAZITX SUSHCHESTVO DELA. 
pREDPOLOZHIM, CHTO V BOLXSHOM DEREVE, POSTROENNOM S POMOSHCHXYU ALGORITMA~A, 
POKAZATELX SBALANSIROVANNOSTI DANNOGO UZLA S VEROYATNOSTXYU~$p$ RAVEN~0; 
TOGDA |TOT POKAZATELX RAVEN~$+1$ S VEROYATNOSTXYU~${1\over2}(1-p)$ I
S TOJ ZHE VEROYATNOSTXYU RAVEN~$-1$. pREDPOLOZHIM DALEE (BEZ VSYAKIH 
OBOSNOVANIJ), CHTO POKAZATELI SBALANSIROVANNOSTI VSEH UZLOV NEZAVISIMY. 
tOGDA VEROYATNOSTX TOGO, CHTO SHAG~A6 DELAET NENULEVYMI ROVNO 
$(k-1)$~POKAZATELEJ, RAVNA~$p^{k-1}(1-p)$, PO|TOMU SREDNEE ZNACHENIE~$k$ 
ESTX~$1/(1-p)$. vEROYATNOSTX TOGO, CHTO
NUZHNO POVERNUTX CHASTX DEREVA, RAVNA~${1\over2}$. v SREDNEM VSTAVKA NOVOGO 
UZLA DOLZHNA UVELICHITX CHISLO SBALANSIROVANNYH UZLOV VA~$p$; |TO CHISLO V 
DEJSTVITELXNOSTI UVELICHIVAETSYA NA~1 V SHAGE~A5, NA $-p1(1-R)$ V SHAGE~A6, 
NA~${1\over2}$ V SHAGE~A7 I NA~${1\over2}\cdot2$ V SHAGE~A8 ILI A9, TAK CHTO 
MY POLUCHAEM
$$
p=1-p/(1-p)+{1\over2}+1.
$$
%%549
rESHENIE |TOGO URAVNENIYA OTNOSITELXNO~$p$ DAET NEPLOHOE SOGLASIE S TABL.~1:
$$
p={9-\sqrt{41}\over 4}\approx 0.649;\quad 1/(1-p)\approx 2.851.
\eqno(14)
$$

vREMYA RABOTY FAZY POISKA PROGRAMMY~A (STROKI 01--19) RAVNO
$$
10C+C1+2D+2-3S,
\eqno(15)
$$
GDE $C$, $C1$, $S$---TE ZHE SAMYE, CHTO I V PREDYDUSHCHIH ALGORITMAH |TOJ GLAVY,
 a $D$---CHISLO NESBALANSIROVANNYH UZLOV, PROHODIMYH PRI POISKE. 
eMPIRICHESKIE PROVERKI POKAZYVAYUT, CHTO MOZHNO
POLOZHITX $D\approx{1\over3}C$, $C1\approx{1\over2}(C+S)$,
$C+S\approx1.01\log_2N+0.1$, TAK
CHTO SREDNEE VREMYA POISKA PRIMERNO RAVNO $11.3\log_2N+3-13.7S$~EDINIC. 
(eSLI POISK PROIZVODITSYA GORAZDO CHASHCHE VSTAVKI, MY MOGLI BY, RAZUMEETSYA, 
ISPOLXZOVATX OTDELXNUYU, BOLEE BYSTRUYU PROGRAMMU POISKA, TAK KAK NE BYLO BY 
NEOBHODIMOSTI SLEDITX ZA KO|FFICIENTAMI SBALANSIROVANNOSTI; V |TOM SLUCHAE 
SREDNEE VREMYA POISKA SOSTAVILO BY LISHX $(6.6\log_2N+3)u$, A V NAIHUDSHEM 
SLUCHAE VREMYA RABOTY BUDET VSE ZHE MENXSHE, CHEM SREDNEE VREMYA RABOTY 
PROGRAMMY 6.2.2t.)

eSLI POISK NEUDACHEN, VREMYA RABOTY FAZY VSTAVKI V PROGRAMME~a (STROKI 
20--45) RAVNO $8F+26+(0, 1\hbox{ ILI }2)$~EDINIC. dANNYE TABL.~1 
POKAZYVAYUT, CHTO V SREDNEM $F\approx1.8$. fAZA BALANSIROVKI (STROKI 
46--101) TREBUET $16.5$, $8$, $27.5$ ILI $45.5(\pm0.5)$~EDINIC V 
ZAVISIMOSTI OT TOGO, UVELICHIVAEM LI MY POLNUYU VYSOTU, PROSTO LI VYHODIM 
BEZ BALANSIROVKI ILI ZHE PROIZVODIM ODNOKRATNYJ ILI DVUKRATNYJ POVOROT. 
pERVYJ SLUCHAJ POCHTI NE VSTRECHAETSYA, A DRUGIE VSTRECHAYUTSYA S 
PRIBLIZHENNYMI VEROYATNOSTYAMI $0.535$, $0.233$, $0.232$, PO|TOMU SREDNEE 
VREMYA VYPOLNENIYA KOMBINIROVANNOJ VSTAVOCHNO-BALANSIROVOCHNOJ 
CHASTI PROGRAMMY~A SOSTAVLYAET PRIMERNO $63u$.

eTI CHISLA POKAZYVAYUT, CHTO OPERACII NAD SBALANSIROVANNYMI DEREVXYAMI 
DOVOLXNO BYSTRY, HOTYA PROGRAMMA I ZANIMAET MNOGO MESTA V PAMYATI. eSLI 
ISHODNYE DANNYE YAVLYAYUTSYA SLUCHAJNYMI, TO PROSTOJ ALGORITM VSTAVKI V 
DEREVO (P.~6.2.2) PROIZVODIT ODNU VSTAVKU PRIMERNO NA $50u$~BYSTREE, NO 
ISPOLXZOVANIE SBALANSIROVANNYH DEREVXEV GARANTIRUET HOROSHIE REZULXTATY 
DAZHE PRI NESLUCHAJNYH ISHODNYH DANNYH.

oDIN IZ SPOSOBOV SRAVNENIYA PROGRAMMY~A S PROGRAMMOJ 6.2.2t SOSTOIT V 
RASSMOTRENII NAIHUDSHEGO DLYA POSLEDNEJ PROGRAMMY SLUCHAYA. eSLI MY 
ZAINTERESUEMSYA KOLICHESTVOM VREMENI, NEOBHODIMYM DLYA VSTAVKI V VOZRASTAYUSHCHEM 
PORYADKE $N$~KLYUCHEJ V PERVONACHALXNO PUSTOE DEREVO, TO OKAZHETSYA, CHTO 
PROGRAMMA~A MEDLENNEE PRI $N\le 26$ I BYSTREE PRI $N\ge 27$.

%%550
\picture{rIS. 24. pOLYA RANK, ISPOLXZUEMYE PRI POISKE PO POZICII.}

%% 551
\section pREDSTAVLENIE LINEJNOGO SPISKA. vERNEMSYA TEPERX K ZAMECHANIYU, 
SDELANNOMU V NACHALE |TOGO PUNKTA, O TOM, CHTO SBALANSIROVANNYE DEREVXYA 
MOGUT ISPOLXZOVATXSYA DLYA PREDSTAVLENIYA LINEJNYH SPISKOV TAKIM OBRAZOM, CHTO 
MOZHNO BUDET BYSTRO VSTAVLYATX |LEMENTY (PREODOLEVAYA TRUDNOSTX 
POSLEDOVATELXNOGO RASPOLOZHENIYA), SOHRANYAYA PRI |TOM SLUCHAJNYM DOSTUP K 
|LEMENTAM SPISKA (T. E. PREODOLEVAYA TRUDNOSTX SVYAZANNOGO RASPOLOZHENIYA).

iDEYA SOSTOIT V TOM, CHTOBY V KAZHDOM UZLE VVESTI NOVOE POLE S IMENEM |RANK|. 
eTO POLE POKAZYVAET OTNOSITELXNOE POLOZHENIE UZLA V SVOEM PODDEREVE, T.~E. 
ONO RAVNO EDINICE PLYUS CHISLO UZLOV V LEVOM PODDEREVE. nA RIS.~24 
IZOBRAZHENY ZNACHENIYA~|RANK| DLYA BINARNOGO DEREVA NA RIS.~23. mY MOZHEM 
POLNOSTXYU ISKLYUCHITX POLE~|KEY|, ILI PRI ZHELANII MOZHNO IMETX OBA POLYA, 
CHTO POZVOLYAET NAHODITX |LEMENTY KAK PO ZNACHENIYU KLYUCHA, TAK I PO 
OTNOSITELXNOMU POLOZHENIYU V SPISKE.

iSPOLXZOVANIE POLYA~|RANK| POZVOLYAET SVESTI POISK PO POZICII K IZUCHENNYM 
ALGORITMAM.

\alg v.(pOISK PO POZICII V DEREVE.) iMEETSYA LINEJNYJ SPISOK, 
PREDSTAVLENNYJ V VIDE BINARNOGO DEREVA. aLGORITM POZVOLYAET PO DANNOMU~$k$ 
NAJTI $k\hbox{-J}$~|LEMENT SPISKA ($k\hbox{-J}$~UZEL DEREVA V SIMMETRICHNOM 
PORYADKE). pREDPOLAGAETSYA, CHTO, KAK I V ALGORITME~A, IMEETSYA GOLOVNOJ UZEL, 
V KAZHDOM UZLE ESTX POLYA~|LLINK| I~|RL1NK| I, KROME TOGO, POLE~|RANK|, 
OPISANNOE VYSHE.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|M|\asg k$, $|P|\asg |RLINK|(|HEAD|)$.

\st[sRAVNENIE.] eSLI $|P|=\NULL$, ALGORITM KONCHAETSYA NEUDACHNO. (eTO MOZHET 
SLUCHITXSYA, LISHX ESLI $k$ BOLXSHE CHISLA UZLOV V DEREVE ILI $k\le 0$.) v 
PROTIVNOM SLUCHAE, ESLI $|M|<|RANK|(|P|)$, PEREJTI NA \stp{3}; ESLI 
$|M|>|RANK|(|P|)$, PEREJTI NA \stp{4}; A ESLI $|M|=|RANK|(|P|)$, ALGORITM 
KONCHAETSYA UDACHNO (|P| UKAZYVAET NA $k\hbox{-J}$~UZEL).

\st[shAG VLEVO.] uSTANOVITX $|P|\asg|LLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}.

\st[shAG   VPRAVO.] uSTANOVITX   $|M|\asg|M|-|RANK|(|P|)$,  
$|P|\asg|RLINK|(|P|)$ I VERNUTXSYA NA~\stp{2}. 
\algend

v DANNOM ALGORITME INTERES PREDSTAVLYAET LISHX 
OPERACIYA~$|M|\asg |M|-|RANK|(|P|)$ V SHAGE v4. mOZHNO ANALOGICHNYM OBRAZOM 
MODIFICIROVATX PROCEDURU VSTAVKI, HOTYA ESTX SVOI TONKOSTI.

\alg C.(vSTAVKA V SBALANSIROVANNOE DEREVO PO POZICII.) iMEETSYA LINEJNYJ 
SPISOK, PREDSTAVLENNYJ V VIDE SBALANSIROVANNOGO BINARNOGO DEREVA. 
aLGORITM POZVOLYAET PRI DANNOM~$k$ VSTAVITX NOVYJ UZEL (|Q|---UKAZATELX NA 
NEGO) PERED $k\hbox{-M}$~|LEMENTOM SPISKA. eSLI $k=N+1$, NOVYJ UZEL 
POMESHCHAETSYA V KONEC SPISKA.

%%552

kROME TOGO, CHTO VYPOLNENY USLOVIYA ALGORITMA~A, PREDPOLAGAETSYA, CHTO 
KAZHDYJ UZEL SODERZHIT POLE~|RANK|. eTOT ALGORITM OCHENX POHOZH NA 
ALGORITM~A S TEM LISHX OTLICHIEM, CHTO VMESTO POLYA~|KEY| ISPOLXZUETSYA POLE~|RANK|.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|T|\asg|HEAD|$, 
$|S|\asg|P|\asg|RLINK|(|HEAD|)$,  $|U|\asg|M|\asg k$.

\st[sRAVNENIE.] eSLI $|M|\le |RANK|(|P|)$, PEREJTI NA~\stp{3}; V 
PROTIVNOM SLUCHAE PEREJTI NA~\stp{4}.

\st[shAG VLEVO.] uSTANOVITX $|RANK|(|P|)\asg|RANK|(|P|)+1$ (MY BUDEM 
VSTAVLYATX NOVYJ UZEL SLEVA OT~$|P|$). uSTANOVITX $|R|\asg|LLINK|(|P|)$. 
eSLI  $|R|=\NULL$, USTANOVITX $|LLINK|(|P|)\asg|Q|$ I PEREJTI NA~\stp{5}. 
v PROTIVNOM SLUCHAE, ESLI $|B|(|R|)\ne0$, USTANOVITX $|T|\asg|P|$, 
$|S|\asg|R|$ I~$|U|\asg|M|$.  uSTANOVITX $|P|\asg|R|$ I VERNUTXSYA NA~\stp{2}.

\st[shAG VPRAVO.] uSTANOVITX $|M|\asg|M|-|RANK|(|P|)$ 
I~$|R|\asg|RLINK|(|P|)$.  eSLI $|R|=\NULL$, USTANOVITX 
$|RLINK|(|P|)\asg|Q|$ I
PEREJTI NA~\stp{5}. v PROTIVNOM SLUCHAE, ESLI $|B|(|R|)\ne0$, USTANOVITX 
$|T|\asg|P|$, $|S|\asg|R|$, $|U|\asg|M|$. nAKONEC, USTANOVITX $|P|\asg|R|$ 
I VERNUTXSYA NA \stp{2}.

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

\st[kORREKTIROVKA POKAZATELEJ SBALANSIROVANNOSTI.] 
uSTANOVITX~$|M|\asg|U|$. (tEM SAMYM VOSSTANAVLIVAETSYA 
PREDYDUSHCHEE ZNACHENIE |M|, KOGDA |P| BYLO RAVNO~|S|; VSE POLYA~|RANK| 
PODHODYASHCHIM OBRAZOM USTANOVLENY.) eSLI $|M|<|RANK|(|S|)$, 
USTANOVITX~$|R|\asg|P|\asg|LLINK|(|S|)$; V PROTIVNOM SLUCHAE USTANOVITX 
$|R|\asg|P|\asg|RLINK|(|S|)$ I~$|M|\asg|M|-|RANK|(|S|)$. zATEM, POKA~|r| 
NE STANET RAVNYM~|Q|, NUZHNO POVTORYATX SLEDUYUSHCHUYU OPERACIYU: ESLI 
$|M|<|RANK|(|P|)$, USTANOVITX $|B|(|P|)\asg-1$ I $|P|\asg|LLINK|(|P|)$; 
ESLI $|M|>|RANK|(|P|)$, USTANOVITX $|B|(|P|)\asg+1$, 
$|M|\asg|M|-|RANK|(|P|)$ I~$|P|\asg|RLINK|(|P|)$. (eSLI $|M|=|RANK|(|P|)$,
 TO~$|P|=|Q|$, I MOZHNO PEREJTI K SLEDUYUSHCHEMU SHAGU.)

\st[pROVERKA SBALANSIROVANNOSTI.] eSLI $|U|<|RANK|(|S|)$, USTANOVITX 
$a\asg-1$; V PROTIVNOM SLUCHAE $a\asg+1$. tEPERX VOZMOZHNO NESKOLXKO SLUCHAEV:
\itemitem{i)} eSLI $|B|(|S|)=0$, USTANOVITX $|B|(|S|)\asg a$, 
$|LLINK|(|HEAD|)\asg|LLINK|(|HEAD|)+1$; ALGORITM ZAVERSHEN.
\itemitem{ii)} eSLI $|B|(|S|)=-a$, USTANOVITX $|B|(|S|)\asg0$; ALGORITM ZAVERSHEN.
\itemitem{iii)} eSLI $|B|(|S|)=a$, TO PRI $|B|(|R|)=a$ NUZHNO IDTI NA~\stp{8}, A
PRI $|B|(|R|)=-a$---NA~\stp{9}.

\st[oDNOKRATNYJ POVOROT.] uSTANOVITX $|P|\asg|R|$, 
$|LINK|(a, |S|)\asg|LINK|(-a, |R|)$, $|LINK|(-a, |R|)\asg|S|$,   
$|B|(|S|)\asg|B|(|R|)\asg0$. eSLI $a= +1$, USTANOVITX 
$|RANK|(|R|)\asg|RANK|(|R|)+|RANK|(|S|)$;
%%553
ESLI $a=-1$, USTANOVITX $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|R|).$ pEREJTI NA~\stp{10}.

\st[dVUKRATNYJ POVOROT.] pRODELATX VSE OPERACII SHAGA~A9 (ALGORITMA ~A).  
zATEM,  ESLI  $a=+1$,   
USTANOVITX $|RANK|(|R|)\asg|RANK|(|R|)-|RANK|(|P|)$, 
$|RANK|(|P|)\asg|RANK|(|P|) +|RANK|(|S|)$, ESLI $a=-1$, USTANOVITX 
$|RANK|(|P|)\asg|RANK|(|P|)+|RANK|(|R|)$, ZATEM $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|P|)$.

\st [pOSLEDNIJ SHTRIH.] eSLI $|S|=|RLINK|(|T|)$, TO 
USTANOVITX $|RLINK|(|T|)\asg|P|$; V PROTIVNOM SLUCHAE $|LLINK|(|T|)\asg|P|$.
\algend

\section {*uDALENIE, KONKATENACIYA I T. D}. vOOBSHCHE GOVORYA, SUSHCHESTVUET MNOGO 
DRUGIH OPERACIJ, KOTORYE NE NARUSHAYUT SBALANSIROVANNOSTI DEREVXEV, NO 
SOOTVETSTVUYUSHCHIE ALGORITMY DOSTATOCHNO DLINNY, TAK CHTO MY NE BUDEM 
RASSMATRIVATX IH PODROBNO. oBSUDIM LISHX OSNOVNYE IDEI, A INTERESUYUSHCHIJSYA 
CHITATELX SMOZHET BEZ BOLXSHOGO TRUDA VOSSTANOVITX NEOBHODIMYE DETALI.

zADACHA UDALENIYA, ESLI POSTAVITX EE KORREKTNO, RESHAETSYA ZA $O(\log N)$~SHAGOV 
[s.~s.~Foster, A Study of AVL Trees, Goodyear Aerospace Corp. 
report GER-12158 (April 1965)]. pREZHDE VSEGO UDALENIE PROIZVOLXNOGO UZLA 
MOZHNO SVESTI K PROSTOMU UDALENIYU UZLA~|P|, V KOTOROM $|LLINK|(|P|)$ 
ILI~$|RLINK|(|P|)$ RAVNY~$\NULL$, KAK V ALGORITME~6.2.2D. eTOT ALGORITM 
SLEDUET MODIFICIROVATX TAKIM OBRAZOM, CHTOBY ON STROIL SPISOK UKAZATELEJ, 
OPREDELYAYUSHCHIH PUTX K UZLU~|P|:
$$
(P_0, a_0), (P_1, a_1), \ldots, (P_l, a_l),
\eqno(16)
$$
GDE   $P_0=|HEAD|$,   $a_0=+1$;  $|LINK| (a_i, P_i)=P_{i+1}$, $0\le i<l$;
$P_l=|P|$, $|LINK|(a_l, P_l)=\NULL$. eLEMENTY |TOGO SPISKA V 
PROCESSE SPUSKA PO DEREVU MOZHNO ZANOSITX VO VSPOMOGATELXNYJ STEK. pROCESS 
UDALENIYA UZLA~|P| 
USTANAVLIVAET~$|LINK|(a_{l-1}, P_{l-1})\asg|LINK|(-a_l, P_l)$, I NUZHNO 
OTKORREKTIROVATX POKAZATELX SBALANSIROVANNOSTI UZLA~$P_{l-1}$. pREDPOLOZHIM,
 CHTO MY DOLZHNY OTKORREKTIROVATX POKAZATELX SBALANSIROVANNOSTI UZLA~$P_k$, 
POTOMU CHTO UMENXSHILASX VYSOTA PODDEREVA~$a_k$; MOZHNO ISPOLXZOVATX 
SLEDUYUSHCHUYU PROCEDURU KORREKTIROVKI: ESLI~$k=0$, PRISVOITX 
$|LLINK|(|HEAD|)\asg|LLINK|(|HEAD|)-1$; ALGORITM ZAVERSHEN, TAK KAK 
UMENXSHILASX VYSOTA VSEGO DEREVA. v PROTIVNOM SLUCHAE NUZHNO RASSMOTRETX 
POKAZATELX SBALANSIROVANNOSTI~$|B|(P_k)$, VOZMOZHNY TRI VARIANTA:

\item{i)} $|B|(P_k)=a_k$. uSTANOVITX $|B|(P_k)\asg0$, UMENXSHITX $k$ NA 1 I
POVTORITX KORREKTIROVKU DLYA NOVOGO ZNACHENIYA~$k$.

\item{ii)} $|B|(P_k) = 0$. uSTANOVITX $|B|(P_k)\asg-a_k$; ALGORITM ZAVERSHEN.

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

bALANSIROVKA TREBUETSYA V OBSHCHEM V TEH ZHE SLUCHAYAH, CHTO I V ALGORITME 
VSTAVKI; POLEZNO SNOVA VERNUTXSYA K (1), GDE V ROLI
%%554
$A$ VYSTUPAET~$P_k$, A V ROLI~$B$---UZEL~$|LINK|(-a_k, P_k)$, 
PRINADLEZHASHCHIJ 
VETVI, \emph{PROTIVOPOLOZHNOJ} TOJ, IZ KOTOROJ PROIZVODITSYA UDALENIE. eSTX 
TOLXKO ODNO OTLICHIE: UZEL~$B$ MOZHET BYTX SBALANSIROVANNYM, I TOGDA POLUCHIM 
NOVYJ SLUCHAJ~3, ANALOGICHNYJ SLUCHAYU~1, NO $\beta$~BUDET IMET VYSOTU~$h+1$. 
v SLUCHAYAH~1 I~2 BALANSIROVKA, PODOBNO~(2), OZNACHAET, CHTO MY UMENXSHAEM 
VYSOTU, USTANAVLIVAYA V KACHESTVE KORNYA~(2) UZEL~$|LINK|(a_{k-1}, P_{k-1})$, 
UMENXSHAYA~$k$ NA~1 I VOZOBNOVLYAYA PROCEDURU KORREKTIROVKI DLYA NOVOGO 
ZNACHENIYA~$k$. v SLUCHAE~3 MY PROIZVODIM ODNOKRATNYJ POVOROT, CHTO NE 
IZMENYAET OBSHCHEJ VYSOTY, NO DELAET POKAZATELI SBALANSIROVANNOSTI KAK~$A$, 
TAK I~$B$ NENULEVYMI; PO|TOMU POSLE ZANESENIYA V~$|LINK|(a_{k-1}, P_{k-1})$ 
ADRESA UZLA~$B$ ALGORITM ZAVERSHAETSYA.

vAZHNAYA OTLICHITELXNAYA CHERTA UDALENIYA SOSTOIT V TOM, CHTO ONO MOZHET 
POTREBOVATX DO $\log N$~POVOROTOV, V TO VREMYA KAK DLYA VSTAVKI VSEGDA 
HVATAET ODNOGO. pRICHINA |TOGO STANET YASNA, ESLI POPYTATXSYA UDALITX SAMYJ 
PRAVYJ UZEL DEREVA fIBONACHCHI (SM.~RIS.~8, P~6.2.1).

iSPOLXZOVANIE SBALANSIROVANNYH DEREVXEV DLYA PREDSTAVLENIYA LINEJNYH SPISKOV 
DELAET NEOBHODIMYM ALGORITM \emph{KONKATENACII}, KOGDA CELOE DEREVO~$L_2$ 
VSTAVLYAETSYA SPRAVA OT DEREVA~$L_1$ BEZ NARUSHENIYA BALANSA. kLARK e. kR|JN 
PRIDUMAL ORIGINALXNOE RESHENIE |TOJ ZADACHI. pREDPOLOZHIM, CHTO 
"$\mathop{\rm VYSOTA}\nolimits(L_1)\ge \mathop{\rm VYSOTY}\nolimits(L_2)$"; 
DRUGOJ SLUCHAJ OBRABATYVAETSYA ANALOGICHNYM OBRAZOM. 
uDALIM IZ~$L_2$ PERVYJ UZEL, NAZVAV EGO STYKOVOCHNYM UZLOM~$J$, A 
CHEREZ~$L'_2$ OBOZNACHIM NOVOE DEREVO DLYA $L_2\backslash\{J\}$. pOSLE |TOGO 
SPUSKAEMSYA PO PRAVYM VETVYAM DEREVA~$L_1$, POKA NE DOSTIGNEM UZLA~$P$, 
TAKOGO, CHTO
$$
\mathop{\rm VYSOTA}\nolimits(P)-\mathop{\rm VYSOTA}\nolimits(L'_2)=0
\hbox{ ILI } 1;
$$
|TO VSEGDA VOZMOZHNO, TAK KAK PRI PEREHODE NA BOLEE NIZKIJ UROVENX VYSOTA 
IZMENYAETSYA NA~1 ILI~2. tEPERX ZAMENYAEM
\picture{RIS. STR. 554}
I PRISTUPAEM K KORREKTIROVKE~$L_1$, KAK ESLI BY NOVYJ UZEL~$J$ BYL 
VSTAVLEN POSREDSTVOM ALGORITMA~A.

kR|JN RESHIL TAKZHE BOLEE TRUDNUYU OBRATNUYU ZADACHU: \emph{RASSHCHEPITX} SPISOK 
NA DVE CHASTI, KONKATENACIYA KOTORYH DALA BY PERVONACHALXNYJ SPISOK. 
rASSMOTRIM, NAPRIMER, ZADACHU RASSHCHEPLENIYA SPISKA RIS.~20 DLYA POLUCHENIYA DVUH 
SPISKOV, SOSTOYASHCHIH IZ |LEMENTOV $\{\, |A|, \ldots, |I|\,\}$ I 
$\{\, |J|, \ldots, |Q|\,\}$ SOOTVETSTVENNO: TREBUETSYA SUSHCHESTVENNAYA 
PEREKOMPONOVKA PODDEREVXEV. v OBSHCHEM SLUCHAE,
%% 555 
KOGDA MY HOTIM RASSHCHEPITX DEREVO V DANNOM UZLE~$P$, PUTX K~$P$ BUDET POHOZH 
NA PUTX RIS.~25. mY HOTELI BY POSTROITX LEVOE DEREVO, SODERZHASHCHEE 
$\alpha_1$, $P_1$, $\alpha_4$, $P_4$, $\alpha_6$, $P_6$, $\alpha_7$, $P_7$,
 $\alpha$, $P$ V SIMMETRICHNOM PORYADKE, I PRAVOE DEREVO, SODERZHASHCHEE 
$\beta$, $P_8$, $\beta_8$, $P_5$, $\beta_5$, $P_3$, $\beta_3$, $P_2$, 
$\beta_2$. eTO MOZHNO SDELATX POSLEDOVATELXNOSTXYU KONKATENACIJ: SNACHALA 
VSTAVLYAEM~$P$ SPRAVA OT~$\alpha$, ZATEM KONKATENIRUEM~$\beta$ S 
$\beta_8$, ISPOLXZUYA~$P_8$ V KACHESTVE STYKOVOCHNOGO UZLA,
\picture{rIS. 25.  zADACHA RASSHCHEPLENIYA SPISKA.}
KONKATENIRUEM $\alpha_7$ S $\alpha P$ (UZEL~$P_7$ STYKOVOCHNYJ), $\alpha_6$ 
S $\alpha_7P_7\alpha P$ (ISPOLXZUYA~$P_6$), $\beta P_8\beta_8$ S~$\beta_5$ 
(ISPOLXZUYA~$P_5$) I~T.~D.; UZLY $P_8$, $P_7$,~\dots{}, $P_1$, LEZHASHCHIE NA 
PUTI K~$P$, ISPOLXZUYUTSYA KAK STYKOVOCHNYE. kR|JN DOKAZAL, CHTO, ESLI 
ISHODNOE DEREVO SODERZHIT $N$~UZLOV, |TOT ALGORITM RASSHCHEPLENIYA TREBUET LISHX 
$O(\log N)$~EDINIC VREMENI. dELO V TOM, CHTO KONKATENACIYA S 
ISPOLXZOVANIEM DANNOGO UZLA V KACHESTVE STYKOVOCHNOGO ZANIMAET 
$O(k)$~SHAGOV, GDE $k$---RAZNOSTX VYSOT KONKATENIRUEMYH DEREVXEV, 
A ZNACHENIYA~$k$, V SUSHCHNOSTI, OBRAZUYUT GEOMETRICHESKUYU PROGRESSIYU.

vSE |TI ALGORITMY MOGUT RABOTATX KAK S POLYAMI~|KEY|, TAK I S POLYAMI~|RANK| 
(ILI S OBOIMI VMESTE), PRAVDA, V SLUCHAE KONKATENACII VSE KLYUCHI 
DEREVA~$L_2$ DOLZHNY BYTX BOLXSHE KLYUCHEJ~$L_1$. dLYA OBSHCHIH CELEJ CHASTO 
PREDPOCHTITELXNEE ISPOLXZOVATX DEREVXYA S \emph{TREMYA SVYAZYAMI}, V KOTORYH 
NARYADU S POLYAMI~|LLINK| I~|RLINK| ISPOLXZUETSYA POLE~|UP|, UKAZYVAYUSHCHEE NA 
OTCA, I ODNOBITOVYJ PRIZNAK TOGO, YAVLYAETSYA LI DANNYJ UZEL "LEVYM" ILI 
"PRAVYM" SYNOM. pREDSTAVLENIE V VIDE DEREVXEV S TREMYA SVYAZYAMI NEMNOGO
%%556
UPROSHCHAET ALGORITMY I DELAET VOZMOZHNOJ SPECIFIKACIYU UZLA BEZ YAVNOGO 
UKAZANIYA PUTI K NEMU OT KORNYA; MY MOZHEM NAPISATX PODPROGRAMMU UDALENIYA PO 
DANNOMU~|P| UZLA~$|NODE|(|P|)$ ILI UZLA, SLEDUYUSHCHEGO ZA~$|NODE|(|P|)$ V 
SIMMETRICHNOM PORYADKE (T.~E.~UZLA~$|NODE|(|P|\$))$, ILI PODPROGRAMMU 
NAHOZHDENIYA SPISKA, SODERZHASHCHEGO~$|NODE|(|P|)$ I~T.~D. v ALGORITME UDALENIYA 
DLYA DEREVXEV S TREMYA SVYAZYAMI NE NUZHNO STROITX SPISOK~(16), TAK KAK 
SSYLKI~|UP| DAYUT NEOBHODIMUYU INFORMACIYU. rAZUMEETSYA, V |TOM SLUCHAE 
PRI VSTAVKE, UDALENII ILI POVOROTE PRIDETSYA MENYATX NESKOLXKO BOLXSHE SSYLOK.
 iSPOLXZOVANIE DEREVA S TREMYA SVYAZYAMI VMESTO DVUH ANALOGICHNO ISPOLXZOVANIYU 
DVUHSVYAZEVOGO SPISKA VMESTO ODNOSVYAZEVOGO: OTPRAVLYAYASX IZ LYUBOGO MESTA, MY 
MOZHEM IDTI KAK VPERED, TAK I NAZAD. pOLNOE OPISANIE ALGORITMOV RABOTY 
SO SPISKAMI, OSNOVANNYH NA ISPOLXZOVANII SBALANSIROVANNYH DEREVXEV S 
TREMYA SVYAZYAMI, MOZHNO NAJTI V DOKTORSKOJ DISSERTACII kLARKA e. kR|JNA 
(sT|NFORDSKIJ UNIVERSITET, 1972).

\section kONKURENTY SBALANSIROVANNYH DEREVXEV. nEDAVNO BYLO PREDLOZHENO 
NESKOLXKO DRUGIH SPOSOBOV ORGANIZACII BINARNYH DEREVXEV, GARANTIRUYUSHCHIH 
NE BOLEE CHEM LOGARIFMICHESKIJ ROST VREMENI POISKA PRI UVELICHENII CHISLA 
UZLOV. k NASTOYASHCHEMU VREMENI ONI IZUCHENY NE POLNOSTXYU; VOZMOZHNO, CHTO DLYA 
NEKOTORYH evm |TI SPOSOBY OKAZHUTSYA PREDPOCHTITELXNEE SBALANSIROVANNYH DEREVXEV.

iNTERESNOE PONYATIE DEREVA SO \emph{SBALANSIROVANNYM VESOM} IZUCHENO 
yu.~nIVERGELXTOM, e.~rEJNGOLXDOM I ch.~k.~uONOM. vMESTO VYSOTY 
RASSMATRIVAETSYA VES DEREVA---PO OPREDELENIYU RAVNYJ CHISLU EGO VNESHNIH UZLOV---I 
NA VSE UZLY NALAGAETSYA USLOVIE
$$
\sqrt{2}-1<{\hbox{vES LEVOGO PODDEREVA}
\over\hbox{vES PRAVOGO PODDEREVA}}<\sqrt{2}+1.
\eqno(17)
$$
mOZHNO POKAZATX, CHTO BALANS VESA SOHRANYAETSYA POSLE VSTAVKI, ESLI, PODOBNO 
ALGORITMU~A, ISPOLXZOVATX DLYA BALANSIROVKI ODNOKRATNYE I DVUKRATNYE 
POVOROTY (SM.~UPR.~25). oDNAKO VO VREMYA ODNOJ VSTAVKI MOZHET POTREBOVATXSYA 
MNOGO POVOROTOV. eSLI OSLABITX USLOVIE~(17), TO BALANSIROVKA STANET 
BOLEE BYSTROJ, PRAVDA, ZA SCHET UVELICHENIYA VREMENI POISKA.

nA PERVYJ VZGLYAD MOZHET POKAZATXSYA, CHTO DEREVXYA SO SBALANSIROVANNYM VESOM 
TREBUYUT BOLXSHE PAMYATI, CHEM OBYCHNYE SBALANSIROVANNYE, NO NA SAMOM DELE 
INOGDA ONI TREBUYUT NESKOLXKO MENXSHE! eSLI V KAZHDOM UZLE UZHE ESTX 
POLE~|RANK| DLYA PREDSTAVLENIYA LINEJNOGO SPISKA, TO |TO V TOCHNOSTI VES 
LEVOGO PODDEREVA, A SOOTVETSTVUYUSHCHIE PRAVYE VESA MOZHNO ZAPOMINATX 
PRI DVIZHENII VNIZ PO DEREVU. kAZHETSYA, ODNAKO, CHTO NAKLADNYE RASHODY, 
TREBUYUSHCHIESYA DLYA SOHRANENIYA VESOVOGO BALANSA, ZANIMAYUT BOLXSHE VREMENI, 
CHEM ALGORITM~A, I |KONOMIYA DVUH BITOV NA UZEL, VEROYATNO, NE YAVLYAETSYA 
DOSTATOCHNOJ KOMPENSACIEJ.

%%557

dRUGOJ INTERESNYJ PODHOD K SBALANSIROVANNYM DEREVXYAM, NAZVANNYJ 
"(3-2)-DEREVXYA", BYL PREDLOZHEN V 1970~G. dZHONOM hOPKROFTOM [SM. Aho, 
Hopcroft, Ullman, The Design and Analysis of Computer Algorithms 
(Reading, Mass.; Addison-Wesley, 1974), ch.~4]. iDEYA SOSTOIT V TOM, CHTO IZ 
KAZHDOGO UZLA MOGUT VYHODITX LIBO DVE, LIBO TRI VETVI, NO VZAMEN TREBUETSYA, 
CHTOBY VSE VNESHNIE UZLY RASPOLAGALISX NA ODNOM UROVNE. kAZHDYJ VNUTRENNIJ 
UZEL SODERZHIT LIBO ODIN, LIBO DVA KLYUCHA, KAK POKAZANO NA RIS.~26.

vSTAVKU V (3-2)-DEREVO OB�YASNITX NESKOLXKO LEGCHE, CHEM VSTAVKU V 
SBALANSIROVANNOE DEREVO. eSLI MY HOTIM POMESTITX
\picture{rIS. 26.  (3-2)-DEREVO.}
NOVYJ KLYUCH V UZEL, SODERZHASHCHIJ ROVNO ODIN KLYUCH, MY PROSTO VSTAVLYAEM EGO V 
KACHESTVE VTOROGO KLYUCHA. s DRUGOJ STORONY, ESLI UZEL UZHE SODERZHAL DVA KLYUCHA,
 MY DELIM EGO NA DVA ODNOKLYUCHEVYH UZLA I VSTAVLYAEM TRETIJ KLYUCH V 
UZEL-OTEC. eTO V SVOYU OCHEREDX MOZHET VYZVATX DELENIE OTCA. nA RIS.~27 
POKAZAN PROCESS VSTAVKI NOVOGO KLYUCHA V (3-2)-DEREVO RIS.~26.

hOPKROFT ZAMETIL, CHTO OPERACII UDALENIYA, KONKATENACII I RASSHCHEPLENIYA 
PROVODYATSYA NAD (3-2)-DEREVXYAMI DOSTATOCHNO PROSTO I VESXMA POHOZHI NA 
SOOTVETSTVUYUSHCHIE OPERACII SO SBALANSIROVANNYMI DEREVXYAMI.

r.~b|JER [{\sl Proc. ACM-SIGFIDET Workshop\/} (1971), 219--235] PREDLOZHIL 
INTERESNOE PREDSTAVLENIE (3-2)-DEREVXEV S POMOSHCHXYU BINARNYH DEREVXEV. nA 
RIS.~28 POKAZANO TAKOE PREDSTAVLENIE (3-2)-DEREVA RIS.~26; ODIN BIT V 
KAZHDOM UZLE ISPOLXZUETSYA, CHTOBY OTLICHITX "GORIZONTALXNYE" PRAVYE SSYLKI OT 
"VERTIKALXNYH". zAMETIM, CHTO, KAK I V LYUBOM BINARNOM DEREVE POISKA, 
KLYUCHI RASPOLOZHENY SLEVA NAPRAVO V SIMMETRICHNOM PORYADKE. oKAZYVAETSYA, CHTO 
PRI VSTAVKE NOVOGO KLYUCHA V TAKIE DEREVXYA NUZHNO PRODELYVATX TE ZHE OPERACII, 
CHTO I V SLUCHAE SBALANSIROVANNYH DEREVXEV, A IMENNO ODNOKRATNYE I 
DVUKRATNYE POVOROTY, PRAVDA, NUZHNA LISHX ODNA VERSIYA KAZHDOGO POVOROTA 
(NET OTRAZHENIJ OTNOSITELXNO VERTIKALXNOJ OSI, IMEVSHIHSYA V ALGORITMAH~a I~s).

%%558

\picture{rIS. 27.vSTAVKA NOVOGO KLYUCHA "|M|" V (3-2)-DEREVO RIS. 26.}

%%559

\picture{rIS. 28.  (3-2)-DEREVO RIS.~26, PREDSTAVLENNOE KAK BINARNOE 
DEREVO POISKA.}

\excercises
\ex[01] pOCHEMU V (1), SLUCHAJ 2, DLYA VOSSTANOVLENIYA BALANSA NELXZYA PROSTO 
POMENYATX MESTAMI LEVYE PODDEREVXYA UZLOV~$A$ I~$B$?

\ex[16] oB�YASNITX, POCHEMU DEREVO STALO NA ODIN UROVENX VYSHE, ESLI 
MY DOSTIGLI SHAGA~a7 S~$|B|(|S|) = 0$.

\rex[m25] dOKAZHITE, CHTO SBALANSIROVANNOE DEREVO, IMEYUSHCHEE 
$N$~VNUTRENNIH UZLOV, NE MOZHET IMETX BOLEE $(\phi-1)N=0.61803N$~UZLOV S 
NENULEVYMI POKAZATELYAMI SBALANSIROVANNOSTI.

\ex[m22] dOKAZHITE ILI OPROVERGNITE SLEDUYUSHCHEE: SREDI VSEH 
SBALANSIROVANNYH DEREVXEV S $F_{n+1}-1$~VNUTRENNIMI UZLAMI DEREVO 
fIBONACHCHI PORYADKA~$n$ IMEET NAIBOLXSHUYU DLINU VNUTRENNEGO PUTI.

\rex[m25] dOKAZHITE ILI OPROVERGNITE SLEDUYUSHCHEE: ESLI ALGORITM~A 
ISPOLXZUETSYA DLYA VSTAVKI $N$~KLYUCHEJ V PERVONACHALXNO PUSTOE DEREVO I ESLI 
|TI KLYUCHI POSTUPAYUT V VOZRASTAYUSHCHEM PORYADKE, TO POLUCHENNOE DEREVO 
OPTIMALXNO (T.~E. ONO IMEET MINIMALXNUYU DLINU VNUTRENNEGO PUTI SREDI VSEH 
BINARNYH DEREVXEV S $N$~UZLAMI).

\ex[m21] dOKAZHITE, CHTO (5) OPREDELYAET PROIZVODYASHCHUYU FUNKCIYU DLYA 
SBALANSIROVANNYH DEREVXEV VYSOTY~$h$.

\ex[m27] (n.~dZH.~a~sLOAN I~a.~v.~aHO.) dOKAZHITE ZAMECHATELXNUYU 
FORMULU~(9) DLYA CHISLA SBALANSIROVANNYH DEREVXEV VYSOTY~$h$. 
[\emph{uKAZANIE:} POLOZHITX $C_n=B_n+B_{n-1}$ I ISPOLXZOVATX TOT FAKT, 
CHTO $\log(C_{n+1}/C_n^2)$ VESXMA MAL PRI BOLXSHIH~$n$.]

\ex[m24] (l.~a.~hIZDER.) pOKAZHITE, CHTO SUSHCHESTVUET KONSTANTA~$\beta$, TAKAYA,
 CHTO $B'_h(l)/B_h(1)-2^h\beta\to1$ PRI~$h\to\infty$.

\ex[m47] kAKOVO ASIMPTOTICHESKOE CHISLO SBALANSIROVANNYH BINARNYH DEREVXEV 
S $n$~VNUTRENNIMI UZLAMI $\sum_{h>0}B_{nh}$? kAKOVA ASIMPTOTICHESKAYA SREDNYAYA
VYSOTA~$\sum_{h\ge0}hB_{nh}/\sum_{h\ge0}B_{nh}$?

\ex[m48] vERNO LI, CHTO PRI VSTAVKE $N\hbox{-GO}$ |LEMENTA ALGORITM~A 
SOVERSHAET V SREDNEM $\sim\log_2N+c$~SRAVNENIJ ($c$---NEKOTORAYA KONSTANTA)?

\ex[22] vELICHINA~$0.144$ TRIZHDY POYAVLYAETSYA V TABL.~1: ODIN RAZ PRI~$k=l$ I 
DVAZHDY PRI~$k=2$. vELICHINA~$1/7$ VSTRECHAETSYA V TEH ZHE TREH MESTAH TABL.~2. 
yaVLYAETSYA LI SOVPADENIEM, CHTO VO VSEH TREH MESTAH STOYAT ODINAKOVYE VELICHINY,
 ILI NA TO ESTX PRICHINY?

\ex[24] chEMU RAVNO MAKSIMALXNOE VREMYA RABOTY PROGRAMMY~A PRI VSTAVKE 
VOSXMOGO UZLA V SBALANSIROVANNOE DEREVO? kAKOVO MINIMALXNO VOZMOZHNOE 
VREMYA TAKOJ VSTAVKI?

\ex[10] pOCHEMU POLE~|RANK| LUCHSHE ISPOLXZOVATX TAK, KAK V TEKSTE, A 
NE ZAPOMINATX V KACHESTVE KLYUCHA NOMER UZLA ("1" V PERVOM UZLE, "2" VO VTOROM 
I~T.~D)?

%%560

\ex[11] aLGORITMY SBALANSIROVANNOGO DEREVA S POMOSHCHXYU POLYA~|RANK| BYLI 
PRISPOSOBLENY DLYA RABOTY S LINEJNYMI SPISKAMI. mOZHNO LI TAKIM ZHE OBRAZOM 
PRISPOSOBITX ALGORITMY 6.2.2t I 6.2.2D?

\ex[18] (k.~e.~kR|JN.) pREDPOLOZHIM, CHTO UPORYADOCHENNYJ LINEJNYJ SPISOK 
PREDSTAVLEN V VIDE BINARNOGO DEREVA S POLYAMI~|KEY| I~|RANK| V KAZHDOM UZLE. 
pRIDUMAJTE ALGORITM, KOTORYJ RAZYSKIVAET V DEREVE DANNYJ KLYUCH~$K$ 
I OPREDELYAET POLOZHENIE~$K$ V SPISKE, T.~E. NAHODIT CHISLO~$M$, TAKOE, CHTO 
MENXSHE~$K$ LISHX $M-1$~KLYUCHEJ.

\rex[20] nARISUJTE SBALANSIROVANNOE DEREVO, KOTOROE POLUCHILOSX BY 
POSLE UDALENIYA KORNEVOGO UZLA~|F| IZ DEREVA RIS.~20 S POMOSHCHXYU ALGORITMA 
UDALENIYA, PREDLOZHENNOGO V TEKSTE.

\rex[21] nARISUJTE SBALANSIROVANNOE DEREVO, KOTOROE POLUCHILOSX BY 
POSLE KONKATENACII DEREVA fIBONACHCHI (12): (a) SPRAVA I (b) SLEVA OT 
DEREVA RIS.~20, ESLI ISPOLXZOVATX ALGORITM KONKATENACII, PREDLOZHENNYJ V TEKSTE.

\ex[21] nARISUJTE SBALANSIROVANNYE DEREVXYA, KOTORYE POLUCHILISX BY POSLE 
RASSHCHEPLENIYA DEREVA RIS.~20 NA DVE CHASTI: $\{\, |A|, \ldots, |I|\,\}$ 
I~$\{\, |J|, \ldots, |Q|\,\}$---S POMOSHCHXYU PREDLOZHENNOGO V TEKSTE ALGORITMA 
RASSHCHEPLENIYA.

\rex[26] nAJDITE SPOSOB TAK PREOBRAZOVATX DANNOE SBALANSIROVANNOE DEREVO,
 CHTOBY POKAZATELX SBALANSIROVANNOSTI KORNYA STAL OTLICHEN OT~$-1$. 
vASHE PREOBRAZOVANIE DOLZHNO SOHRANYATX SIMMETRICHNYJ PORYADOK UZLOV; ONO 
DOLZHNO POROZHDATX ISKOMOE SBALANSIROVANNOE DEREVO ZA $O(1)$~EDINIC VREMENI 
NEZAVISIMO OT CHISLA EGO UZLOV.

\ex[40] rASSMOTRITE IDEYU ISPOLXZOVANIYA OGRANICHENNOGO KLASSA 
SBALANSIROVANNYH DEREVXEV, VSE UZLY KOTORYH IMEYUT POKAZATELI 
SBALANSIROVANNOSTI~$0$ ILI~$+1$. (tOGDA POLE~|B| MOZHNO SVESTI K ODNOMU 
BITU.) sUSHCHESTVUET LI DLYA TAKIH DEREVXEV PROCEDURA VSTAVKI S RAZUMNOJ 
|FFEKTIVNOSTXYU?

\rex[30] pRIDUMAJTE ALGORITM, KOTORYJ STROIL BY OPTIMALXNYE (V SMYSLE 
UPR. 5) $N\hbox{-UZLOVYE}$ BINARNYE DEREVXYA ZA $O(N)$~SHAGOV. vASH ALGORITM 
DOLZHEN BYTX "DIALOGOVYM" V TOM SMYSLE, CHTO ON POLUCHAET UZLY PO ODNOMU V 
VOZRASTAYUSHCHEM PORYADKE I STROIT CHASTICHNYE DEREVXYA, NE ZNAYA ZARANEE 
OKONCHATELXNOGO ZNACHENIYA~$N$. (tAKOJ ALGORITM MOZHNO BYLO BY ISPOLXZOVATX 
PRI PERESTROJKE PLOHO SBALANSIROVANNOGO DEREVA ILI PRI SLIYANII KLYUCHEJ IZ 
DVUH DEREVXEV V ODNO DEREVO.)

\ex[m20] kAKOV ANALOG TEOREMY~A DLYA DEREVXEV SO SBALANSIROVANNYM VESOM?

\ex[m20] (e.~rEJNGOLXD.) (a)~dOKAZHITE, CHTO SUSHCHESTVUYUT SBALANSIROVANNYE 
DEREVXYA S PROIZVOLXNO MALYM VESOVYM OTNOSHENIEM 
"(VES LEVOGO PODDEREVA)/(VES PRAVOGO PODDEREVA)". 
(b)~dOKAZHITE, CHTO SUSHCHESTVUYUT DEREVXYA SO SBALANSIROVANNYM VESOM, IMEYUSHCHIE 
SKOLX UGODNO BOLXSHUYU RAZNOSTX MEZHDU VYSOTAMI LEVOGO I PRAVOGO PODDEREVXEV.

\ex[m22] (e.~rEJNGOLXD.) dOKAZHITE, CHTO EDINSTVENNYMI BINARNYMI DEREVXYAMI,
 UDOVLETVORYAYUSHCHIMI USILENNOMU USLOVIYU (17)
$$
{1\over2}<{\hbox{vES LEVOGO PODDEREVA}\over\hbox{vES PRAVOGO PODDEREVA}}<2,
$$
YAVLYAYUTSYA IDEALXNO SBALANSIROVANNYE DEREVXYA S $2^n-1$~VNUTRENNIMI 
UZLAMI. (v TAKIH DEREVXYAH LEVYE I PRAVYE VESA V KAZHDOM UZLE RAVNY MEZHDU SOBOJ.)

\ex[27] (yu.~nIVERGELXT, e.~rEJNGOLXD, ch.~uON.) pOKAZHITE, CHTO 
MOZHNO PRIDUMATX ALGORITM VSTAVKI DLYA DEREVXEV SO SBALANSIROVANNYM VESOM, 
SOHRANYAYUSHCHIJ USLOVIE~(17) I PROIZVODYASHCHIJ NE BOLEE $O(\log N)$ POVOROTOV 
NA VSTAVKU.

\ex[40] iSSLEDUJTE SVOJSTVA SBALANSIROVANNYH $t\hbox{-ARNYH}$ DEREVXEV 
DLYA~$t>2$.

\rex[M23] oCENITE MAKSIMALXNOE CHISLO SRAVNENIJ, NEOBHODIMYH DLYA POISKA V 
(3-2)-DEREVE S $N$~VNUTRENNIMI UZLAMI.

\ex[41] dAJTE |FFEKTIVNUYU REALIZACIYU ALGORITMOV (3-2)-DEREVA.

\ex[m47] pROANALIZIRUJTE POVEDENIE (3-2)-DEREVXEV V SREDNEM PRI 
SLUCHAJNYH VSTAVKAH.

%% 561

\ex[26] (e.~mAK-kR|JT.) v \S~2.5 OBSUZHDALISX RAZLICHNYE STRATEGII 
DINAMICHESKOGO RASPREDELENIYA PAMYATI, VKLYUCHAYA "NAIBOLEE PODHODYASHCHIJ" 
(VYBOR OBLASTI NAIMENXSHEGO RAZMERA, UDOVLETVORYAYUSHCHEJ ZAPROSU) I "PERVYJ 
PODHODYASHCHIJ" (VYBOR OBLASTI S NAIMENXSHIM ADRESOM, UDOVLETVORYAYUSHCHEJ 
ZAPROSU). pOKAZHITE, CHTO ESLI SVOBODNOE PROSTRANSTVO SVYAZANO V BINARNOE 
DEREVO, V NEKOTOROM SMYSLE, SBALANSIROVANNOE, TO MOZHNO NAJTI (a)~"NAIBOLEE 
PODHODYASHCHUYU" I (b)~"PERVUYU PODHODYASHCHUYU" OBLASTI V $O(\log n)$~EDINIC 
VREMENI, GDE $n$~ESTX CHISLO SVOBODNYH OBLASTEJ PAMYATI. 
(aLGORITMY~\S~2.5 SOVERSHAYUT PORYADKA $n$~SHAGOV.)

\ex[34] (m.~fREDM|N.) pRIDUMAJTE PREDSTAVLENIE LINEJNYH SPISKOV,
 OBLADAYUSHCHEE TEM SVOJSTVOM, CHTO VSTAVKA NOVOGO |LEMENTA MEZHDU 
POZICIYAMI $m-1$ I~$m$ PRI DANNOM~$m$ TREBUET $O(\log m)$~EDINIC VREMENI.

\subsubchap{sILXNO VETVYASHCHIESYA DEREVXYA } %6.2.4.
iZUCHENNYE NAMI METODY POISKA PO DEREVU BYLI RAZVITY V OSNOVNOM DLYA 
VNUTRENNEGO POISKA, T.~E.~KOGDA ISSLEDUEMAYA TABLICA CELIKOM SODERZHITSYA V 
BYSTROJ VNUTRENNEJ PAMYATI evm. tEPERX ZHE RASSMOTRIM ZADACHU VNESHNEGO POISKA,
 KOGDA NUZHNO VYBRATX INFORMACIYU IZ OCHENX BOLXSHOGO FAJLA, RASPOLOZHENNOGO 
NA VNESHNIH ZAPOMINAYUSHCHIH USTROJSTVAH S PRYAMYM DOSTUPOM, TAKIH, KAK 
MAGNITNYE DISKI ILI BARABANY. (o DISKAH I BARABANAH MOZHNO PROCHITATX V P.~5.4.9.)

\picture{
rIS. 29. bOLXSHOE BINARNOE DEREVO POISKA MOZHNO RAZDELITX  NA "STRANICY".
}

dREVOVIDNYE STRUKTURY DOVOLXNO UDOBNY DLYA VNESHNEGO POISKA (RAZUMEETSYA, 
ESLI ONI PREDSTAVLENY PODHODYASHCHIM OBRAZOM). rASSMOTRIM BOLXSHOE BINARNOE 
DEREVO POISKA (RIS.~29) I PREDPOLOZHIM, CHTO ONO HRANITSYA V DISKOVOM FAJLE.
 (pOLYA |LLINK| I~|RLINK| SODERZHAT TEPERX ADRESA NA DISKE, A NE ADRESA 
VNUTRENNEJ PAMYATI.) eSLI MY PROYAVIM PROSTODUSHIE I BUDEM 
BUKVALXNO SLEDOVATX IZUCHENNYM ALGORITMAM POISKA PO DEREVU, NAM 
PONADOBITSYA OKOLO $\log_2 N$~OBRASHCHENIJ K DISKU. pRI $N$, RAVNOM MILLIONU,
%%562
IH BUDET PRIMERNO 20. nO ESLI RAZDELITX DEREVO NA "STRANICY" PO 7 
UZLOV V KAZHDOJ, KAK POKAZANO PUNKTIROM NA RIS.~29, I ESLI V KAZHDYJ MOMENT 
VREMENI DOSTUPNA LISHX ODNA STRANICA, TO POTREBUETSYA PRIMERNO V TRI RAZA 
MENXSHE OBRASHCHENIJ, T. E. POISK USKORITSYA V TRI RAZA!

gRUPPIROVKA UZLOV V STRANICY, PO SUSHCHESTVU, PREOBRAZUET BINARNYE DEREVXYA V 
OKTARNYE, RAZVETVLYAYUSHCHIESYA V KAZHDOJ STRANICE-UZLE NA 8 PUTEJ. eSLI 
DOPUSTIMY STRANICY BOLXSHIH RAZMEROV, RAZVETVLYAYUSHCHIESYA NA 128 PUTEJ POSLE 
KAZHDOGO OBRASHCHENIYA K DISKU, TO MOZHNO NAHODITX TREBUEMYJ KLYUCH V TABLICE 
IZ MILLIONA |LEMENTOV, PROSMOTREV LISHX TRI STRANICY. mOZHNO POSTOYANNO 
HRANITX KORNEVUYU STRANICU VO VNUTRENNEJ PAMYATI;
TOGDA POTREBUYUTSYA LISHX DVA OBRASHCHENIYA K DISKU, HOTYA V LYUBOJ MOMENT 
VREMENI VO VNUTRENNEJ PAMYATI BUDET NE BOLEE 254 KLYUCHEJ.

rAZUMEETSYA, NE SLEDUET DELATX STRANICY OCHENX BOLXSHIMI, TAK KAK RAZMERY 
VNUTRENNEJ PAMYATI OGRANICHENY I CHTENIE BOLXSHEJ STRANICY ZANIMAET BOLXSHE 
VREMENI. pREDPOLOZHIM, NAPRIMER, CHTO CHTENIE STRANICY, DOPUSKAYUSHCHEJ 
RAZVETVLENIE NA $m$ PUTEJ, ZANIMAET $72.5+0.05m$ MS. vREMYA NA VNUTRENNYUYU 
OBRABOTKU KAZHDOJ STRANICY SOSTAVIT OKOLO $a+b\log m$ MS, GDE $a$ MALO PO 
SRAVNENIYU S $72.5$, TAK CHTO POLNOE VREMYA, TREBUYUSHCHEESYA NA POISK V BOLXSHOJ 
TABLICE, PRIMERNO PROPORCIONALXNO $\log N$, UMNOZHENNOMU NA
$$
(72.5 + 0.05m)/\log m +b.
$$
eTA VELICHINA DOSTIGAET MINIMUMA PRI $m\approx350$; V DEJSTVITELXNOSTI 
|TOT MINIMUM OCHENX "SHIROK". zNACHENIYA, OCHENX BLIZKIE K OPTIMALXNOMU, 
DOSTIGAYUTSYA PRI $m$ OT~200 DO~500. nA PRAKTIKE POLUCHENIE PODOBNOGO 
DIAPAZONA HOROSHIH ZNACHENIJ $m$ ZAVISIT OT HARAKTERISTIK ISPOLXZUEMYH 
VNESHNIH ZAPOMINAYUSHCHIH USTROJSTV I OT DLINY ZAPISEJ V TABLICE.

u. i. lANDAU|R [{\sl IEE Trans.\/}, {\bf EC-12} (1963), 863--871] 
PREDLOZHIL STROITX $m$-ARNYE DEREVXYA SLEDUYUSHCHIM OBRAZOM: RAZMESHCHATX UZLY 
NA UROVNE $l+1$, LISHX ESLI UROVENX $l$ POCHTI ZAPOLNEN. eTA SHEMA TREBUET 
DOVOLXNO SLOZHNOJ SISTEMY POVOROTOV, TAK KAK DLYA VSTAVKI ODNOGO NOVOGO 
|LEMENTA MOZHET POTREBOVATXSYA OSNOVATELXNAYA PERESTROJKA DEREVA; 
lANDAU|R ISHODIL IZ PREDPOLOZHENIYA, CHTO POISK PRIHODITSYA 
PROIZVODITX GORAZDO CHASHCHE VSTAVOK I UDALENIJ.

eSLI FAJL HRANITSYA NA DISKE I YAVLYAETSYA OB�EKTOM SRAVNITELXNO REDKIH 
VSTAVOK I UDALENIJ, TO DLYA EGO PREDSTAVLENIYA PODHODIT TREHUROVNEVOE 
DEREVO, GDE PERVYJ UROVENX RAZVETVLENIYA OPREDELYAET, KAKOJ CILINDR BUDET 
ISPOLXZOVATXSYA, SLEDUYUSHCHIJ UROVENX RAZVETVLENIYA OPREDELYAET 
SOOTVETSTVUYUSHCHUYU DOROZHKU NA |TOM CILINDRE, A TRETIJ UROVENX SODERZHIT SOBSTVENNO
%% 563
ZAPISI. tAKOJ METOD NAZYVAETSYA \dfn{INDEKSNO-POSLEDOVATELXNOJ} 
ORGANIZACIEJ FAJLA [SR. {\sl JACM\/}, {\bf 16} (1969), 569--571].

r. mYUNC I r. uZGALIS [Proc. Princeton Conf. on Inf. Sciences and Systems, 
4 (1970), 345--349] PREDLOZHILI MODIFIKACIYU ALGORITMA 6.2.2t, GDE VSE 
VSTAVKI POROZHDAYUT UZLY, PRINADLEZHASHCHIE TOJ ZHE STRANICE, CHTO I IH 
PREDSHESTVENNIK (ESLI TOLXKO |TO VOZMOZHNO); ESLI STRANICA POLNOSTXYU ZANYATA, 
ZAVODITSYA NOVAYA STRANICA (ESLI TAKOVAYA IMEETSYA). pRI NEOGRANICHENNOM 
KOLICHESTVE STRANIC I SLUCHAJNOM PORYADKE POSTUPAYUSHCHIH DANNYH SREDNEE 
CHISLO OBRASHCHENIJ, K DISKU, KAK MOZHNO POKAZATX, PRIBLIZHENNO 
RAVNO $H_N/(H_m-1)$, CHTO LISHX NEMNOGIM BOLXSHE CHISLA OBRASHCHENIJ V SLUCHAE 
NAILUCHSHEGO VOZMOZHNOGO $m$-ARNOGO DEREVA (SM. UPR.~10).

\section $B\hbox{-DEREVXYA}$. v 1970~G. r. b|JER I e. mAK-kR|JT 
[{\sl Acta Informatica\/}, (1972), 173--189] 
I NEZAVISIMO OT NIH PRIMERNO V TO ZHE VREMYA m. kAUFMAN [NEOPUBLIKOVANO] 
PREDLOZHILI NOVYJ PODHOD K VNESHNEMU POISKU POSREDSTVOM SILXNO VETVYASHCHIHSYA 
DEREVXEV. iH IDEYA OSNOVYVAETSYA NA PODVIZHNOSTI NOVOGO TIPA STRUKTUR DANNYH,
 NAZVANNYH \dfn{$B\hbox{-DEREVXYAMI}$}, I POZVOLYAET PROIZVODITX POISK ILI
IZMENYATX 
BOLXSHOJ FAJL S "GARANTIROVANNOJ" |FFEKTIVNOSTXYU V NAIHUDSHEM SLUCHAE, 
ISPOLXZUYA PRI |TOM SRAVNITELXNO PROSTYE ALGORITMY.

\dfn{$B\hbox{-DEREVOM}$ PORYADKA $m$} NAZYVAETSYA DEREVO, OBLADAYUSHCHEE SLEDUYUSHCHIMI
SVOJSTVAMI:
\medskip
\item{i)} kAZHDYJ UZEL IMEET NE BOLEE $m$ SYNOVEJ.
\item{ii)} kAZHDYJ UZEL, KROME KORNYA I LISTXEV, IMEET NE MENEE
$m/2$ SYNOVEJ.
\item{iii)} kORENX, ESLI ON NE LIST, IMEET NE MENEE 2 SYNOVEJ.
\item{iv)} vSE LISTXYA RASPOLOZHENY NA ODNOM UROVNE I NE SODERZHAT
INFORMACII.
\item{v)} nELISTOVOJ UZEL S $k$ SYNOVXYAMI SODERZHIT $k-1$ KLYUCHEJ.
\medskip
\noindent (kAK I OBYCHNO, LIST---KONCEVOJ UZEL, U NEGO NET PREEMNIKOV. tAK 
KAK LISTXYA NE SODERZHAT INFORMACII, IH MOZHNO RASSMATRIVATX KAK VNESHNIE 
UZLY, KOTORYH V DEJSTVITELXNOSTI NET V DEREVE, TAK CHTO $\NULL$---|TO 
UKAZATELX NA LIST.)

nA RIS.~30 POKAZANO $B\hbox{-DEREVO}$ PORYADKA 7. kAZHDYJ UZEL (KROME KORNYA I 
LISTXEV) IMEET OT~$\lceil 7/2\rceil$ DO~7 PREEMNIKOV I SODERZHIT 3, 4, 5 
ILI 6 KLYUCHEJ. kORNEVOJ UZEL MOZHET SODERZHATX OT~1 DO~6 KLYUCHEJ (V DANNOM 
SLUCHAE 2). vSE LISTXYA NAHODYATSYA NA TRETXEM UROVNE. zAMETXTE, CHTO (a) 
KLYUCHI RASPOLOZHENY V VOZRASTAYUSHCHEM PORYADKE SLEVA NAPRAVO, ESLI 
ISPOLXZOVATX ESTESTVENNOE OBOBSHCHENIE PONYATIYA SIMMETRICHNOGO PORYADKA, I 
(b) KOLICHESTVO LISTXEV ROVNO NA EDINICU BOLXSHE KOLICHESTVA KLYUCHEJ.

B-DEREVXYA PORYADKA 1 I~2, OCHEVIDNO, NEINTERESNY; PO|TOMU MY RASSMOTRIM LISHX 
SLUCHAJ $m\ge 3$. zAMETXTE, CHTO (3-2)-DEREVXYA,
%% 564
\picture{rIS. 30. $B\hbox{-DEREVO}$ PORYADKA 7}
%% 565
OPREDELENNYE V KONCE P.~6.2.3, YAVLYAYUTSYA $B\hbox{-DEREVXYAMI}$ PORYADKA 3;
I OBRATNO, $B\hbox{-DEREVO}$ PORYADKA 3 ESTX (3-2)-DEREVO.

uZEL, SODERZHASHCHIJ $j$ KLYUCHEJ I $j+1$ UKAZATELEJ, MOZHNO PREDSTAVITX V VIDE
\picture{uZEL $B\hbox{-DEREVA}$}
GDE $K_1<K_2<\ldots <K_j$, A $P_i$ UKAZYVAET NA PODDEREVO KLYUCHEJ, BOLXSHIH 
$K_i$ I MENXSHIH $K_{i+1}$. sLEDOVATELXNO, POISK V $B\hbox{-DEREVE}$ ABSOLYUTNO 
PRYAMOLINEEN: POSLE TOGO KAK UZEL (1) RAZMESHCHEN VO VNUTRENNEJ PAMYATI, MY 
ISHCHEM DANNYJ ARGUMENT SREDI KLYUCHEJ $K_1$, $K_2$, \dots, $K_j$. (pRI BOLXSHIH 
$j$, VEROYATNO, PROIZVODITSYA BINARNYJ POISK, A PRI MALYH $j$ NAILUCHSHIM 
BUDET POSLEDOVATELXNYJ POISK.) eSLI POISK UDACHEN, NUZHNYJ KLYUCH NAJDEN; 
ESLI POISK NEUDACHEN V SILU TOGO, CHTO ARGUMENT LEZHIT MEZHDU $K_i$,
 I~$K_{i+1}$, MY "PODKACHIVAEM" (VYZYVAEM V OPERATIVNUYU PAMYATX) UZEL, 
UKAZANNYJ $P_i$, I PRODOLZHAEM PROCESS. uKAZATELX $P_0$ ISPOLXZUETSYA, 
ESLI ARGUMENT MENXSHE $K_1$, a $P_j$ ISPOLXZUETSYA, ESLI ARGUMENT BOLXSHE 
$K_j$. pRI $P_i=\NULL$ POISK NEUDACHEN.

pRIVLEKATELXNOJ CHERTOJ $B\hbox{-DEREVXEV}$ YAVLYAETSYA ISKLYUCHITELXNAYA PROSTOTA, S 
KOTOROJ PROIZVODYATSYA VSTAVKI. rASSMOTRIM, NAPRIMER, RIS.~30; KAZHDYJ LIST 
SOOTVETSTVUET MESTU VOZMOZHNOJ VSTAVKI. eSLI NUZHNO VSTAVITX NOVYJ KLYUCH 
$337$, MY PROSTO MENYAEM UZEL
\picture{vSTAVKA V $B\hbox{-DEREVO}$}
s DRUGOJ STORONY, PRI POPYTKE VSTAVITX NOVYJ KLYUCH $071$ MY OBNARUZHIVAEM, 
CHTO V SOOTVETSTVUYUSHCHEM UZLE UROVNYA 2 NET MESTA---ON UZHE "POLON". eTU 
TRUDNOSTX MOZHNO PREODOLETX, RASSHCHEPIV UZEL NA DVE CHASTI PO TRI KLYUCHA V 
KAZHDOJ I PODNYAV SREDNIJ KLYUCH NA UROVENX 1:
\picture{rASSHCHEPLENIE UZLA PRI VSTAVKE}
%% 566 

vOOBSHCHE, ESLI NUZHNO VSTAVITX NOVYJ |LEMENT V $B\hbox{-DEREVO}$ PORYADKA $m$, VSE 
LISTXYA KOTOROGO RASPOLOZHENY NA UROVNE $l$, NOVYJ KLYUCH VSTAVLYAYUT V 
PODHODYASHCHIJ UZEL UROVNYA $l-1$. eSLI UZEL TEPERX SODERZHIT $m$ KLYUCHEJ, T. E. 
IMEET VID (1) S $j=m$, EGO RASSHCHEPLYAYUT NA DVA UZLA
\picture{rASSHCHEPLENIE UZLA: OBSHCHIJ VID}
I VSTAVLYAYUT KLYUCH $K_{\lceil m/2\rceil}$ V UZEL-OTEC. (tAKIM OBRAZOM, 
UKAZATELX $P$ V NEM ZAMENYAETSYA POSLEDOVATELXNOSTXYU $P$, $K_{\lceil 
m/2\rceil}$, $P'$.) eTA VSTAVKA V SVOYU OCHEREDX MOZHET PRIVESTI K 
RASSHCHEPLENIYU UZLA-OTCA. (sR. S RIS.~27, GDE IZOBRAZHEN SLUCHAJ $m=3$.) 
eSLI NUZHNO RASSHCHEPITX KORNEVOJ UZEL, KOTORYJ NE IMEET OTCA, TO PROSTO 
SOZDAYUT NOVYJ KORENX I POMESHCHAYUT V NEGO EDINSTVENNYJ KLYUCH $K_{\lceil 
m/2\rceil}$, V TAKOM SLUCHAE DEREVO STANOVITSYA NA EDINICU VYSHE.

oPISANNAYA PROCEDURA VSTAVKI SOHRANYAET VSE SVOJSTVA $B\hbox{-DEREVXEV}$; CHTOBY 
OCENITX VSYU KRASOTU IDEI, CHITATELX DOLZHEN VYPOLNITX UPR.~1. zAMETXTE, 
CHTO DEREVO MALO-POMALU RASTET VVERH OT VERHNEJ CHASTI, A NE VNIZ OT NIZHNEJ 
CHASTI, TAK KAK EDINSTVENNAYA PRICHINA, SPOSOBNAYA VYZVATX ROST 
DEREVA,---RASSHCHEPLENIE KORNYA.

uDALENIYA IZ $B\hbox{-DEREVXEV}$ LISHX NEMNOGIM SLOZHNEE VSTAVOK (SM. UPR.~7).

\section gARANTIROVANNAYA |FFEKTIVNOSTX. rASSMOTRIM, K SKOLXKIM UZLAM BUDET 
PROISHODITX OBRASHCHENIE V NAIHUDSHEM SLUCHAE PRI POISKE V $B\hbox{-DEREVE}$ 
PORYADKA $m$. pREDPOLOZHIM, CHTO IMEETSYA $N$ KLYUCHEJ, A NA UROVNE $l$ RASPOLOZHENO 
$N+1$ LISTXEV. tOGDA CHISLO UZLOV NA UROVNYAH 1, 2, 3, \dots NE MENEE 2, 
$2\lceil m/2\rceil$,  $2\lceil m/2\rceil^2$, \dots; SLEDOVATELXNO,
$$
N+1\ge 2\lceil m/2\rceil^{l-1}.
\eqno (5)
$$

iNYMI SLOVAMI,
$$
l\le 1+\log_{\lceil m/2\rceil}\left({N+1\over2}\right);
\eqno(6)
$$
|TO OZNACHAET, NAPRIMER, CHTO PRI $N=1999998$ I $m=199$ IMEEM $l \le  3$. 
tAK KAK PRI POISKE PROISHODIT OBRASHCHENIE SAMOE BOLXSHEE K $l$ UZLAM, |TA 
FORMULA GARANTIRUET MALOE VREMYA RABOTY ALGORITMA.

pRI VSTAVKE NOVOGO KLYUCHA MOZHET PONADOBITXSYA RASSHCHEPITX $l$ UZLOV. oDNAKO 
SREDNEE CHISLO RASSHCHEPLYAEMYH UZLOV MNOGO MENXSHE, TAK KAK OBSHCHEE KOLICHESTVO 
RASSHCHEPLENIJ PRI POSTROENII DEREVA ROVNO NA EDINICU MENXSHE KOLICHESTVA 
UZLOV, KOTOROE MY OBOZNACHIM CHEREZ $p$. v DEREVE NE MENEE 
$1 + (\lceil m/2\rceil-1) (p-1)$
%% 567
KLYUCHEJ; SLEDOVATELXNO,
$$
p\le 1+{N-1\over \ceil{m/2}-1}.
\eqno(7)
$$
eTO OZNACHAET, CHTO SREDNEE CHISLO RASSHCHEPLENIJ, TREBUYUSHCHIHSYA NA ODNU VSTAVKU, 
MENXSHE~$1/(\ceil{m/2}-1)$.

\section uLUCHSHENIYA I IZMENENIYA. pREDLOZHENNYE METODY MOZHNO ULUCHSHITX, ESLI 
SLEGKA IZMENITX OPREDELENIE $B\hbox{-DEREVA}$. pREZHDE.VSEGO ZAMETIM, CHTO 
VSE UKAZATELI V UZLAH NA UROVNE~$l-1$ RAVNY~$\NULL$ I NE RAVNY~$\NULL$ NA 
DRUGIH UROVNYAH. eTO CHASTO PREDSTAVLYAET SOBOJ ZNACHITELXNUYU POTERYU 
PROSTRANSTVA, I MY MOZHEM S|KONOMITX KAK PROSTRANSTVO, TAK I VREMYA, ESLI 
ISKLYUCHIM VSE~$\NULL$ I BUDEM ISPOLXZOVATX DLYA VSEH NIZHNIH UZLOV DRUGOE 
ZNACHENIE~$m$. iSPOLXZOVANIE DVUH RAZLICHNYH~$m$ NE UHUDSHAET ALGORITMA 
VSTAVKI, TAK KAK OBE POLOVINKI RASSHCHEPLENNOGO UZLA OSTAYUTSYA NA TOM ZHE 
UROVNE, CHTO I PERVONACHALXNYJ UZEL. mOZHNO OPREDELITX OBOBSHCHENNOE 
$B\hbox{-DEREVO}$ PORYADKOV~$m_1$, $m_2$, $m_3$,~\dots, POTREBOVAV, CHTOBY 
VSE NEKORNEVYE UZLY NA UROVNE~$l-i$ IMELI OT~$m_i/2$ DO~$m_i$ PREEMNIKOV; 
U PODOBNOGO $B\hbox{-DEREVA}$ SVOE~$m$ DLYA KAZHDOGO UROVNYA, ODNAKO ALGORITM 
VSTAVKI RABOTAET, V SUSHCHNOSTI, PO-PREZHNEMU.

rAZVIVAYA IDEYU PREDYDUSHCHEGO ABZACA, MY MOZHEM ISPOLXZOVATX SOVERSHENNO RAZNYE 
FORMATY UZLOV DLYA RAZNYH UROVNEJ DEREVA, MOZHEM, KROME TOGO, HRANITX V 
LISTXYAH INFORMACIYU. iNOGDA KLYUCHI SOSTAVLYAYUT LISHX NEBOLXSHUYU CHASTX ZAPISEJ, 
I V TAKIH SLUCHAYAH BYLO BY OSHIBKOJ HRANITX ZAPISI CELIKOM V UZLAH, BLIZKIH 
K KORNYU; |TO PRIVELO BY K SLISHKOM MALOMU ZNACHENIYU~$m$ I NE DALO BY 
|FFEKTIVNOGO RAZVETVLENIYA.

uMESTNO PO|TOMU SNOVA RASSMOTRETX RIS.~30, PREDSTAVLYAYA SEBE, CHTO VSE 
ZAPISI FAJLA HRANYATSYA TEPERX V LISTXYAH I CHTO LISHX NESKOLXKO KLYUCHEJ 
PRODUBLIROVANO V OSTALXNYH UZLAH. v TAKOM SLUCHAE SAMYJ LEVYJ LIST SODERZHIT 
VSE ZAPISI S KLYUCHAMI $\le011$;
LIST, OTMECHENNYJ BUKVOJ~$A$, SODERZHIT ZAPISI, KLYUCHI KOTORYH UDOVLETVORYAYUT 
SOOTNOSHENIYU~$439<K\le 449$, I~T.~P. lISTXYA RASTUT I RASSHCHEPLYAYUTSYA, KAK 
DRUGIE UZLY, NO S TOJ SUSHCHESTVENNOJ RAZNICEJ, CHTO ZAPISI NE PEREMESHCHAYUTSYA 
IZ LISTXEV VVERH NA SLEDUYUSHCHIJ UROVENX. tAKIM OBRAZOM, LISTXYA VSEGDA 
ZAPOLNENY NE MENEE CHEM NAPOLOVINU; PRI IH RASSHCHEPLENII V "NELISTOVUYU" 
CHASTX DEREVA POSTUPAET NOVYJ KLYUCH. eSLI KAZHDYJ LIST SVYAZAN SO SVOIM 
PREEMNIKOM OTNOSHENIEM- SIMMETRICHNOGO PORYADKA, MY POLUCHAEM VOZMOZHNOSTX 
|FFEKTIVNO I UDOBNO OBHODITX FAJL KAK POSLEDOVATELXNO, TAK I SLUCHAJNYM OBRAZOM.

nEKOTORYE VYCHISLENIYA s.~p.~gHOSHA I~m.~X.~sENKO 
[{\sl JACM,\/} {\bf 16} (1969), 569--579] NAVODYAT NA MYSLX O TOM, CHTO 
POLEZNO IMETX DOVOLXNO BOLXSHIE LISTXYA; SKAZHEM DO~10 POSLEDOVATELXNYH 
STRANIC V DLINU. zNAYA DIAPAZON KLYUCHEJ DLYA KAZHDOGO LISTA, S POMOSHCHXYU
%%568
LINEJNOJ INTERPOLYACII MOZHNO PREDUGADATX, KAKAYA IZ 10~STRANIC 
SODERZHIT DANNYJ ARGUMENT POISKA. eSLI DOGADKA OKAZHETSYA NEVERNOJ, MY 
POTERYAEM VREMYA, NO |KSPERIMENTY POKAZYVAYUT, CHTO |TA POTERYA MOZHET BYTX 
MENXSHE, CHEM |KONOMIYA VREMENI OT UMENXSHENIYA RAZMERA DEREVA.

t.~X.~mARTIN (NE OPUBLIKOVANO) UKAZAL NA TO, CHTO IDEYA, LEZHASHCHAYA V OSNOVE 
$B\hbox{-DEREVXEV}$, POLEZNA TAKZHE PRI RABOTE S KLYUCHAMI \emph{PEREMENNOJ 
DLINY}. nET NUZHDY ZAKLYUCHATX CHISLO SYNOVEJ KAZHDOGO UZLA V PREDELY~$[m/2, 
m]$; VMESTO |TOGO MOZHNO PROSTO SKAZATX, CHTO KAZHDYJ UZEL DOLZHEN BYTX 
ZAPOLNEN DANNYMI NE MENEE CHEM NAPOLOVINU. mEHANIZM VSTAVKI I RASSHCHEPLENIYA 
RABOTAET PO-PREZHNEMU PREVOSHODNO, HOTYA TOCHNOE CHISLO KLYUCHEJ V KAZHDOM 
UZLE ZAVISIT OT IH DLIN. oDNAKO NELXZYA POZVOLYATX KLYUCHAM BYTX SLISHKOM 
DLINNYMI (UPR.~5).

dRUGOJ VAZHNOJ MODIFIKACIEJ SHEMY $B\hbox{-DEREVA}$ YAVLYAETSYA 
IDEYA "PERELIVANIYA", VVEDENNAYA b|JEROM I~mAK-kR|JTOM. oNA SOSTOIT V TOM, 
CHTOBY ULUCHSHITX ALGORITM VSTAVKI PUTEM UMENXSHENIYA KOLICHESTVA RASSHCHEPLENIJ; 
VMESTO NIH ISPOLXZUYUTSYA LOKALXNYE POVOROTY. pUSTX IMEETSYA PEREPOLNENNYJ 
UZEL, SODERZHASHCHIJ $m$~KLYUCHEJ I $m+1$~UKAZATELEJ; PREZHDE CHEM RASSHCHEPLYATX |TOT 
UZEL, STOIT OBRATITX VNIMANIE NA EGO BRATA SPRAVA, SODERZHASHCHEGO, NAPRIMER, 
$j$~KLYUCHEJ I $j+1$~UKAZATELEJ. v UZLE-OTCE 
SUSHCHESTVUET KLYUCH~$\overline{K}_f$, RAZDELYAYUSHCHIJ KLYUCHI |TIH dVUH BRATXEV; 
SHEMATICHESKI |TO MOZHNO IZOBRAZITX TAK:
\picture{rIS. STR. 568}
pRI $j<m-1$ PROSTOE PERERAZMESHCHENIE DELAET RASSHCHEPLENIE NENUZHNYM: MY 
OSTAVLYAEM $\ceil{(m+j)/2}$~KLYUCHEJ V LEVOM UZLE, ZAMENYAEM V 
UZLE-OTCE~$\overline{K}_f$ NA~$K_{\floor{(m+j)/2}+1}$,. A OSTALXNYE KLYUCHI 
(IH $\ceil{(m+j)/2})$ I SOOTVETSTVUYUSHCHIE UKAZATELI POMESHCHAEM V PRAVYJ UZEL. 
tAKIM OBRAZOM, IZBYTOK "PERELIVAETSYA" V SOSEDNIJ UZEL. eSLI ZHE ON BYL 
POLON ($j=m-1$), MOZHNO RASSHCHEPITX \emph{OBA} UZLA, POLUCHAYA TRI ZAPOLNENNYH 
PRIMERNO NA DVE TRETI UZLA, SODERZHASHCHIH SOOTVETSTVENNO $\floor{(2m-2)/3}$,
 $\floor{(2m-1)/3}$ I $\floor{2m/3}$~KLYUCHEJ:
\picture{rIS. STR. 568}
%%569
eSLI U ISHODNOGO UZLA NET PRAVOGO BRATA, UMESTNO OPISANNYM OBRAZOM 
ISPOLXZOVATX LEVOGO. (eSLI ZHE SUSHCHESTVUYUT OBA BRATA, MOZHNO VOZDERZHATXSYA OT 
RASSHCHEPLENIYA, POKA OBA NE ZAPOLNYATSYA.) nAKONEC, ESLI RASSHCHEPLYAEMYJ UZEL NE 
IMEET BRATXEV, TO |TO OBYAZATELXNO KORENX; MY MOZHEM IZMENITX OPREDELENIE 
$B\hbox{-DEREVA}$, DOPUSTIV, CHTOBY KORENX SODERZHAL DO 
$2\floor{(2m-2)/3}$~KLYUCHEJ, TAK CHTO PRI SVOEM RASSHCHEPLENII ON POROZHDAET DVA 
UZLA, V KAZHDOM IZ KOTORYH $\floor{(2m-2)/3}$~KLYUCHEJ.

pRIVEDENNYE RASSUZHDENIYA POZVOLYAYUT "VYVESTI NOVYJ, LUCHSHIJ VID" DEREVXEV; 
NAZOVEM IH $B^*\hbox{-DEREVXYAMI}$ I OPREDELIM SLEDUYUSHCHIM OBRAZOM:

\medskip
\item{i)} kAZHDYJ UZEL, KROME KORNYA, IMEET NE BOLEE $m$~SYNOVEJ.

\item{ii)} kAZHDYJ UZEL, KROME KORNYA I LISTXEV, IMEET NE MENEE
$(2m-1)/3$~SYNOVEJ.

\item{iii)} kORENX IMEET NE MENEE~2 I NE BOLEE $2\floor{(2m-2)/3}+1$~SYNOVEJ.

\item{iv)} vSE LISTXYA RASPOLOZHENY NA ODNOM UROVNE.

\item{v)} uZLY, NE YAVLYAYUSHCHIESYA LISTXYAMI I IMEYUSHCHIE $k$~SYNOVEJ, SODERZHAT 
$k-1$~KLYUCHEJ.
\medskip

\noindent vAZHNOE IZMENENIE DOSTAVLYAET USLOVIE (ii), UTVERZHDAYUSHCHEE, CHTO MY 
ISPOLXZUEM PO KRAJNEJ MERE DVE TRETI IMEYUSHCHEGOSYA V KAZHDOM UZLE 
PROSTRANSTVA. tEM SAMYM |KONOMITSYA I VREMYA, TAK. KAK V FORMULAH~(6) I~(7) 
VELICHINU "$\ceil{m/2}$" SLEDUET ZAMENITX NA "$\ceil{(2m-1)/3}$".

vOZMOZHNO, CHITATELX OTNESSYA K $B\hbox{-DEREVXYAM}$ SKEPTICHESKI IZ-ZA TOGO, 
CHTO STEPENX KORNYA MOZHET BYTX RAVNA~2. zACHEM TRATITX CELOE OBRASHCHENIE K 
DISKU RADI RAZVETVLENIYA VSEGO LISHX NA DVA PUTI? pROSTAYA SHEMA BUFERIZACII, 
NAZYVAEMAYA "ZAMESHCHENIEM DOLXSHE VSEGO NE ISPOLXZOVAVSHEJSYA STRANICY", 
POMOGAET PREODOLETX |TO NEUDOBSTVO; MY MOZHEM VYDELITX VO VNUTRENNEJ 
PAMYATI NESKOLXKO BUFEROV, TAK CHTO KOMANDA REALXNOGO VVODA BUDET NE NUZHNA, 
ESLI SOOTVETSTVUYUSHCHAYA STRANICA UZHE PRISUTSTVUET V PAMYATI. pRI TAKOJ SHEME 
ALGORITMY POISKA ILI VSTAVKI VYPOLNYAYUT KOMANDY "VIRTUALXNOGO CHTENIYA", 
KOTORYE NA SAMOM DELE TRANSLIRUYUTSYA V INSTRUKCII VVODA, LISHX ESLI NUZHNOJ 
STRANICY NET V PAMYATI; POSLEDUYUSHCHAYA KOMANDA "OSVOBOZHDENIYA" VYPOLNYAETSYA, 
KOGDA INFORMACIYA V BUFERE OBRABOTANA I, VOZMOZHNO, IZMENENA ALGORITMOM. 
eSLI TREBUETSYA DEJSTVITELXNOE CHTENIE, MY VYBIRAEM BUFER, OSVOBOZHDENNYJ 
RANEE DRUGIH, ZAPISYVAEM EGO OBRATNO NA DISK, ESLI ON IZMENILSYA S MOMENTA 
SCHITYVANIYA, ZATEM V VYBRANNYJ BUFER SCHITYVAEM NUZHNUYU STRANICU.

tAK KAK CHISLO UROVNEJ DEREVA OBYCHNO MALO PO SRAVNENIYU. S CHISLOM BUFEROV, 
TAKAYA STRANICHNAYA SISTEMA OBESPECHIVAET POSTOYANNOE PRISUTSTVIE V PAMYATI 
KORNEVOJ STRANICY; TO ZHE SAMOE
%%564
MOZHNO UTVERZHDATX O STRANICAH PERVOGO UROVNYA, ESLI KORENX IMEET DVA ILI TRI 
SYNA. mOZHNO BYLO BY VVESTI SPECIALXNYJ MEHANIZM DLYA OBESPECHENIYA 
POSTOYANNOGO PRISUTSTVIYA OPREDELENNOGO MINIMALXNOGO KOLICHESTVA BLIZKIH K 
KORNYU STRANIC. zAMETXTE, CHTO PREDLOZHENNAYA SHEMA AVTOMATICHESKI 
OBESPECHIVAET PRISUTSTVIE V PAMYATI STRANIC, NEOBHODIMYH DLYA 
VYPOLNENIYA RASSHCHEPLENIJ, KOTORYE MOGUT PONADOBITXSYA PRI VSTAVKAH.

sUDYA PO |KSPERIMENTAM, PROVEDENNYM e.~mAK-kR|JTOM, |TA IDEYA OKAZALASX 
VESXMA UDACHNOJ. nAPRIMER, ON OBNARUZHIL, CHTO S DESYATXYU BUFERNYMI STRANICAMI 
I~$m=121$ PROCESS VSTAVKI V VOZRASTAYUSHCHEM PORYADKE 100000~KLYUCHEJ POTREBOVAL 
LISHX 22~DEJSTVITELXNYE KOMANDY CHTENIYA I 857~DEJSTVITELXNYH KOMAND ZAPISI; 
TAKIM OBRAZOM, BOLXSHAYA CHASTX DEJSTVIJ PROIZVODILASX VO VNUTRENNEJ PAMYATI. 
dALEE, DEREVO SODERZHALO LISHX 835~UZLOV---ROVNO NA~1 BOLXSHE MINIMALXNO 
VOZMOZHNOGO ZNACHENIYA~$\ceil{100000/(m-1)}=834$, T.~E. PAMYATX ISPOLXZOVALASX 
POCHTI NA~100\%. dLYA |TOGO |KSPERIMENTA mAK-kR|JT PRIMENIL 
TEHNIKU PERELIVANIYA, NO S RASSHCHEPLENIEM NA DVE CHASTI, KAK V~(4), A NE NA 
TRI, KAK V~(9). (sM.~UPR.~3.)

v DRUGOM |KSPERIMENTE (TOZHE S 10~BUFERAMI, $m=121$ I TOJ ZHE TEHNIKOJ 
PERELIVANIYA) ON VSTAVIL V PERVONACHALXNO PUSTOE DEREVO 5000~KLYUCHEJ V 
SLUCHAJNOM PORYADKE. pOLUCHILOSX DVUHUROVNEVOE DEREVO S 48~UZLAMI (PAMYATX 
ISPOLXZOVALASX NA~87\%), I POTREBOVALISX 2762~DEJSTVITELXNYE KOMANDY 
SCHITYVANIYA I 2739~DEJSTVITELXNYH KOMAND ZAPISI. pOSLE |TOGO 
1000~SLUCHAJNYH POISKOV 786~RAZ PROIZVODILI DEJSTVITELXNYE, 
SCHITYVANIYA. tOT ZHE |KSPERIMENT \emph{BEZ} METODA PERELIVANIYA POSLE 
2743~DEJSTVITELXNYH SCHITYVANIJ I 2800~DEJSTVITELXNYH ZAPISEJ PRIVEL K 
DVUHUROVNEVOMU DEREVU S 62~UZLAMI (67\% ISPOLXZOVANIYA PAMYATI); 
1000~POSLEDOVATELXNYH SLUCHAJNYH POISKOV POTREBOVALI 836~DEJSTVITELXNYH 
SCHITYVANIJ. eTO POKAZYVAET NE TOLXKO |FFEKTIVNOSTX STRANICHNOJ SHEMY, NO 
TAKZHE POLEZNOSTX LOKALXNOJ OBRABOTKI PEREPOLNENIYA VMESTO NEMEDLENNOGO 
RASSHCHEPLENIYA. eNDRYU yaO DOKAZAL, CHTO SREDNEE CHISLO UZLOV POSLE SLUCHAJNYH 
VSTAVOK BEZ PERELIVANIYA PRI BOLXSHIH~$N$ I~$m$ 
SOSTAVIT $N/(m\ln2)+O(N/m^2)$, TAK CHTO PAMYATX BUDET ISPOLXZOVATXSYA 
PRIMERNO NA~$\ln 2=0.693$ [{\sl Acta Informatica,\/} BUDET OPUBLIKOVANO].

\excercises
\ex[10] kAKOE $B\hbox{-DEREVO}$ PORYADKA~7 POLUCHITSYA POSLE VSTAVKI 
KLYUCHA~613 V DEREVO RIS.~30? (mETOD PERELIVANIYA NE PRIMENYATX.)

\ex[15] vYPOLNITE UPR.~1, ISPOLXZUYA METOD PERELIVANIYA S RASSHCHEPLENIEM NA 
TRI CHASTI, KAK V~(9).

\rex[23] pREDPOLOZHIM, CHTO KLYUCHI 1, 2, 3,~\dots{} V VOZRASTAYUSHCHEM 
PORYADKE VSTAVLYAYUTSYA V PERVONACHALXNO PUSTOE $B\hbox{-DEREVO}$ PORYADKA~101. 
kAKOJ KLYUCH VPERVYE PRIVEDET K POYAVLENIYU LISTXEV NA UROVNE 4: (a) ESLI NE 
ISPOLXZOVATX
%%571
PERELIVANIYA; (b) ESLI ISPOLXZOVATX PERELIVANIYA LISHX S RASSHCHEPLENIEM NA DVE 
CHASTI, KAK V~(4); (c) ESLI ISPOLXZOVATX $B^*\hbox{-DEREVXYA}$ PORYADKA~101 S 
RASSHCHEPLENIEM NA TRI CHASTI, KAK V~(9)?

\ex[21] (b|JER I~mAK-kR|JT.) oB�YASNITE, KAK PROIZVODITX VSTAVKI V 
OBOBSHCHENNOE $B\hbox{-DEREVO}$, CHTOBY VSE UZLY, KROME KORNYA I LISTXEV, 
IMELI NE MENEE ${3\over4}m-{1\over2}$~ SYNOVEJ.

\rex[21] pREDPOLOZHIM, CHTO POD UZLY OTVODITSYA PO 1000~BAJTOV POZICIJ DLYA 
LITER NA VNESHNEJ PAMYATI. eSLI KAZHDAYA SSYLKA ZANIMAET 5~BAJTOV I ESLI KLYUCHI 
IMEYUT PEREMENNUYU, NO KRATNUYU~5 DLINU OT~5 DO~50 BAJTOV, TO 
KAKOE MINIMALXNOE CHISLO BAJTOV MOZHET BYTX ZANYATO V UZLE POSLE EGO 
RASSHCHEPLENIYA V PROCESSE VSTAVKI? (rASSMOTRITE LISHX PROSTUYU PROCEDURU 
RASSHCHEPLENIYA, ANALOGICHNUYU OPISANNOJ V TEKSTE DLYA $B\hbox{-DEREVXEV}$ S 
KLYUCHAMI FIKSIROVANNOJ DLINY, BEZ PERELIVANIYA.)

\ex[22] mOZHNO LI ISPOLXZOVATX IDEYU $B\hbox{-DEREVA}$ DLYA VYBORKI 
|LEMENTOV LINEJNOGO SPISKA PO POZICII, A NE PO ZNACHENIYU KLYUCHA? (sR. S 
ALGORITMOM~6.2.3v.)

\ex[23] pRIDUMAJTE ALGORITM UDALENIYA DLYA $B\hbox{-DEREVXEV}$.

\ex[28] pRIDUMAJTE ALGORITM KONKATENACII $B\hbox{-DEREVXEV}$ (SR. S~P.~6.2.3).

\ex[30] oBDUMAJTE, KAK BOLXSHOJ FAJL, ORGANIZOVANNYJ V VIDE 
$B\hbox{-DEREVA}$, MOZHNO ISPOLXZOVATX DLYA DOSTUPA I IZMENENIYA SO STORONY 
BOLXSHOGO CHISLA ODNOVREMENNO RABOTAYUSHCHIH POLXZOVATELEJ TAK, CHTOBY 
POLXZOVATELI RAZLICHNYH STRANIC PRAKTICHESKI NE SOZDAVALI POMEH DRUG DRUGU.

{\catcode`\!=\active\def!{\hfill}
\ex[vm37] rASSMOTRIM OBOBSHCHENIE VSTAVKI V DEREVO, PREDLOZHENNOE mYUNCEM 
I~uZGALISOM, KOGDA KAZHDAYA STRANICA MOZHET SODERZHATX $M$~KLYUCHEJ. pUSTX MY 
VSTAVILI V TAKOE DEREVO $N$~SLUCHAJNYH |LEMENTOV; TEPERX ONO IMEET 
$N+1$~VNESHNIH UZLOV. oBOZNACHIM CHEREZ~$b^{(j)}_{Nk}$ VEROYATNOSTX TOGO, CHTO 
NEUDACHNYJ POISK TREBUET OBRASHCHENIJ K $k$~STRANICAM I CHTO PREDSHESTVENNIK 
TOGO VNESHNEGO UZLA, GDE KONCHAETSYA POISK, PRINADLEZHIT K STRANICE, 
SODERZHASHCHEJ $j$~KLYUCHEJ. pUSTX 
$B^{(j)}_N(z)=\sum b^{(j)}_{Nk} z^k$---SOOTVETSTVUYUSHCHAYA PROIZVODYASHCHAYA FUNKCIYA. 
dOKAZHITE, CHTO
$$
\displaylines{
B^{(j)}_1(z)=\delta_{j1}z;\cr
B^{(j)}_N(z)={N-j-1\over N+1}B^{(j)}_{N-1}(z)+{j+1\over 
N+1}B^{(j-1)}_{N-1}(z),
\qquad 1<1<M;\cr
B^{(1)}_N(z)={N-2\over N+1}B^{(1)}_{N-1}(z)+{2z\over N+1}B^{(M)}_{N-1}(z);\cr
B^{(M)}_N(z)={N-1\over N+1}B^{(M)}_{N-1}(z)+{M+1\over N+1}B^{(M-1)}_{N-1}(z).\cr
}
$$
nAJDITE ASIMPTOTICHESKOE POVEDENIE 
$C'_N=\sum_{1\le j\le M} {B^{(j)}_N}'(1)$---SREDNEGO CHISLA STRANIC, K KOTORYM 
PROISHODIT OBRASHCHENIE V 
PROCESSE NEUDACHNOGO POISKA. [\emph{uKAZANIE:} VYRAZITX REKURRENTNOE 
SOOTNOSHENIE S POMOSHCHXYU MATRICY
$$
W(z)=\pmatrix{
-3 & !0 & \ldots & !0! & !2z! \cr
!3 & -4 & \ldots & !0! & !0!\cr
!0 & !4 & \ldots & !0! & !0!\cr
!\vdots & !\vdots & & !\vdots! & !\vdots! \cr
!0 & !0 & \ldots & !-M-1! & !0!\cr
!0 & !0 & \ldots & !M+1 & -2! \cr
}
$$
I SOPOSTAVITX $C'_N$ S MNOGOCHLENOM $N\hbox{-J}$~STEPENI V~$W(l)$.]
\par
}
%% 572

\bye
