\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