\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 i0}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