\input style
\chapnotrue
\chapno=6
\subchno=2
\subsubchno=2
%% 536
\subsubchap{sBALANSIROVANNYE DEREVXYA}
tOLXKO CHTO IZUCHENNYJ NAMI ALGORITM VSTAVKI V DEREVO POROZHDAET HOROSHIE 
DEREVXYA POISKA PRI SLUCHAJNYH ISHODNYH DANNYH, NO VSE ZHE SUSHCHESTVUET 
DOSADNAYA VEROYATNOSTI POLUCHITX VYROZHDENNOE DEREVO. vOZMOZHNO, MY MOGLI BY 
IZOBRESTI ALGORITM, KOTORYJ V LYUBOM SLUCHAE DAET OPTIMALXNOE DEREVO, NO,
 K SOZHALENIYU, |TO DALEKO NE PROSTO. dRUGOJ PODHOD SOSTOIT V HRANENII 
POLNOJ DLINY PUTI I REORGANIZACII DEREVA VSYAKIJ RAZ, KOGDA DLINA EGO PUTI 
PREVYSHAET, SKAZHEM, $5N\log_2N$. nO TOGDA V PROCESSE POSTROENIYA DEREVA 
POTREBOVALOSX BY OKOLO $\sqrt{N/2}$ REORGANIZACIJ.

oCHENX OSTROUMNOE RESHENIE PROBLEMY PODDERZHANIYA HOROSHEGO DEREVA POISKA BYLO 
NAJDENO V 1962~G. DVUMYA SOVETSKIMI MATEMATIKAMI---g.~m.~aDELXSONOM-vELXSKIM 
I e. m. lANDISOM [{\sl dan sssr\/}, {\bf 146} (1962), 263--266]. 
iH METOD TREBUET LISHX DVUH DOPOLNITELXNYH BITOV NA UZEL I 
NIKOGDA NE ISPOLXZUET BOLEE $O(\log N)$ OPERACIJ DLYA POISKA PO DEREVU ILI 
DLYA VSTAVKI |LEMENTA. v DALXNEJSHEM MY UVIDIM, CHTO |TOT PODHOD 
TAKZHE PRIVODIT K OBSHCHEMU METODU PREDSTAVLENIYA PROIZVOLXNYH LINEJNYH 
\emph{SPISKOV} DLINY $N$, PRICHEM KAZHDAYA IZ SLEDUYUSHCHIH OPERACIJ TREBUET LISHX 
$O(\log N)$ EDINIC VREMENI:
\medskip
\item{i)} nAJTI |LEMENT PO DANNOMU KLYUCHU.
\item{ii)} pRI DANNOM $k$ NAJTI $k$-J |LEMENT.
\item{iii)} vSTAVITX V OPREDELENNOM MESTE |LEMENT. 
\item{iv)} uDALITX OPREDELENNYJ |LEMENT.
\medskip
\noindent eSLI DLYA LINEJNYH SPISKOV PRINYATO POSLEDOVATELXNOE RASPOLOZHENIE, 
TO OPERACII (i) I (ii) BUDUT |FFEKTIVNYMI, NO OPERACII (iii) I (iv) 
ZAJMUT PORYADKA $N$ SHAGOV; S DRUGOJ STORONY, PRI ISPOLXZOVANII SVYAZANNOGO 
RASPOLOZHENIYA |FFEKTIVNY OPERACII (iii) I (iv), A (i) I (ii) POTREBUYUT 
PORYADKA $N$ SHAGOV. pREDSTAVLENIE LINEJNYH SPISKOV V VIDE DEREVA POZVOLYAET 
SDELATX \emph{VSE CHETYRE} OPERACII ZA $O(\log N)$ SHAGOV. mOZHNO TAKZHE 
SRAVNITELXNO |FFEKTIVNO PROIZVODITX DRUGIE STANDARTNYE OPERACII; 
NAPRIMER, VOZMOZHNA KONKATENACIYA (SCEPLENIE) SPISKA IZ $m$ |LEMENTOV SO 
SPISKOM IZ $N$ |LEMENTOV ZA $O(\log (m+N))$ SHAGOV.

mETOD, DAYUSHCHIJ VSE |TI PREIMUSHCHESTVA ISPOLXZUET TAK NAZYVAEMYE 
"SBALANSIROVANNYE DEREVXYA". pREDYDUSHCHIJ ABZAC SLUZHIT REKLAMOJ 
SBALANSIROVANNYH DEREVXEV---|TAKOJ PANACEI OT VSEH BED; PO SRAVNENIYU S NIMI 
VSE DRUGIE SPOSOBY PREDSTAVLENIYA DANNYH KAZHUTSYA USTAREVSHIMI. nO NEOBHODIMO 
SBALANSIROVATX NASHE OTNOSHENIE K SBALANSIROVANNYM DEREVXYAM! eSLI 
TREBUYUTSYA NE VSE. CHETYRE RASSMOTRENNYE OPERACII, TO NAS MOZHET UDOVLETVORITX
%% 537
ZNACHITELXNO MENEE UNIVERSALXNYJ, NO PROSHCHE PROGRAMMIRUEMYJ METOD. 
bOLEE TOGO, SBALANSIROVANNYE DEREVXYA HOROSHI LISHX PRI DOSTATOCHNO BOLXSHIH 
$N$; TAK. ESLI ESTX |FFEKTIVNYJ ALGORITM, TREBUYUSHCHIJ $20\log_2N$ EDINIC 
VREMENI, I NE|FFEKTIVNYJ ALGORITM, TREBUYUSHCHIJ $2N$ EDINIC VREMENI, TO PRI 
$N<1024$ SLEDUET ISPOLXZOVATX NE|FFEKTIVNYJ METOD. s DRUGOJ STORONY, $N$ 
NE DOLZHNO BYTX SLISHKOM VELIKO; SBALANSIROVANNYE DEREVXYA PODHODYAT GLAVNYM 
OBRAZOM DLYA HRANENIYA DANNYH VO \emph{VNUTRENNEJ} PAMYATI, A V P.~6.2.4 MY 
IZUCHIM LUCHSHIE METODY DLYA VNESHNIH FAJLOV S PRYAMYM DOSTUPOM. tAK KAK SO 
VREMENEM RAZMERY VNUTRENNEJ PAMYATI STANOVYATSYA VSE BOLXSHE I BOLXSHE, 
SBALANSIROVANNYE DEREVXYA STANOVYATSYA VSE BOLEE VAZHNYMI.

\dfn{vYSOTA} DEREVA OPREDELYAETSYA KAK EGO NAIBOLXSHIJ UROVENX, KAK 
MAKSIMALXNAYA, DLINA PUTI OT KORNYA DO VNESHNEGO UZLA.
\picture{20. sBALANSIROVANNOE BINARNOE DEREVO}
bINARNOE DEREVO NAZYVAETSYA \dfn{SBALANSIROVANNYM}; ESLI VYSOTA LEVOGO 
PODDEREVA KAZHDOGO UZLA OTLICHAETSYA OT VYSOTY PRAVOGO PODDEREVA NE BOLEE CHEM 
NA $\pm1$. nA RIS.~20 POKAZANO SBALANSIROVANNOE DEREVO S 17 VNUTRENNIMI 
UZLAMI I VYSOTOJ 5; \dfn{POKAZATELX SBALANSIROVANNOSTI} PREDSTAVLEN 
VNUTRI KAZHDOGO UZLA ZNAKAMI $+$, $\cdot$ ILI $-$, CHTO OTVECHAET RAZNOSTI 
VYSOT PRAVOGO I LEVOGO PODDEREVXEV, RAVNOJ $+1$, $0$ ILI $-1$ 
SOOTVETSTVENNO. fIBONACHCHIEVO DEREVO NA RIS.~8 (P~6.2.1) YAVLYAETSYA DRUGIM 
SBALANSIROVANNYM BINARNYM DEREVOM VYSOTY 5, IMEYUSHCHIM TOLXKO 12 VNUTRENNIH 
UZLOV; BOLXSHINSTVO POKAZATELEJ SBALANSIROVANNOSTI RAVNO $-1$. 
"zODIAKALXNOE DEREVO" NA RIS.~10 (P.~6.2.2) \emph{NE} SBALANSIROVANO, TAK 
KAK PODDEREVXYA UZLOV |AQUARIUS| I |GEMINI| NE UDOVLETVORYAYUT PRINYATYM 
OGRANICHENIYAM.

eTO OPREDELENIE SBALANSIROVANNOSTI PREDSTAVLYAET SOBOJ KOMPROMISS MEZHDU 
\emph{OPTIMALXNYMI} BINARNYMI DEREVXYAMI (VSE VNESHNIE UZLY KOTORYH 
RASPOLOZHENY NA DVUH SMEZHNYH UROVNYAH)
%% 538
I \emph{PROIZVOLXNYMI} BINARNYMI DEREVXYAMI. pO|TOMU UMESTNO SPROSITX, 
KAK DALEKO MOZHET OTKLONITXSYA OT OPTIMALXNOSTI SBALANSIROVANNOE DEREVO? 
oKAZYVAETSYA, CHTO DLINA EGO POISKOVOGO PUTI .NIKOGDA NE PREVYSIT OPTIMUM 
BOLEE CHEM NA 45\%.

\proclaim tEOREMA a. (g. m. aDELXSON-vELXSKIJ I e. m. lANDIS). 
vYSOTA SBALANSIROVANNOGO DEREVA S $N$ VNUTRENNIMI UZLAMI ZAKLYUCHENA MEZHDU 
$\log_2(N+1)$ I $1.4404 \log_2(N+ 2)-0.328$.

\proof\ bINARNOE DEREVO VYSOTY $h$, OCHEVIDNO, NE MOZHET SODERZHATX BOLEE CHEM 
$2^h$ VNESHNIH UZLOV; PO|TOMU $N+1\le 2^h$, T.E. 
$h\ge \lceil \log_2(N+1)\rceil$.

chTOBY NAJTI MAKSIMALXNOE ZNACHENIE $h$, POSTAVIM VOPROS PO-DRUGOMU: KAKOVO 
MINIMALXNOE CHISLO UZLOV V SBALANSIROVANNOM DEREVE VYSOTY $h$? pUSTX 
$T_h$--- TAKOE DEREVO S NAIMENXSHIM VOZMOZHNYM KOLICHESTVOM UZLOV; TOGDA ODNO 
PODDEREVO KORNYA, NAPRIMER LEVOE, IMEET VYSOTU $h-1$, A DRUGOE---ILI $h-1$, 
ILI $h-2$. v SILU OPREDELENIYA $T_h$ MOZHNO SCHITATX, CHTO LEVOE PODDEREVO 
KORNYA ESTX $T_{h-1}$, A PRAVOE---$T_{h-2}$. tAKIM OBRAZOM, SREDI VSEH 
SBALANSIROVANNYH DEREVXEV VYSOTY $h$ NAIMENXSHEE KOLICHESTVO UZLOV IMEET 
\emph{FIBONACHCHIEVO DEREVO} PORYADKA $h+1$. (sM. OPREDELENIE DEREVXEV 
fIBONACHCHI V P.~6.2.1.) iTAK,
$$
N\ge F_{h+2}-1 > \phi^{h+2}/\sqrt{5}-2,
$$
I TREBUEMYJ REZULXTAT POLUCHAETSYA TAK ZHE, KAK SLEDSTVIE IZ TEOREMY 4.5.3F. \proofend

mY VIDIM, CHTO POISK V SBALANSIROVANNOM DEREVE POTREBUET BOLEE 25 SRAVNENIJ,
 TOLXKO ESLI DEREVO SOSTOIT IZ PO KRAJNEJ MERE $F_{27}-1= 196417$ UZLOV.

rASSMOTRIM TEPERX, CHTO PROISHODIT, KOGDA NOVYJ UZEL VSTAVLYAETSYA V 
SBALANSIROVANNOE DEREVO POSREDSTVOM ALGORITMA 6.2.2t. dEREVO NA RIS.~20 
OSTAETSYA SBALANSIROVANNYM, ESLI NOVYJ UZEL ZAJMET MESTO ODNOGO IZ UZLOV 
\leaf{4}, \leaf{5}, \leaf{B}, \leaf{7}, \leaf{10} ILI \leaf{13}, NO 
V DRUGIH SLUCHAYAH POTREBUETSYA NEKOTORAYA KORREKTIROVKA. tRUDNOSTI 
VOZNIKAYUT, ESLI IMEETSYA UZEL S POKAZATELEM SBALANSIROVANNOSTI $+1$, 
PRAVOE PODDEREVO KOTOROGO POSLE VSTAVKI STANOVITSYA VYSHE, ILI ESLI 
POKAZATELX SBALANSIROVANNOSTI RAVEN $-1$ I VYSHE. STANOVITSYA LEVOE 
PODDEREVO. lEGKO PONYATX, CHTO, V SUSHCHNOSTI, NAS BESPOKOYAT LISHX DVA SLUCHAYA:
\picture{sLUCHAI VSTAVKI V avl-DEREVO}
%% 539
(dRUGIE "PLOHIE" SLUCHAI MOZHNO POLUCHITX, ZERKALXNO OTRAZIV |TI DIAGRAMMY 
OTNOSITELXNO VERTIKALXNOJ OSI.) bOLXSHIMI PRYAMOUGOLXNIKAMI $\alpha$, 
$\beta$, $\gamma$, $\delta$ OBOZNACHENY PODDEREVXYA S SOOTVETSTVUYUSHCHIMI 
VYSOTAMI. sLUCHAJ 1 IMEET MESTO, ESLI NOVYJ |LEMENT UVELICHIL VYSOTU 
PRAVOGO PODDEREVA UZLA $B$ S~$h$ DO~$h+1$, A SLUCHAJ 2---KOGDA NOVYJ |LEMENT 
UVELICHIVAET VYSOTU LEVOGO PODDEREVA UZLA $B$. vO VTOROM SLUCHAE MY IMEEM 
LIBO $h=0$ (I TOGDA SAM UZEL $X$ YAVLYAETSYA NOVYM UZLOM), LIBO UZEL $X$ 
IMEET DVA PODDEREVA S SOOTVETSTVENNYMI VYSOTAMI $(h-1, h)$ ILI $(h,h--l).$

pROSTYE PREOBRAZOVANIYA VOSSTANAVLIVAYUT BALANS V OBOIH SLUCHAYAH, SOHRANYAYA V 
TO ZHE VREMYA SIMMETRICHNYJ PORYADOK UZLOV $A$, $B$ I $X$.
\picture{pOVOROTY}
v SLUCHAE 1 MY PROSTO POVORACHIVAEM DEREVO NALEVO, PRIKREPLYAYA $\beta$ K 
$A$ VMESTO $B$. eTO PREOBRAZOVANIE PODOBNO PRIMENENIYU ASSOCIATIVNOGO 
ZAKONA K ALGEBRAICHESKOJ FORMULE, KOGDA MY ZAMENYAEM $\alpha (\beta\gamma)$ 
NA $(\alpha\beta)\gamma$. v SLUCHAE 2 |TO PRODELYVAETSYA DVAZHDY:
SNACHALA $(X,B)$ POVORACHIVAETSYA NAPRAVO, ZATEM $(A,X)$---NALEVO. v OBOIH 
SLUCHAYAH NUZHNO IZMENITX V DEREVE LISHX NESKOLXKO SSYLOK. dALEE NOVYE DEREVXYA 
IMEYUT VYSOTU $h+2$, V TOCHNOSTI TU ZHE, CHTO I DO VSTAVKI |LEMENTA; 
SLEDOVATELXNO, CHASTX DEREVA, RASPOLOZHENNAYA NAD UZLOM $A$ (ESLI TAKOVAYA 
IMEETSYA), OSTAETSYA SBALANSIROVANNOJ.
\picture{dEREVO RIS. 20, SBALANSIROVANNOE POSLE VSTAVKI NOVOGO KLYUCHA R}

%% 540

nAPRIMER, ESLI MY VSTAVLYAEM NOVYJ UZEL NA MESTO \leaf{17} (RIS.~20), TO 
POSLE POVOROTA POLUCHIM SBALANSIROVANNOE DEREVO, IZOBRAZHENNOE NA RIS.~21 
(SLUCHAJ 1). zAMETXTE, CHTO NEKOTORYE IZ POKAZATELEJ SBALANSIROVANNOSTI IZMENILISX.

dETALI |TOJ PROCEDURY VSTAVKI MOZHNO RAZRABOTATX RAZLICHNYMI SPOSOBAMI. nA 
PERVYJ VZGLYAD BEZ VSPOMOGATELXNOGO STEKA NE OBOJTISX, TAK KAK NEOBHODIMO 
ZAPOMINATX UZLY, KOTORYE BUDUT ZATRONUTY VSTAVKOJ. nIZHE PRIVODITSYA 
ALGORITM, V KOTOROM, PRIBEGNUV K MALENXKOJ HITROSTI, MY OBHODIMSYA BEZ 
STEKA, VYIGRYVAYA PRI |TOM V SKOROSTI.

\alg a.(pOISK, S VSTAVKOJ PO SBALANSIROVANNOMU DEREVU.) iMEETSYA TABLICA 
ZAPISEJ, OBRAZUYUSHCHIH SBALANSIROVANNOE BINARNOE DEREVO. aLGORITM POZVOLYAET 
PROIZVESTI POISK DANNOGO ARGUMENTA $K$. eSLI $K$ V TABLICE NET, V 
PODHODYASHCHEM MESTE V DEREVO VSTAVLYAETSYA NOVYJ UZEL, SODERZHASHCHIJ $K$. pRI 
NEOBHODIMOSTI PROIZVODITSYA BALANSIROVKA DEREVA.

pREDPOLAGAETSYA (KAK I V ALGORITME 6.2.2t), CHTO UZLY SODERZHAT POLYA |KEY|, 
|LLINK| I |RLINK|. kROME TOGO, IMEETSYA NOVOE POLE
|B(P)| = POKAZATELX SBALANSIROVANNOSTI UZLA |NODE(P)|, T. E. RAZNOSTX 
VYSOT PRAVOGO I LEVOGO PODDEREVXEV; |TO POLE VSEGDA SODERZHIT $+1$, $0$ 
ILI~$-1$. pO ADRESU |HEAD| RASPOLOZHEN SPECIALXNYJ GOLOVNOJ UZEL; |RLINK 
(HEAD)| UKAZYVAET NA KORENX DEREVA, a |LLINK (HEAD)| ISPOLXZUETSYA DLYA 
HRANENIYA POLNOJ VYSOTY DEREVA. dLYA DANNOGO ALGORITMA VYSOTA NE IMEET 
ZNACHENIYA, NO ZNANIE EE POLEZNO DLYA PROCEDURY KONKATENACII, 
OBSUZHDAYUSHCHEJSYA NIZHE. mY PREDPOLAGAEM, CHTO DEREVO \emph{NEPUSTO}, 
T.~E. CHTO |RLINK (HEAD)\NE \NULL|.

v CELYAH UDOBSTVA OPISANIYA V ALGORITME ISPOLXZUETSYA OBOZNACHENIE 
|LINK (A, r)| KAK SINONIM |LLINK (r)| PRI $A=-1$ I KAK SINONIM |RLINK (r)| 
PRI $a=+1$.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX $|t|\asg |HEAD|$, 
$|S|\asg |P|\asg |RLINK (HEAD)|$. [uKAZATELXNAYA PEREMENNAYA |P| BUDET DVIGATXSYA 
VNIZ PO DEREVU; |S| BUDET UKAZYVATX NA MESTO, GDE MOZHET POTREBOVATXSYA 
BALANSIROVKA; |T| VSEGDA UKAZYVAET NA OTCA |S|.]

\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 UDACHNO ZAVERSHEN.
\st[shAG VLEVO.] uSTANOVITX $|Q|\asg |LLINK (r)|$. eSLI $|Q|=|\NULL|$, VYPOLNITX 
$|Q|\Asg|AVAIL|$ I $|LLINK(P)|\asg|Q|$; ZATEM IDTI NA \stp{5}. v PROTIVNOM 
SLUCHAE, ESLI $|B(Q)|\NE|0|$, USTANOVITX $|T|\asg|r|$ I $|S| \asg |Q|$. nAKONEC, 
USTANOVITX $|P|\asg|Q|$ I VERNUTXSYA NA \stp{2}.

\st[shAG VPRAVO.] uSTANOVITX $|Q|\asg |RLINK (r)|$. eSLI $|Q|=|\NULL|$, VYPOLNITX 
$|Q|\Asg|AVAIL|$ I $|RLINK (r)|\asg |Q|$; ZATEM IDTI NA \stp{5}.

%% 541
v PROTIVNOM SLUCHAE, ESLI $|B|(|Q|)\NE 0$, USTANOVITX $|t|\asg |r|$ I $|S|\asg |Q|$. 
nAKONEC, USTANOVITX |P\asg Q| I VERNUTXSYA NA \stp{2}. (pOSLEDNYUYU CHASTX 
|TOGO SHAGA MOZHNO OB®EDINITX S POSLEDNEJ CHASTXYU SHAGA \stp{3}.)

\st[vSTAVKA.] (mY TOLXKO CHTO PRISOEDINILI NOVYJ UZEL |NODE (Q)| K DEREVU; 
TEPERX EGO POLYA NUZHDAYUTSYA V NACHALXNOJ USTANOVKE.) uSTANOVITX    
$|KEY|(|Q|)\asg |K|$, 
$|LLINK(Q)|\asg |RLINK(Q)|\asg\NULL$, $|B(Q)|\asg 0$. 

\st[kORREKTIROVKA POKAZATELEJ SBALANSIROVANNOSTI.] (tEPERX NULEVYE POKAZATELI 
SBALANSIROVANNOSTI MEZHDU |S| I |Q| NUZHNO ZAMENITX NA $\pm1$.) eSLI 
$K<|KEY(S)|$, USTANOVITX 
$|R|\asg |P| \asg |LLINK(S)|$;  V PROTIVNOM SLUCHAE USTANOVITX 
$|R|\asg |r| \asg |RLINK(S)|$. zATEM NUZHNO 0 ILI BOLEE RAZ POVTORYATX SLEDUYUSHCHUYU 
OPERACIYU, POKA |P| NE STANET RAVNYM |Q|: ESLI $K<|KEY(P)|$, USTANOVITX 
$|B(P)|\asg -1$ I $|P|\asg |LLINK(P)|$;
ESLI $K > |KEY(P)|$, USTANOVITX $|B(P)|\asg +1$  I $|P|\asg |RLINK (r)|$. (eSLI 
$K= |KEY(r)|$, ZNACHIT, $|P|=|Q|$, I MOZHNO PEREJTI K SLEDUYUSHCHEMU SHAGU.)

\st[pROVERKA SBALANSIROVANNOSTI.] eSLI $K<|KEY (S)|$, USTANOVITX 
$a\asg -1$; V PROTIVNOM SLUCHAE $a\asg +1$. tEPERX VOZMOZHNY TRI SLUCHAYA:

\medskip
\item{i)} eSLI $|v (S)| = 0$ (DEREVO STALO VYSHE), USTANOVITX 
$|v (S)|\asg a$, $|LLINk (HEAD)| \asg  |LLINk(HEAD)| + 1$; ALGORITM 
ZAVERSHEN.

\item{ii} eSLI $|B(S)|=-a$ (DEREVO STALO BOLEE SBALANSIROVANNYM),
USTANOVITX $|B(S)|\asg 0$; ALGORITM ZAVERSHEN. 

\item{iii)} eSLI $|B(S)|=a$ (DEREVO PERESTALO BYTX SBALANSIROVANNYM), 
PRI $|B(R)|=a$ IDTI NA \stp{8}, PRI $|B(R)|=-a$ IDTI NA \stp{9}.
\medskip

\noindent(sLUCHAJ (iii) SOOTVETSTVUET SITUACII, IZOBRAZHENNOJ NA DIAGRAMME (1), 
PRI $a=+1$; |S| I |R| UKAZYVAYUT SOOTVETSTVENNO
NA UZLY $A$ I $B$, a $|LINK|(-a, |S|)$ UKAZYVAET NA $\alpha$ I T.D.) 

\st[oDNOKRATNYJ POVOROT.] uSTANOVITX $|P|\asg |R|$, 
$|LINK| (a, |S|)\asg |LINK|(-a, |R|)$, $|LINK|(-a, |R|)\asg |S|$, 
$|B|(|S|)\asg |B|(|R|)\asg 0$. pEREJTI NA \stp{10}.
\st[dVUKRATNYJ POVOROT.] uSTANOVITX $|P|\asg |LINK|(-a, |R|)$, $|LINK|(-a, 
|R|)\asg |LINK|(a, |P|)$, $|LINK|(a, |P|)\asg |R|$, $|LINK|(a, 
|S|)\asg |LINK|(-a, |P|)$,  $|LINK|(-a, |P|)\asg |S|$. tEPERX USTANOVITX
$$
(|B|(|S|), |B|(|R|))\asg \cases{
(-a, 0), & ESLI $|B|(|P|)=a$;\cr
( 0, 0), & ESLI $|B|(|P|)=0$;\cr
(0, a),  & ESLI $|B|(|P|)=-a$;\cr
}
\eqno(3)
$$
ZATEM $|B|(|P|)\asg 0$. 

\st[pOSLEDNIJ SHTRIH.] [mY ZAVERSHILI BALANSIRUYUSHCHEE 
PREOBRAZOVANIE OT (1) K (2), |P| UKAZYVAET NA NOVYJ KORENX,
%% 542
A |t|---NA OTCA STAROGO KORNYA.] eSLI $|S|=|RLINK(T)|$, TO USTANOVITX   
$|RLINK(T)|\asg |P|$;   V   PROTIVNOM   SLUCHAE $|LLINK(T)|\asg |P|$. 
\algend

eTOT ALGORITM DOVOLXNO DLINNYJ, NO RAZDELYAETSYA NA TRI PROSTYE CHASTI: SHAGI 
a1--a4 (POISK), SHAGI a5--a7 (VSTAVKA NOVOGO UZLA), SHAGI a8--a10 
(BALANSIROVKA DEREVA, ESLI ONA NUZHNA).
\picture{22. pOISK S VSTAVKOJ PO SBALANSIROVANNOMU DEREVU}

mY ZNAEM, CHTO DLYA RABOTY ALGORITMA TREBUETSYA OKOLO $C\log N$ EDINIC 
VREMENI PRI NEKOTOROM $C$, NO CHTOBY ZNATX, PRI KAKIH $N$ VYGODNO 
ISPOLXZOVATX SBALANSIROVANNYE DEREVXYA, NUZHNO OCENITX VELICHINU $C$. 
aNALIZ SLEDUYUSHCHEJ \MIX-PROGRAMMY POZVOLYAET PODOJTI K RESHENIYU |TOGO VOPROSA.
\prog a.(pOISK S VSTAVKOJ PO SBALANSIROVANNOMU DEREVU.) eTA REALIZACIYA 
ALGORITMA a ISPOLXZUET SLEDUYUSHCHIJ FORMAT UZLOV DEREVA:
\picture{fORMAT UZLA avl-DEREVA}
%% 543
$|rA|\equiv K$, $|rI1|\equiv|P|$, $|rI2|\equiv |Q|$, $|rI3|\equiv |R|$, 
$|rI4|\equiv S$, $|rI5|\equiv |t|$. pROGRAMMA DLYA SHAGOV a7--a9 DUBLIRUETSYA,
 TAK CHTO VELICHINA $a$ V YAVNOM VIDE V PROGRAMME NE FIGURIRUET.
\code
B     &EQU   &0:1
LLINK &EQU   &2:3
RLINK &EQU   &4:5
START &LDA   &k              &   1      &A1. nACHALXNAYA USTANOVKA.
      &ENT5  &HEAD           &   1      &$|t|\asg |HEAD|$.
      &LD2   &0,5 (RLINK)    &   1      &$|Q|\asg |RLINK(HEAD)|$.
      &JMP   &2F             &   1      &nA a2 S $|S|\asg |P| \asg |Q|$
4n    &LD2   &0,1 (RLINK)    &  s2      &a4. shAG VPRAVO. $|Q|\asg |RLINK(P)|$
      &J2Z   &5F             &  s2      &nA a5, ESLI $|Q|=\NULL$.
1n    &LDX   &0,2 (v)        &  C-1     &$|rX|\asg |B(Q)|$.
      &JXZ   &*+3            &  C-1     &pEREHOD, ESLI $|B(Q)|=0$.
      &ENT5  &0,1            &  D-1     &$|T|\asg |P|$.
2H    &ENT4  &0,2            &  D       &$|S|\asg |Q|$.
      &ENT1  &0,2            &  s       &$|P|\asg |Q|$.
      &CMPA  &1,1            &  s       &a2. sRAVNENIE.
      &JG    &4v             &  s       &nA a4,ESLI $K>|KEY(P)|$.
      &JE    &SUCCESS        &  s1      &vYHOD, ESLI $k=|KEY(r)|$.
      &LD2   &0,1 (LLINK)    & C1-S     &A3. shAG VLEVO. $|Q|\asg |LLINK(r)|$.
      &J2NZ  &1v             & C1-S     &pEREHOD, ESLI $|Q|\ne\NULL$.
\noalign{20--29 5n (SKOPIROVATX ZDESX STROKI 14---23 PROGRAMMY 6.2.2 t)   a5. vSTAVKA.}
6H    &CMPA  &1,4            & 1-S      &A6. KoppeKT. POKAZAT. SBALANSIR.
      &JL    &*+3            & 1-S      &pEREHOD, ESLI $K< |KEY(S)|$.
      &LDS   &0,4 (RLINK)    &  E       &$|R|\asg |RLINK(S)|$.
      &Jmr   &*+2            &  E
      &LD3   &0,4 (LLINK)    & 1-S-E    &$|R|\asg |LLINK(S)|$.
      &ENT1  &0,3            & 1-S      &$|P|\asg |R|$.
      &ENTX  &-1             & 1-S      &$|rX|\asg -1$.
      &JMP   &1F             & 1-S      &nA CIKL SRAVNENIYA.
4n    &JE    &7F             &F2+1-S    &nA a7, ESLI $K=|KEY(P)|$.
      &STX   &0,1 (1:1)      &  F2      &$|B(P)|\asg +1$ (ON BYL $+0$).
      &LD1   &0,1 (RLINK)    &  F2      &$|P|\asg |RLINK(P)|$.
1n    &CMPA  &1,1            &F+1-S
      &JGE   &4B             &F+1-S     &pEREHOD, ESLI $k \ge |KEY (P)|$.
      &STX   &0,1 (v)        &  F1      &$|v(r)|\asg -1$.
      &LD1   &0,1 (LLINK)    &  F1      &$|P|\asg |LLINK(P)|$.
      &JMP   &1B             &  F1      &nA CIKL SRAVNENIYA.
7n    &LD2   &0,4(B)         & 1-S      &A7. pROVERKA SBALANSIR. $|rI2|\asg |B(S)|$.
      &STZ   &0,4 (v)        & 1-S      &$|B(S)|\asg 0$.
      &CMPA  &1,4            &1-S
      &JG    &A7R            &1-S       &nA $a=+1$ PODPROGRAMMU,  ESLI $K>|KEY(S)|$.
\endcode
(ZDESX ESHCHE KOD V 2 KOLONKI --- PRIDELATX)
% 50--68
%A7L    J2P   DONE          A7R J2N   DONE          1-S   vYHOD,    ESLI $|rl2|=-a$.
%       J2Z   7F                J2Z   6F            G+J   pEREHOD,  ESLI |B(S)| BYL NULEM.
%       ENT1 0,3                ENT1 0,3             G    $|P|\asg|R|$.
%       LD2  0,3 (v)            LD2  0,3 (v)         G    $|rI2|\asg |B(R)|$.
%       J2N  A8L                J2P A8R              G    nA. a8,   ESLI $|rI2|=a$.

\bye