\input style \chapno=6\subchno=2\subsubchno=3\chapnotrue %%545 Ч ретчха пюетедш обу нпцеф йофетеупчбфш юйумп~$B_{nh}$ увбмбоуйтпчбоощи вйобтощи детечшеч у $n$~чохфтеоойнй хъмбнй й чщупфпк~$h$. Дмс оевпмшыйи~$h$ йъ уппфопыеойк $$ 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) $$ оефтхдоп чщюйумйфш ртпйъчпдсэха жхолгйа~$B_h(z)=\sum_{n\ge0}B_{nh}z^n$ (ун. хрт.~6). Фблйн пвтбъпн, $$ \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 } $$ й чппвэе $B_h(z)$ ртй $h\ge3$ йнееф чйд $$ 2^{F_{h+1}-1}z^{F_{h+2}-1}+2^{F_{h+1}-2}L_{h-1}z^{F_{h+2}} +\hbox{умпцоще юмеощ}+2^{h-1}z^{2^h-2}+z^{2^h-1}, \eqno(6) $$ зде $L_k=F_{k+1}+F_{k-1}$. (Ьфб жптнхмб пвпвэбеф фептенх~A.) Юйумп чуеи увбмбоуйтпчбоощи детечшеч чщупфщ~$h$ тбчоп $B_h=B_h(1)$ й хдпчмефчптсеф телхттеофопнх уппфопыеойа $$ B_0=B_1=1,\quad B_{h+1}=B^2_h+2B_hB_{h-1}, \eqno(7) $$ фбл юфп $B_2=3$, $B_3=3\cdot5$, $B_4=3^2\cdot5\cdot7$, $B_5=3^3\cdot5^2\cdot7\cdot23$; ч пвэен умхюбе $$ 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) $$ зде $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$. Рпумедпчбфемшопуфй $A_h$ й $B_h$ тбуфхф пюеош вщуфтп, лбл "ьлурпоеофб ьлурпоеофщ"; йъ хрт.~7 умедхеф, юфп ухэеуфчхеф декуфчйфемшопе юйумп $\theta\approx1.43684$, фблпе, юфп $$ 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) $$ Еумй уюйфбфш, юфп чуе $B_h$~детечшеч тбчопчетпсфощ, фп, лбл рплбъщчбеф хрт.~8, утедоее юйумп хъмпч ч детече чщупфщ~$h$ тбчоп $$ B'_h(1)/B_h(1)\approx (0.70118)\cdot 2^h. \eqno(10) $$ Ьфп пъобюбеф, юфп чщупфб увбмбоуйтпчбоопзп детечб у $n$~хъмбнй пвщюоп зптбъдп вмйце л~$\log_2 n$, юен л~$\log_\phi n$. Л упцбмеойа, рпмхюеооще теъхмшфбфщ ое йнеаф пфопыеойс л бмзптйфнх~A, фбл лбл неибойън ьфпзп бмзптйфнб дембеф оелпфптще детечшс зптбъдп впмее четпсфощнй, юен дтхзйе. Тбуунпфтйн, обртйнет, умхюбк~$N=7$, лпздб ухэеуфчхеф 17~увбмбоуйтпчбоощи детечшеч. Лмаюй нпцоп чуфбчмсфш $7!=5040$ тбъмйюощнй урпупвбнй, ртй ьфпн йдебмшоп увбмбоуйтпчбоопе "упчетыеоопе" %%546 детечп \picture{тйу. об уфт. 546} рпмхюбефус 2160~тбъ. Ч ртпфйчпрпмпцопуфш ьфпнх жйвпобююйечп детечп \picture{тйу. об уфт. 546} чуфтеюбефус мйыш 144~тбъб, б рпипцее детечп \picture{тйу. об уфт. 546} чуфтеюбефус 216~тбъ. [Ъбнеойч мечще рпддетечшс ч~(12) й~(13) ртпйъчпмшощнй увбмбоуйтпчбоощнй детечшснй у юефщтшнс хъмбнй й ъбфен ъетлбмшоп пфтбъйч пфопуйфемшоп четфйлбмшопк пуй, рпмхюйн 16~тбъмйюощи детечшеч; чпуенш детечшеч, рпмхюеоощи йъ~(12), чуфтеюбафус рп 144~тбъб, б рпмхюеооще йъ~(13)---рп 216~тбъ. Дпчпмшоп уфтбооп, юфп (13) чуфтеюбефус юбэе, юен (12).] Фпф жблф, юфп йдебмшоп увбмбоуйтпчбооще детечшс рпмхюбафус у фблпк чщуплпк четпсфопуфша---упчнеуфоп у жптнхмпк~(10), уппфчефуфчхаэек умхюба тбчощи четпсфопуфек,---дембеф ютеъчщюбкоп ртбчдпрпдпвощн уппфопыеойе: (утедоее юйумп утбчоеойк ртй рпйуле рп увбмбоуйтпчбоопнх детечх)% $\approx\log_2 N+c$, зде $c$---нбмбс лпоуфбофб. Декуфчйфемшоп, ьнрйтйюеулйе ртпчетлй рплбъщчбаф, юфп утедоее юйумп утбчоеойк, фтевхенщи дмс чуфбчлй $N\hbox{-зп}$ ьменеофб, ртй ое умйылпн нбмщи~$N$ ртйнетоп тбчоп~$1.01\log_2 N+0.1$ Юфпвщ йъхюйфш рпчедеойе бмзптйфнб~A об жбъби чуфбчлй й вбмбоуйтпчлй, нпцоп лмбууйжйгйтпчбфш чоеыойе хъмщ увбмбоуйтпчбоопзп детечб, лбл рплбъбоп об тйу.~23. Рхфш, чедхэйк йъ чоеыоезп хъмб ччети, прйущчбефус рпумедпчбфемшопуфша рмаупч й нйохупч ("|+|" дмс ртбчпк уущмлй, "|-|" дмс мечпк); нщ чщрйущчбен ее, рплб ое дпуфйзоен ретчпзп хъмб у оеохмечщн %% 547 рплбъбфемен увбмбоуйтпчбоопуфй ймй (еумй фблйи хъмпч оеф) рплб ое дпуфйзоен лптос. Ъбфен нщ рйыен |A| ймй~|B| ч уппфчефуфчйй у фен, вхдеф мй опчпе детечп, рпмхюеоопе рпуме чуфбчлй об дбоопе неуфп чохфтеооезп хъмб, увбмбоуйтпчбоощн ймй оеф. Фбл/рхфш йъ (3) ччети лпдйтхефус |++-B|, юфп пъобюбеф "ртбчбс уущмлб, ртбчбс уущмлб, мечбс уущмлб, оеувбмбоуйтпчбоп". Еумй лпд плбоюйчбефус об~|A|, рпуме чуфбчлй опчпзп хъмб ое \picture{ Тйу. 23.Лпдщ лмбууйжйлбгйй, пртедемсаэйе рпчедеойе бмзптйфнб A рпуме чуфбчлй. } фтевхефус вбмбоуйтпчлй; лпд, плбоюйчбаэйкус об~|++B| ймй~|--B|, фтевхеф пдоплтбфопзп рпчптпфб, б лпд, плбоюйчбаэйкус об~|+-B| ймй~|-+B|, фтевхеф дчхлтбфопзп рпчптпфб. Еумй рхфш упуфпйф йъ $k$~ъчеошеч, ч ыбзе~A6 лпттелфйтхефус тпчоп $k-1$~рплбъбфемек увбмбоуйтпчбоопуфй. Фблйн пвтбъпн, прйубооще рпумедпчбфемшопуфй дбаф оепвипдйнха йожптнбгйа п чтенеой тбвпфщ ыбзпч~A6--A10. Ьнрйтйюеулйе ртпчетлй уп умхюбкощнй юйумбнй ч дйбрбъпое $100\le N\le2000$ дбмй ртйвмйцеооще четпсфопуфй дмс рхфек тбъмйюощи чйдпч (фбвм.~1); пюечйдоп, ьфй четпсфопуфй вщуфтп ртйвмйцбафус л ртедемшощн ъобюеойсн ртй~$N\to\infty$. Ч фбвм.~2 дбощ уппфчефуфчхаэйе фпюоще четпсфопуфй ($N=10$; чуе $10!$~ретеуфбопчпл уюйфбмйуш тбчопчетпсфощнй.) Йъ фбвм.~1 нщ чйдйн, юфп четпсфопуфш упвщфйс~$k\le 2$ тбчоб $0.144+0.153+0.144+0.144=0.585$; фблйн пвтбъпн, рпюфй ч 60\%~умхюбеч ыбз~A6 фтйчйбмео. Утедоее юйумп йънеоеойк лпьжжйгйеофпч увбмбоуйтпчбоопуфй об ьфпн ыбзе (0 ъбнеосефус об~$\pm1$) ртйнетоп тбчоп~$1.8$. Утедоее юйумп йънеоеойк лпьжжйгйеофпч увбмбоуйтпчбоопуфй пф~$\pm1$ дп~$0$ ч ыбзби~A7--A10 тбчоп $0.535+2(0.233+0.232)\approx1.5$, ф.~е.~чуфбчлб пдопзп опчпзп хъмб дпвбчмсеф ч утедоен $0.3$~оеувбмбоуйтпчбоопзп хъмб. Ьфп упзмбухефус у фен жблфпн, юфп плпмп 68\% чуеи хъмпч ч умхюбкощи детечшси, рпмхюеоощи у рпнпэша бмзптйфнб~A, плбъбмйуш увбмбоуйтпчбоощнй. %%548 { \def\!#1{\overline{\mathstrut #1}} \htable{Фбвмйгб 1}{Ртйвмйцеооще четпсфопуфй ртй чуфбчле $N\hbox{-зп}$ ьменеофб}% {#&\hfill$#$&&\bskip\hfill$#$\hfill\cr & \hbox{Дмйоб рхфй} & \hbox{ Оеф вбмбоуйтпчлй} & \hbox{ Пдоплтбфощк рпчптпф} & \hbox{Дчхлтбфощк рпчптпф}\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{Фбвмйгб 2}{Фпюоще четпсфопуфй ртй чуфбчле $10\hbox{-зп}$ ьменеофб}% {#&\hfill$#$\hfill&&\bskip\hfill$#$\hfill\cr &\hbox{Дмйоб рхфй} & \hbox{ Оеф вбмбоуйтпчлй} & \hbox{ Пдоплтбфощк рпчптпф} & \hbox{Дчхлтбфощк рпчптпф}\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} } } Ртйвмйцеообс нпдемш рпчедеойс бмзптйфнб~A вщмб ртедмпцеоб Л.~Л.~Жпуфетпн [Proc. ACM Nat. Conf., {\bf 20}, (1965), 192--205]. Нпдемш ьфб ое чрпмое лпттелфоб, оп дпуфбфпюоп вмйълб л йуфйое, юфпвщ пфтбъйфш ухэеуфчп демб. Ртедрпмпцйн, юфп ч впмшыпн детече, рпуфтпеоопн у рпнпэша бмзптйфнб~A, рплбъбфемш увбмбоуйтпчбоопуфй дбоопзп хъмб у четпсфопуфша~$p$ тбчео~0; фпздб ьфпф рплбъбфемш тбчео~$+1$ у четпсфопуфша~${1\over2}(1-p)$ й у фпк це четпсфопуфша тбчео~$-1$. Ртедрпмпцйн дбмее (веъ чуслйи пвпуопчбойк), юфп рплбъбфемй увбмбоуйтпчбоопуфй чуеи хъмпч оеъбчйуйнщ. Фпздб четпсфопуфш фпзп, юфп ыбз~A6 дембеф оеохмечщнй тпчоп $(k-1)$~рплбъбфемек, тбчоб~$p^{k-1}(1-p)$, рпьфпнх утедоее ъобюеойе~$k$ еуфш~$1/(1-p)$. Четпсфопуфш фпзп, юфп охцоп рпчетохфш юбуфш детечб, тбчоб~${1\over2}$. Ч утедоен чуфбчлб опчпзп хъмб дпмцоб хчемйюйфш юйумп увбмбоуйтпчбоощи хъмпч чб~$p$; ьфп юйумп ч декуфчйфемшопуфй хчемйюйчбефус об~1 ч ыбзе~A5, об $-p1(1-т)$ ч ыбзе~A6, об~${1\over2}$ ч ыбзе~A7 й об~${1\over2}\cdot2$ ч ыбзе~A8 ймй A9, фбл юфп нщ рпмхюбен $$ p=1-p/(1-p)+{1\over2}+1. $$ %%549 Теыеойе ьфпзп хтбчоеойс пфопуйфемшоп~$p$ дбеф оермпипе упзмбуйе у фбвм.~1: $$ p={9-\sqrt{41}\over 4}\approx 0.649;\quad 1/(1-p)\approx 2.851. \eqno(14) $$ Чтенс тбвпфщ жбъщ рпйулб ртпзтбннщ~A (уфтплй 01--19) тбчоп $$ 10C+C1+2D+2-3S, \eqno(15) $$ зде $C$, $C1$, $S$---фе це убнще, юфп й ч ртедщдхэйи бмзптйфнби ьфпк змбчщ, a $D$---юйумп оеувбмбоуйтпчбоощи хъмпч, ртпипдйнщи ртй рпйуле. Ьнрйтйюеулйе ртпчетлй рплбъщчбаф, юфп нпцоп рпмпцйфш $D\approx{1\over3}C$, $C1\approx{1\over2}(C+S)$, $C+S\approx1.01\log_2N+0.1$, фбл юфп утедоее чтенс рпйулб ртйнетоп тбчоп $11.3\log_2N+3-13.7S$~едйойг. (Еумй рпйул ртпйъчпдйфус зптбъдп юбэе чуфбчлй, нщ нпзмй вщ, тбъхнеефус, йурпмшъпчбфш пфдемшоха, впмее вщуфтха ртпзтбннх рпйулб, фбл лбл ое вщмп вщ оепвипдйнпуфй умедйфш ъб лпьжжйгйеофбнй увбмбоуйтпчбоопуфй; ч ьфпн умхюбе утедоее чтенс рпйулб упуфбчймп вщ мйыш $(6.6\log_2N+3)u$, б ч обйихдыен умхюбе чтенс тбвпфщ вхдеф чуе це неошые, юен утедоее чтенс тбвпфщ ртпзтбннщ 6.2.2Ф.) Еумй рпйул оехдбюео, чтенс тбвпфщ жбъщ чуфбчлй ч ртпзтбнне~Б (уфтплй 20--45) тбчоп $8F+26+(0, 1\hbox{ ймй }2)$~едйойг. Дбооще фбвм.~1 рплбъщчбаф, юфп ч утедоен $F\approx1.8$. Жбъб вбмбоуйтпчлй (уфтплй 46--101) фтевхеф $16.5$, $8$, $27.5$ ймй $45.5(\pm0.5)$~едйойг ч ъбчйуйнпуфй пф фпзп, хчемйюйчбен мй нщ рпмоха чщупфх, ртпуфп мй чщипдйн веъ вбмбоуйтпчлй ймй це ртпйъчпдйн пдоплтбфощк ймй дчхлтбфощк рпчптпф. Ретчщк умхюбк рпюфй ое чуфтеюбефус, б дтхзйе чуфтеюбафус у ртйвмйцеоощнй четпсфопуфснй $0.535$, $0.233$, $0.232$, рпьфпнх утедоее чтенс чщрпмоеойс лпнвйойтпчбоопк чуфбчпюоп-вбмбоуйтпчпюопк юбуфй ртпзтбннщ~A упуфбчмсеф ртйнетоп $63u$. Ьфй юйумб рплбъщчбаф, юфп претбгйй обд увбмбоуйтпчбоощнй детечшснй дпчпмшоп вщуфтщ, ипфс ртпзтбннб й ъбойнбеф нопзп неуфб ч рбнсфй. Еумй йуипдоще дбооще счмсафус умхюбкощнй, фп ртпуфпк бмзптйфн чуфбчлй ч детечп (р.~6.2.2) ртпйъчпдйф пдох чуфбчлх ртйнетоп об $50u$~вщуфтее, оп йурпмшъпчбойе увбмбоуйтпчбоощи детечшеч збтбофйтхеф иптпыйе теъхмшфбфщ дбце ртй оеумхюбкощи йуипдощи дбоощи. Пдйо йъ урпупвпч утбчоеойс ртпзтбннщ~A у ртпзтбннпк 6.2.2Ф упуфпйф ч тбуунпфтеойй обйихдыезп дмс рпумедоек ртпзтбннщ умхюбс. Еумй нщ ъбйофетеухенус лпмйюеуфчпн чтенеой, оепвипдйнщн дмс чуфбчлй ч чпътбуфбаэен рптсдле $N$~лмаюек ч ретчпобюбмшоп рхуфпе детечп, фп плбцефус, юфп ртпзтбннб~A недмеооее ртй $N\le 26$ й вщуфтее ртй $N\ge 27$. %%550 \picture{Тйу. 24. Рпмс RANK, йурпмшъхенще ртй рпйуле рп рпъйгйй.} %% 551 \section Ртедуфбчмеойе мйоекопзп урйулб. Четоенус феретш л ъбнеюбойа, удембоопнх ч обюбме ьфпзп рхолфб, п фпн, юфп увбмбоуйтпчбооще детечшс нпзхф йурпмшъпчбфшус дмс ртедуфбчмеойс мйоекощи урйулпч фблйн пвтбъпн, юфп нпцоп вхдеф вщуфтп чуфбчмсфш ьменеофщ (ртепдпмечбс фтхдопуфш рпумедпчбфемшопзп тбурпмпцеойс), упитбосс ртй ьфпн умхюбкощн дпуфхр л ьменеофбн урйулб (ф. е. ртепдпмечбс фтхдопуфш учсъбоопзп тбурпмпцеойс). Йдес упуфпйф ч фпн, юфпвщ ч лбцдпн хъме ччеуфй опчпе рпме у йнеоен |RANK|. Ьфп рпме рплбъщчбеф пфопуйфемшопе рпмпцеойе хъмб ч учпен рпддетече, ф.~е. поп тбчоп едйойге рмау юйумп хъмпч ч мечпн рпддетече. Об тйу.~24 йъпвтбцеощ ъобюеойс~|RANK| дмс вйобтопзп детечб об тйу.~23. Нщ нпцен рпмопуфша йулмаюйфш рпме~|KEY|, ймй ртй цембойй нпцоп йнефш пвб рпмс, юфп рпъчпмсеф обипдйфш ьменеофщ лбл рп ъобюеойа лмаюб, фбл й рп пфопуйфемшопнх рпмпцеойа ч урйуле. Йурпмшъпчбойе рпмс~|RANK| рпъчпмсеф учеуфй рпйул рп рпъйгйй л йъхюеоощн бмзптйфнбн. \alg Ч.(Рпйул рп рпъйгйй ч детече.) Йнеефус мйоекощк урйупл, ртедуфбчмеоощк ч чйде вйобтопзп детечб. Бмзптйфн рпъчпмсеф рп дбоопнх~$k$ обкфй $k\hbox{-к}$~ьменеоф урйулб ($k\hbox{-к}$~хъем детечб ч уйннефтйюопн рптсдле). Ртедрпмбзбефус, юфп, лбл й ч бмзптйфне~A, йнеефус зпмпчопк хъем, ч лбцдпн хъме еуфш рпмс~|LLINK| й~|RL1NK| й, лтпне фпзп, рпме~|RANK|, прйубоопе чщые. \st[Обюбмшобс хуфбопчлб.] Хуфбопчйфш $|M|\asg k$, $|P|\asg |RLINK|(|HEAD|)$. \st[Утбчоеойе.] Еумй $|P|=\NULL$, бмзптйфн лпоюбефус оехдбюоп. (Ьфп нпцеф умхюйфшус, мйыш еумй $k$ впмшые юйумб хъмпч ч детече ймй $k\le 0$.) Ч ртпфйчопн умхюбе, еумй $|M|<|RANK|(|P|)$, ретекфй об \stp{3}; еумй $|M|>|RANK|(|P|)$, ретекфй об \stp{4}; б еумй $|M|=|RANK|(|P|)$, бмзптйфн лпоюбефус хдбюоп (|P| хлбъщчбеф об $k\hbox{-к}$~хъем). \st[Ыбз чмечп.] Хуфбопчйфш $|P|\asg|LLINK|(|P|)$ й четохфшус об~\stp{2}. \st[Ыбз чртбчп.] Хуфбопчйфш $|M|\asg|M|-|RANK|(|P|)$, $|P|\asg|RLINK|(|P|)$ й четохфшус об~\stp{2}. \algend Ч дбоопн бмзптйфне йофетеу ртедуфбчмсеф мйыш претбгйс~$|M|\asg |M|-|RANK|(|P|)$ ч ыбзе Ч4. Нпцоп бобмпзйюощн пвтбъпн нпдйжйгйтпчбфш ртпгедхтх чуфбчлй, ипфс еуфш учпй фполпуфй. \alg C.(Чуфбчлб ч увбмбоуйтпчбоопе детечп рп рпъйгйй.) Йнеефус мйоекощк урйупл, ртедуфбчмеоощк ч чйде увбмбоуйтпчбоопзп вйобтопзп детечб. Бмзптйфн рпъчпмсеф ртй дбоопн~$k$ чуфбчйфш опчщк хъем (|Q|---хлбъбфемш об оезп) ретед $k\hbox{-н}$~ьменеофпн урйулб. Еумй $k=N+1$, опчщк хъем рпнеэбефус ч лпоег урйулб. %%552 Лтпне фпзп, юфп чщрпмоеощ хумпчйс бмзптйфнб~A, ртедрпмбзбефус, юфп лбцдщк хъем упдетцйф рпме~|RANK|. Ьфпф бмзптйфн пюеош рпипц об бмзптйфн~A у фен мйыш пфмйюйен, юфп чнеуфп рпмс~|KEY| йурпмшъхефус рпме~|RANK|. \st[Обюбмшобс хуфбопчлб.] Хуфбопчйфш $|T|\asg|HEAD|$, $|S|\asg|P|\asg|RLINK|(|HEAD|)$, $|U|\asg|M|\asg k$. \st[Утбчоеойе.] Еумй $|M|\le |RANK|(|P|)$, ретекфй об~\stp{3}; ч ртпфйчопн умхюбе ретекфй об~\stp{4}. \st[Ыбз чмечп.] Хуфбопчйфш $|RANK|(|P|)\asg|RANK|(|P|)+1$ (нщ вхден чуфбчмсфш опчщк хъем умечб пф~$|P|$). Хуфбопчйфш $|R|\asg|LLINK|(|P|)$. Еумй $|R|=\NULL$, хуфбопчйфш $|LLINK|(|P|)\asg|Q|$ й ретекфй об~\stp{5}. Ч ртпфйчопн умхюбе, еумй $|B|(|R|)\ne0$, хуфбопчйфш $|T|\asg|P|$, $|S|\asg|R|$ й~$|U|\asg|M|$. Хуфбопчйфш $|P|\asg|R|$ й четохфшус об~\stp{2}. \st[Ыбз чртбчп.] Хуфбопчйфш $|M|\asg|M|-|RANK|(|P|)$ й~$|R|\asg|RLINK|(|P|)$. Еумй $|R|=\NULL$, хуфбопчйфш $|RLINK|(|P|)\asg|Q|$ й ретекфй об~\stp{5}. Ч ртпфйчопн умхюбе, еумй $|B|(|R|)\ne0$, хуфбопчйфш $|T|\asg|P|$, $|S|\asg|R|$, $|U|\asg|M|$. Облпоег, хуфбопчйфш $|P|\asg|R|$ й четохфшус об \stp{2}. \st[Чуфбчлб.] Хуфбопчйфш $|RANK|(|Q|)+1$, $|LLINK|(|Q|)\asg|RLINK|(|Q|)\asg\NULL$, $|B|(|Q|)\asg0$. \st[Лпттелфйтпчлб рплбъбфемек увбмбоуйтпчбоопуфй.] Хуфбопчйфш~$|M|\asg|U|$. (Фен убнщн чпууфбобчмйчбефус ртедщдхэее ъобюеойе |M|, лпздб |P| вщмп тбчоп~|S|; чуе рпмс~|RANK| рпдипдсэйн пвтбъпн хуфбопчмеощ.) Еумй $|M|<|RANK|(|S|)$, хуфбопчйфш~$|R|\asg|P|\asg|LLINK|(|S|)$; ч ртпфйчопн умхюбе хуфбопчйфш $|R|\asg|P|\asg|RLINK|(|S|)$ й~$|M|\asg|M|-|RANK|(|S|)$. Ъбфен, рплб~|Т| ое уфбоеф тбчощн~|Q|, охцоп рпчфптсфш умедхаэха претбгйа: еумй $|M|<|RANK|(|P|)$, хуфбопчйфш $|B|(|P|)\asg-1$ й $|P|\asg|LLINK|(|P|)$; еумй $|M|>|RANK|(|P|)$, хуфбопчйфш $|B|(|P|)\asg+1$, $|M|\asg|M|-|RANK|(|P|)$ й~$|P|\asg|RLINK|(|P|)$. (Еумй $|M|=|RANK|(|P|)$, фп~$|P|=|Q|$, й нпцоп ретекфй л умедхаэенх ыбзх.) \st[Ртпчетлб увбмбоуйтпчбоопуфй.] Еумй $|U|<|RANK|(|S|)$, хуфбопчйфш $a\asg-1$; ч ртпфйчопн умхюбе $a\asg+1$. Феретш чпънпцоп оеулпмшлп умхюбеч: \itemitem{i)} Еумй $|B|(|S|)=0$, хуфбопчйфш $|B|(|S|)\asg a$, $|LLINK|(|HEAD|)\asg|LLINK|(|HEAD|)+1$; бмзптйфн ъбчетыео. \itemitem{ii)} Еумй $|B|(|S|)=-a$, хуфбопчйфш $|B|(|S|)\asg0$; бмзптйфн ъбчетыео. \itemitem{iii)} Еумй $|B|(|S|)=a$, фп ртй $|B|(|R|)=a$ охцоп йдфй об~\stp{8}, б ртй $|B|(|R|)=-a$---об~\stp{9}. \st[Пдоплтбфощк рпчптпф.] Хуфбопчйфш $|P|\asg|R|$, $|LINK|(a, |S|)\asg|LINK|(-a, |R|)$, $|LINK|(-a, |R|)\asg|S|$, $|B|(|S|)\asg|B|(|R|)\asg0$. Еумй $a= +1$, хуфбопчйфш $|RANK|(|R|)\asg|RANK|(|R|)+|RANK|(|S|)$; %%553 еумй $a=-1$, хуфбопчйфш $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|R|).$ Ретекфй об~\stp{10}. \st[Дчхлтбфощк рпчптпф.] Ртпдембфш чуе претбгйй ыбзб~A9 (бмзптйфнб ~A). Ъбфен, еумй $a=+1$, хуфбопчйфш $|RANK|(|R|)\asg|RANK|(|R|)-|RANK|(|P|)$, $|RANK|(|P|)\asg|RANK|(|P|) +|RANK|(|S|)$, еумй $a=-1$, хуфбопчйфш $|RANK|(|P|)\asg|RANK|(|P|)+|RANK|(|R|)$, ъбфен $|RANK|(|S|)\asg|RANK|(|S|)-|RANK|(|P|)$. \st [Рпумедойк ыфтйи.] Еумй $|S|=|RLINK|(|T|)$, фп хуфбопчйфш $|RLINK|(|T|)\asg|P|$; ч ртпфйчопн умхюбе $|LLINK|(|T|)\asg|P|$. \algend \section {*Хдбмеойе, лполбфеобгйс й ф. д}. Чппвэе зпчптс, ухэеуфчхеф нопзп дтхзйи претбгйк, лпфптще ое обтхыбаф увбмбоуйтпчбоопуфй детечшеч, оп уппфчефуфчхаэйе бмзптйфнщ дпуфбфпюоп дмйоощ, фбл юфп нщ ое вхден тбуунбфтйчбфш йи рпдтпвоп. Пвухдйн мйыш пуопчоще йдей, б йофетеухаэйкус юйфбфемш унпцеф веъ впмшыпзп фтхдб чпууфбопчйфш оепвипдйнще дефбмй. Ъбдбюб хдбмеойс, еумй рпуфбчйфш ее лпттелфоп, теыбефус ъб $O(\log N)$~ыбзпч [У.~У.~Foster, A Study of AVL Trees, Goodyear Aerospace Corp. report GER-12158 (April 1965)]. Ртецде чуезп хдбмеойе ртпйъчпмшопзп хъмб нпцоп учеуфй л ртпуфпнх хдбмеойа хъмб~|P|, ч лпфптпн $|LLINK|(|P|)$ ймй~$|RLINK|(|P|)$ тбчощ~$\NULL$, лбл ч бмзптйфне~6.2.2D. Ьфпф бмзптйфн умедхеф нпдйжйгйтпчбфш фблйн пвтбъпн, юфпвщ по уфтпйм урйупл хлбъбфемек, пртедемсаэйи рхфш л хъмх~|P|: $$ (P_0, a_0), (P_1, a_1), \ldots, (P_l, a_l), \eqno(16) $$ зде $P_0=|HEAD|$, $a_0=+1$; $|LINK| (a_i, P_i)=P_{i+1}$, $0\le i0}B_{nh}$? Лблпчб буйнрфпфйюеулбс утедосс чщупфб~$\sum_{h\ge0}hB_{nh}/\sum_{h\ge0}B_{nh}$? \ex[Н48] Четоп мй, юфп ртй чуфбчле $N\hbox{-зп}$ ьменеофб бмзптйфн~A упчетыбеф ч утедоен $\sim\log_2N+c$~утбчоеойк ($c$---оелпфптбс лпоуфбофб)? \ex[22] Чемйюйоб~$0.144$ фтйцдщ рпсчмсефус ч фбвм.~1: пдйо тбъ ртй~$k=l$ й дчбцдщ ртй~$k=2$. Чемйюйоб~$1/7$ чуфтеюбефус ч феи це фтеи неуфби фбвм.~2. Счмсефус мй упчрбдеойен, юфп чп чуеи фтеи неуфби уфпсф пдйоблпчще чемйюйощ, ймй об фп еуфш ртйюйощ? \ex[24] Юенх тбчоп нблуйнбмшопе чтенс тбвпфщ ртпзтбннщ~A ртй чуфбчле чпушнпзп хъмб ч увбмбоуйтпчбоопе детечп? Лблпчп нйойнбмшоп чпънпцопе чтенс фблпк чуфбчлй? \ex[10] Рпюенх рпме~|RANK| мхюые йурпмшъпчбфш фбл, лбл ч фелуфе, б ое ъбрпнйобфш ч лбюеуфче лмаюб опнет хъмб ("1" ч ретчпн хъме, "2" чп чфптпн й~ф.~д)? %%560 \ex[11] Бмзптйфнщ увбмбоуйтпчбоопзп детечб у рпнпэша рпмс~|RANK| вщмй ртйурпупвмеощ дмс тбвпфщ у мйоекощнй урйулбнй. Нпцоп мй фблйн це пвтбъпн ртйурпупвйфш бмзптйфнщ 6.2.2Ф й 6.2.2D? \ex[18] (Л.~Ь.~Лтько.) Ртедрпмпцйн, юфп хрптсдпюеоощк мйоекощк урйупл ртедуфбчмео ч чйде вйобтопзп детечб у рпмснй~|KEY| й~|RANK| ч лбцдпн хъме. Ртйдхнбкфе бмзптйфн, лпфптщк тбъщулйчбеф ч детече дбоощк лмаю~$K$ й пртедемсеф рпмпцеойе~$K$ ч урйуле, ф.~е. обипдйф юйумп~$M$, фблпе, юфп неошые~$K$ мйыш $M-1$~лмаюек. \rex[20] Обтйухкфе увбмбоуйтпчбоопе детечп, лпфптпе рпмхюймпуш вщ рпуме хдбмеойс лптоечпзп хъмб~|F| йъ детечб тйу.~20 у рпнпэша бмзптйфнб хдбмеойс, ртедмпцеоопзп ч фелуфе. \rex[21] Обтйухкфе увбмбоуйтпчбоопе детечп, лпфптпе рпмхюймпуш вщ рпуме лполбфеобгйй детечб Жйвпобююй (12): (a) уртбчб й (b) умечб пф детечб тйу.~20, еумй йурпмшъпчбфш бмзптйфн лполбфеобгйй, ртедмпцеоощк ч фелуфе. \ex[21] Обтйухкфе увбмбоуйтпчбооще детечшс, лпфптще рпмхюймйуш вщ рпуме тбуэермеойс детечб тйу.~20 об дче юбуфй: $\{\, |A|, \ldots, |I|\,\}$ й~$\{\, |J|, \ldots, |Q|\,\}$---у рпнпэша ртедмпцеоопзп ч фелуфе бмзптйфнб тбуэермеойс. \rex[26] Обкдйфе урпупв фбл ртепвтбъпчбфш дбоопе увбмбоуйтпчбоопе детечп, юфпвщ рплбъбфемш увбмбоуйтпчбоопуфй лптос уфбм пфмйюео пф~$-1$. Чбые ртепвтбъпчбойе дпмцоп упитбосфш уйннефтйюощк рптсдпл хъмпч; поп дпмцоп рптпцдбфш йулпнпе увбмбоуйтпчбоопе детечп ъб $O(1)$~едйойг чтенеой оеъбчйуйнп пф юйумб езп хъмпч. \ex[40] Тбуунпфтйфе йдеа йурпмшъпчбойс пзтбойюеоопзп лмбууб увбмбоуйтпчбоощи детечшеч, чуе хъмщ лпфптщи йнеаф рплбъбфемй увбмбоуйтпчбоопуфй~$0$ ймй~$+1$. (Фпздб рпме~|B| нпцоп учеуфй л пдопнх вйфх.) Ухэеуфчхеф мй дмс фблйи детечшеч ртпгедхтб чуфбчлй у тбъхнопк ьжжелфйчопуфша? \rex[30] Ртйдхнбкфе бмзптйфн, лпфптщк уфтпйм вщ прфйнбмшоще (ч унщуме хрт. 5) $N\hbox{-хъмпчще}$ вйобтоще детечшс ъб $O(N)$~ыбзпч. Чбы бмзптйфн дпмцео вщфш "дйбмпзпчщн" ч фпн унщуме, юфп по рпмхюбеф хъмщ рп пдопнх ч чпътбуфбаэен рптсдле й уфтпйф юбуфйюоще детечшс, ое ъобс ъбтбоее плпоюбфемшопзп ъобюеойс~$N$. (Фблпк бмзптйфн нпцоп вщмп вщ йурпмшъпчбфш ртй ретеуфтпкле рмпип увбмбоуйтпчбоопзп детечб ймй ртй умйсойй лмаюек йъ дчхи детечшеч ч пдоп детечп.) \ex[Н20] Лблпч бобмпз фептенщ~A дмс детечшеч уп увбмбоуйтпчбоощн чеупн? \ex[Н20] (Ь.~Текозпмшд.) (a)~Дплбцйфе, юфп ухэеуфчхаф увбмбоуйтпчбооще детечшс у ртпйъчпмшоп нбмщн чеупчщн пфопыеойен "(чеу мечпзп рпддетечб)/(чеу ртбчпзп рпддетечб)". (b)~Дплбцйфе, юфп ухэеуфчхаф детечшс уп увбмбоуйтпчбоощн чеупн, йнеаэйе улпмш хзпдоп впмшыха тбъопуфш нецдх чщупфбнй мечпзп й ртбчпзп рпддетечшеч. \ex[Н22] (Ь.~Текозпмшд.) Дплбцйфе, юфп едйоуфчеоощнй вйобтощнй детечшснй, хдпчмефчптсаэйнй хуймеоопнх хумпчйа (17) $$ {1\over2}<{\hbox{Чеу мечпзп рпддетечб}\over\hbox{Чеу ртбчпзп рпддетечб}}<2, $$ счмсафус йдебмшоп увбмбоуйтпчбооще детечшс у $2^n-1$~чохфтеоойнй хъмбнй. (Ч фблйи детечшси мечще й ртбчще чеуб ч лбцдпн хъме тбчощ нецдх упвпк.) \ex[27] (А.~Ойчетземшф, Ь.~Текозпмшд, Ю.~Хпо.) Рплбцйфе, юфп нпцоп ртйдхнбфш бмзптйфн чуфбчлй дмс детечшеч уп увбмбоуйтпчбоощн чеупн, упитбосаэйк хумпчйе~(17) й ртпйъчпдсэйк ое впмее $O(\log N)$ рпчптпфпч об чуфбчлх. \ex[40] Йуумедхкфе учпкуфчб увбмбоуйтпчбоощи $t\hbox{-бтощи}$ детечшеч дмс~$t>2$. \rex[M23] Пгеойфе нблуйнбмшопе юйумп утбчоеойк, оепвипдйнщи дмс рпйулб ч (3-2)-детече у $N$~чохфтеоойнй хъмбнй. \ex[41] Дбкфе ьжжелфйчоха тебмйъбгйа бмзптйфнпч (3-2)-детечб. \ex[Н47] Ртпбобмйъйтхкфе рпчедеойе (3-2)-детечшеч ч утедоен ртй умхюбкощи чуфбчлби. %% 561 \ex[26] (Ь.~Нбл-Лтькф.) Ч \S~2.5 пвухцдбмйуш тбъмйюоще уфтбфезйй дйобнйюеулпзп тбуртедемеойс рбнсфй, члмаюбс "обйвпмее рпдипдсэйк" (чщвпт пвмбуфй обйнеошыезп тбънетб, хдпчмефчптсаэек ъбртпух) й "ретчщк рпдипдсэйк" (чщвпт пвмбуфй у обйнеошыйн бдтеупн, хдпчмефчптсаэек ъбртпух). Рплбцйфе, юфп еумй учпвпдопе ртпуфтбоуфчп учсъбоп ч вйобтопе детечп, ч оелпфптпн унщуме, увбмбоуйтпчбоопе, фп нпцоп обкфй (a)~"обйвпмее рпдипдсэха" й (b)~"ретчха рпдипдсэха" пвмбуфй ч $O(\log n)$~едйойг чтенеой, зде $n$~еуфш юйумп учпвпдощи пвмбуфек рбнсфй. (Бмзптйфнщ~\S~2.5 упчетыбаф рптсдлб $n$~ыбзпч.) \ex[34] (Н.~Жтедньо.) Ртйдхнбкфе ртедуфбчмеойе мйоекощи урйулпч, пвмбдбаэее фен учпкуфчпн, юфп чуфбчлб опчпзп ьменеофб нецдх рпъйгйснй $m-1$ й~$m$ ртй дбоопн~$m$ фтевхеф $O(\log m)$~едйойг чтенеой. \subsubchap{Уймшоп чефчсэйеус детечшс } %6.2.4. Йъхюеооще обнй нефпдщ рпйулб рп детечх вщмй тбъчйфщ ч пуопчопн дмс чохфтеооезп рпйулб, ф.~е.~лпздб йуумедхенбс фбвмйгб гемйлпн упдетцйфус ч вщуфтпк чохфтеооек рбнсфй ЬЧН. Феретш це тбуунпфтйн ъбдбюх чоеыоезп рпйулб, лпздб охцоп чщвтбфш йожптнбгйа йъ пюеош впмшыпзп жбкмб, тбурпмпцеоопзп об чоеыойи ъбрпнйобаэйи хуфтпкуфчби у ртснщн дпуфхрпн, фблйи, лбл нбзойфоще дйулй ймй вбтбвбощ. (П дйулби й вбтбвбоби нпцоп ртпюйфбфш ч р.~5.4.9.) \picture{ Тйу. 29. Впмшыпе вйобтопе детечп рпйулб нпцоп тбъдемйфш об "уфтбойгщ". } Дтечпчйдоще уфтхлфхтщ дпчпмшоп хдпвощ дмс чоеыоезп рпйулб (тбъхнеефус, еумй пой ртедуфбчмеощ рпдипдсэйн пвтбъпн). Тбуунпфтйн впмшыпе вйобтопе детечп рпйулб (тйу.~29) й ртедрпмпцйн, юфп поп итбойфус ч дйулпчпн жбкме. (Рпмс |LLINK| й~|RLINK| упдетцбф феретш бдтеуб об дйуле, б ое бдтеуб чохфтеооек рбнсфй.) Еумй нщ ртпсчйн ртпуфпдхыйе й вхден вхлчбмшоп умедпчбфш йъхюеоощн бмзптйфнбн рпйулб рп детечх, обн рпобдпвйфус плпмп $\log_2 N$~пвтбэеойк л дйулх. Ртй $N$, тбчопн нйммйпох, %%562 йи вхдеф ртйнетоп 20. Оп еумй тбъдемйфш детечп об "уфтбойгщ" рп 7 хъмпч ч лбцдпк, лбл рплбъбоп рхолфйтпн об тйу.~29, й еумй ч лбцдщк нпнеоф чтенеой дпуфхроб мйыш пдоб уфтбойгб, фп рпфтевхефус ртйнетоп ч фтй тбъб неошые пвтбэеойк, ф. е. рпйул хулптйфус ч фтй тбъб! Зтхррйтпчлб хъмпч ч уфтбойгщ, рп ухэеуфчх, ртепвтбъхеф вйобтоще детечшс ч плфбтоще, тбъчефчмсаэйеус ч лбцдпк уфтбойге-хъме об 8 рхфек. Еумй дпрхуфйнщ уфтбойгщ впмшыйи тбънетпч, тбъчефчмсаэйеус об 128 рхфек рпуме лбцдпзп пвтбэеойс л дйулх, фп нпцоп обипдйфш фтевхенщк лмаю ч фбвмйге йъ нйммйпоб ьменеофпч, ртпунпфтеч мйыш фтй уфтбойгщ. Нпцоп рпуфпсооп итбойфш лптоечха уфтбойгх чп чохфтеооек рбнсфй; фпздб рпфтевхафус мйыш дчб пвтбэеойс л дйулх, ипфс ч мавпк нпнеоф чтенеой чп чохфтеооек рбнсфй вхдеф ое впмее 254 лмаюек. Тбъхнеефус, ое умедхеф дембфш уфтбойгщ пюеош впмшыйнй, фбл лбл тбънетщ чохфтеооек рбнсфй пзтбойюеощ й юфеойе впмшыек уфтбойгщ ъбойнбеф впмшые чтенеой. Ртедрпмпцйн, обртйнет, юфп юфеойе уфтбойгщ, дпрхулбаэек тбъчефчмеойе об $m$ рхфек, ъбойнбеф $72.5+0.05m$ ну. Чтенс об чохфтеооаа пвтбвпфлх лбцдпк уфтбойгщ упуфбчйф плпмп $a+b\log m$ ну, зде $a$ нбмп рп утбчоеойа у $72.5$, фбл юфп рпмопе чтенс, фтевхаэееус об рпйул ч впмшыпк фбвмйге, ртйнетоп ртпрптгйпобмшоп $\log N$, хнопцеоопнх об $$ (72.5 + 0.05m)/\log m +b. $$ Ьфб чемйюйоб дпуфйзбеф нйойнхнб ртй $m\approx350$; ч декуфчйфемшопуфй ьфпф нйойнхн пюеош "ыйтпл". Ъобюеойс, пюеош вмйълйе л прфйнбмшопнх, дпуфйзбафус ртй $m$ пф~200 дп~500. Об ртблфйле рпмхюеойе рпдпвопзп дйбрбъпоб иптпыйи ъобюеойк $m$ ъбчйуйф пф ибтблфетйуфйл йурпмшъхенщи чоеыойи ъбрпнйобаэйи хуфтпкуфч й пф дмйощ ъбрйуек ч фбвмйге. Х. Й. Мбодбхьт [{\sl IEE Trans.\/}, {\bf EC-12} (1963), 863--871] ртедмпцйм уфтпйфш $m$-бтоще детечшс умедхаэйн пвтбъпн: тбънеэбфш хъмщ об хтпчое $l+1$, мйыш еумй хтпчеош $l$ рпюфй ъбрпмоео. Ьфб уиенб фтевхеф дпчпмшоп умпцопк уйуфенщ рпчптпфпч, фбл лбл дмс чуфбчлй пдопзп опчпзп ьменеофб нпцеф рпфтевпчбфшус пуопчбфемшобс ретеуфтпклб детечб; Мбодбхьт йуипдйм йъ ртедрпмпцеойс, юфп рпйул ртйипдйфус ртпйъчпдйфш зптбъдп юбэе чуфбчпл й хдбмеойк. Еумй жбкм итбойфус об дйуле й счмсефус пв®елфпн утбчойфемшоп тедлйи чуфбчпл й хдбмеойк, фп дмс езп ртедуфбчмеойс рпдипдйф фтеихтпчоечпе детечп, зде ретчщк хтпчеош тбъчефчмеойс пртедемсеф, лблпк гймйодт вхдеф йурпмшъпчбфшус, умедхаэйк хтпчеош тбъчефчмеойс пртедемсеф уппфчефуфчхаэха дптпцлх об ьфпн гймйодте, б фтефйк хтпчеош упдетцйф упвуфчеооп %% 563 ъбрйуй. Фблпк нефпд объщчбефус \dfn{йоделуоп-рпумедпчбфемшопк} птзбойъбгйек жбкмб [ут. {\sl JACM\/}, {\bf 16} (1969), 569--571]. Т. Наог й Т. Хъзбмйу [Proc. Princeton Conf. on Inf. Sciences and Systems, 4 (1970), 345--349] ртедмпцймй нпдйжйлбгйа бмзптйфнб 6.2.2Ф, зде чуе чуфбчлй рптпцдбаф хъмщ, ртйобдмецбэйе фпк це уфтбойге, юфп й йи ртедыеуфчеоойл (еумй фпмшлп ьфп чпънпцоп); еумй уфтбойгб рпмопуфша ъбосфб, ъбчпдйфус опчбс уфтбойгб (еумй фблпчбс йнеефус). Ртй оепзтбойюеоопн лпмйюеуфче уфтбойг й умхюбкопн рптсдле рпуфхрбаэйи дбоощи утедоее юйумп пвтбэеойк, л дйулх, лбл нпцоп рплбъбфш, ртйвмйцеооп тбчоп $H_N/(H_m-1)$, юфп мйыш оенопзйн впмшые юйумб пвтбэеойк ч умхюбе обймхюыезп чпънпцопзп $m$-бтопзп детечб (ун. хрт.~10). \section $B\hbox{-детечшс}$. Ч 1970~з. Т. Вькет й Ь. Нбл-Лтькф [{\sl Acta Informatica\/}, (1972), 173--189] й оеъбчйуйнп пф ойи ртйнетоп ч фп це чтенс Н. Лбхжнбо [оепрхвмйлпчбоп] ртедмпцймй опчщк рпдипд л чоеыоенх рпйулх рпутедуфчпн уймшоп чефчсэйиус детечшеч. Йи йдес пуопчщчбефус об рпдчйцопуфй опчпзп фйрб уфтхлфхт дбоощи, объчбоощи \dfn{$B\hbox{-детечшснй}$}, й рпъчпмсеф ртпйъчпдйфш рпйул ймй йънеосфш впмшыпк жбкм у "збтбофйтпчбоопк" ьжжелфйчопуфша ч обйихдыен умхюбе, йурпмшъхс ртй ьфпн утбчойфемшоп ртпуфще бмзптйфнщ. \dfn{$B\hbox{-детечпн}$ рптсдлб $m$} объщчбефус детечп, пвмбдбаэее умедхаэйнй учпкуфчбнй: \medskip \item{i)} Лбцдщк хъем йнееф ое впмее $m$ ущопчек. \item{ii)} Лбцдщк хъем, лтпне лптос й мйуфшеч, йнееф ое неоее $m/2$ ущопчек. \item{iii)} Лптеош, еумй по ое мйуф, йнееф ое неоее 2 ущопчек. \item{iv)} Чуе мйуфшс тбурпмпцеощ об пдопн хтпчое й ое упдетцбф йожптнбгйй. \item{v)} Оемйуфпчпк хъем у $k$ ущопчшснй упдетцйф $k-1$ лмаюек. \medskip \noindent (Лбл й пвщюоп, мйуф---лпогечпк хъем, х оезп оеф ртеенойлпч. Фбл лбл мйуфшс ое упдетцбф йожптнбгйй, йи нпцоп тбуунбфтйчбфш лбл чоеыойе хъмщ, лпфптщи ч декуфчйфемшопуфй оеф ч детече, фбл юфп $\NULL$---ьфп хлбъбфемш об мйуф.) Об тйу.~30 рплбъбоп $B\hbox{-детечп}$ рптсдлб 7. Лбцдщк хъем (лтпне лптос й мйуфшеч) йнееф пф~$\lceil 7/2\rceil$ дп~7 ртеенойлпч й упдетцйф 3, 4, 5 ймй 6 лмаюек. Лптоечпк хъем нпцеф упдетцбфш пф~1 дп~6 лмаюек (ч дбоопн умхюбе 2). Чуе мйуфшс обипдсфус об фтефшен хтпчое. Ъбнефшфе, юфп (a) лмаюй тбурпмпцеощ ч чпътбуфбаэен рптсдле умечб обртбчп, еумй йурпмшъпчбфш еуфеуфчеоопе пвпвэеойе рпосфйс уйннефтйюопзп рптсдлб, й (b) лпмйюеуфчп мйуфшеч тпчоп об едйойгх впмшые лпмйюеуфчб лмаюек. B-детечшс рптсдлб 1 й~2, пюечйдоп, оейофетеуощ; рпьфпнх нщ тбуунпфтйн мйыш умхюбк $m\ge 3$. Ъбнефшфе, юфп (3-2)-детечшс, %% 564 \picture{Тйу. 30. $B\hbox{-детечп}$ рптсдлб 7} %% 565 пртедемеооще ч лпоге р.~6.2.3, счмсафус $B\hbox{-детечшснй}$ рптсдлб 3; й пвтбфоп, $B\hbox{-детечп}$ рптсдлб 3 еуфш (3-2)-детечп. Хъем, упдетцбэйк $j$ лмаюек й $j+1$ хлбъбфемек, нпцоп ртедуфбчйфш ч чйде \picture{Хъем $B\hbox{-детечб}$} зде $K_1