\input style \chapnotrue \chapno=6 \subchno=2 \subsubchno=2 %% 536 \subsubchap{Яаюкюмяхпнбюммше депебэъ} Рнкэйн врн хгсвеммши мюлх юкцнпхрл бярюбйх б депебн онпнфдюер унпньхе депебэъ онхяйю опх яксвюимшу хяундмшу дюммшу, мн бяе фе ясыеярбсер дняюдмюъ бепнърмнярх онксвхрэ бшпнфдеммне депебн. Бнглнфмн, лш лнцкх аш хгнапеярх юкцнпхрл, йнрнпши б кчанл яксвюе дюер норхлюкэмне депебн, мн, й янфюкемхч, щрн дюкейн ме опнярн. Дпсцни ондунд янярнхр б упюмемхх онкмни дкхмш осрх х пенпцюмхгюжхх депебю бяъйхи пюг, йнцдю дкхмю ецн осрх опебшьюер, яйюфел, $5N\log_2N$. Мн рнцдю б опнжеяяе онярпнемхъ депебю онрпеанбюкняэ аш нйнкн $\sqrt{N/2}$ пенпцюмхгюжхи. Нвемэ нярпнслмне пеьемхе опнакелш онддепфюмхъ унпньецн депебю онхяйю ашкн мюидемн б 1962~ц. дбслъ янберяйхлх люрелюрхйюлх---Ц.~Л.~Юдекэянмнл-Бекэяйхл х Е. Л. Кюмдхянл [{\sl ДЮМ ЯЯЯП\/}, {\bf 146} (1962), 263--266]. Ху лернд рпеасер кхьэ дбсу днонкмхрекэмшу ахрнб мю сгек х мхйнцдю ме хяонкэгсер анкее $O(\log N)$ ноепюжхи дкъ онхяйю он депебс хкх дкъ бярюбйх щкелемрю. Б дюкэмеиьел лш сбхдхл, врн щрнр ондунд рюйфе опхбндхр й наыелс лерндс опедярюбкемхъ опнхгбнкэмшу кхмеимшу \emph{яохяйнб} дкхмш $N$, опхвел йюфдюъ хг якедсчыху ноепюжхи рпеасер кхьэ $O(\log N)$ едхмхж бпелемх: \medskip \item{i)} Мюирх щкелемр он дюммнлс йкчвс. \item{ii)} Опх дюммнл $k$ мюирх $k$-и щкелемр. \item{iii)} Бярюбхрэ б нопедекеммнл леяре щкелемр. \item{iv)} Сдюкхрэ нопедекеммши щкелемр. \medskip \noindent Еякх дкъ кхмеимшу яохяйнб опхмърн онякеднбюрекэмне пюяонкнфемхе, рн ноепюжхх (i) х (ii) асдср щттейрхбмшлх, мн ноепюжхх (iii) х (iv) гюилср онпъдйю $N$ ьюцнб; я дпсцни ярнпнмш, опх хяонкэгнбюмхх ябъгюммнцн пюяонкнфемхъ щттейрхбмш ноепюжхх (iii) х (iv), ю (i) х (ii) онрпеасчр онпъдйю $N$ ьюцнб. Опедярюбкемхе кхмеимшу яохяйнб б бхде депебю онгбнкъер ядекюрэ \emph{бяе вершпе} ноепюжхх гю $O(\log N)$ ьюцнб. Лнфмн рюйфе япюбмхрекэмн щттейрхбмн опнхгбндхрэ дпсцхе ярюмдюпрмше ноепюжхх; мюопхлеп, бнглнфмю йнмйюремюжхъ (яжеокемхе) яохяйю хг $Л$ щкелемрнб ян яохяйнл хг $N$ щкелемрнб гю $O(\log (Л+N))$ ьюцнб. Лернд, дючыхи бяе щрх опехлсыеярбю хяонкэгсер рюй мюгшбюелше "яаюкюмяхпнбюммше депебэъ". Опедшдсыхи юагюж яксфхр пейкюлни яаюкюмяхпнбюммшу депебэеб---щрюйни оюмюжех нр бяеу аед; он япюбмемхч я мхлх бяе дпсцхе яонянаш опедярюбкемхъ дюммшу йюфсряъ сярюпебьхлх. Мн менаундхлн яаюкюмяхпнбюрэ мюье нрмньемхе й яаюкюмяхпнбюммшл депебэъл! Еякх рпеасчряъ ме бяе. вершпе пюяялнрпеммше ноепюжхх, рн мюя лнфер сднбкербнпхрэ %% 537 гмювхрекэмн лемее смхбепяюкэмши, мн опные опнцпюллхпселши лернд. Анкее рнцн, яаюкюмяхпнбюммше депебэъ унпньх кхьэ опх днярюрнвмн анкэьху $N$; рюй. еякх еярэ щттейрхбмши юкцнпхрл, рпеасчыхи $20\log_2N$ едхмхж бпелемх, х мещттейрхбмши юкцнпхрл, рпеасчыхи $2N$ едхмхж бпелемх, рн опх $N<1024$ якедсер хяонкэгнбюрэ мещттейрхбмши лернд. Я дпсцни ярнпнмш, $N$ ме днкфмн ашрэ якхьйнл бекхйн; яаюкюмяхпнбюммше депебэъ ондундър цкюбмшл напюгнл дкъ упюмемхъ дюммшу бн \emph{бмсрпеммеи} оюлърх, ю б о.~6.2.4 лш хгсвхл ксвьхе лерндш дкъ бмеьмху тюикнб я опълшл днярсонл. Рюй йюй ян бпелемел пюглепш бмсрпеммеи оюлърх ярюмнбъряъ бяе анкэье х анкэье, яаюкюмяхпнбюммше депебэъ ярюмнбъряъ бяе анкее бюфмшлх. \dfn{Бшянрю} депебю нопедекъеряъ йюй ецн мюханкэьхи спнбемэ, йюй люйяхлюкэмюъ, дкхмю осрх нр йнпмъ дн бмеьмецн сгкю. \picture{20. Яаюкюмяхпнбюммне ахмюпмне депебн} Ахмюпмне депебн мюгшбюеряъ \dfn{яаюкюмяхпнбюммшл}; еякх бшянрю кебнцн онддепебю йюфднцн сгкю нркхвюеряъ нр бшянрш опюбнцн онддепебю ме анкее вел мю $\pm1$. Мю пхя.~20 онйюгюмн яаюкюмяхпнбюммне депебн я 17 бмсрпеммхлх сгкюлх х бшянрни 5; \dfn{онйюгюрекэ яаюкюмяхпнбюммнярх} опедярюбкем бмсрпх йюфднцн сгкю гмюйюлх $+$, $\cdot$ хкх $-$, врн нрбевюер пюгмнярх бшянр опюбнцн х кебнцн онддепебэеб, пюбмни $+1$, $0$ хкх $-1$ яннрберярбеммн. Тханмюввхебн депебн мю пхя.~8 (о~6.2.1) ъбкъеряъ дпсцхл яаюкюмяхпнбюммшл ахмюпмшл депебнл бшянрш 5, хлечыхл рнкэйн 12 бмсрпеммху сгкнб; анкэьхмярбн онйюгюрекеи яаюкюмяхпнбюммнярх пюбмн $-1$. "Гндхюйюкэмне депебн" мю пхя.~10 (о.~6.2.2) \emph{ме} яаюкюмяхпнбюмн, рюй йюй онддепебэъ сгкнб |AQUARIUS| х |GEMINI| ме сднбкербнпъчр опхмършл нцпюмхвемхъл. Щрн нопедекемхе яаюкюмяхпнбюммнярх опедярюбкъер янани йнлопнлхяя лефдс \emph{норхлюкэмшлх} ахмюпмшлх депебэълх (бяе бмеьмхе сгкш йнрнпшу пюяонкнфемш мю дбсу ялефмшу спнбмъу) %% 538 х \emph{опнхгбнкэмшлх} ахмюпмшлх депебэълх. Онщрнлс слеярмн яопняхрэ, йюй дюкейн лнфер нрйкнмхрэяъ нр норхлюкэмнярх яаюкюмяхпнбюммне депебн? Нйюгшбюеряъ, врн дкхмю ецн онхяйнбнцн осрх .мхйнцдю ме опебшяхр норхлсл анкее вел мю 45\%. \proclaim Ренпелю Ю. (Ц. Л. Юдекэянм-Бекэяйхи х Е. Л. Кюмдхя). Бшянрю яаюкюмяхпнбюммнцн депебю я $N$ бмсрпеммхлх сгкюлх гюйкчвемю лефдс $\log_2(N+1)$ х $1.4404 \log_2(N+ 2)-0.328$. \proof\ Ахмюпмне депебн бшянрш $h$, нвебхдмн, ме лнфер яндепфюрэ анкее вел $2^h$ бмеьмху сгкнб; онщрнлс $N+1\le 2^h$, р.е. $h\ge \lceil \log_2(N+1)\rceil$. Врнаш мюирх люйяхлюкэмне гмювемхе $h$, онярюбхл бнопня он-дпсцнлс: йюйнбн лхмхлюкэмне вхякн сгкнб б яаюкюмяхпнбюммнл депебе бшянрш $h$? Осярэ $T_h$--- рюйне депебн я мюхлемэьхл бнглнфмшл йнкхвеярбнл сгкнб; рнцдю ндмн онддепебн йнпмъ, мюопхлеп кебне, хлеер бшянрс $h-1$, ю дпсцне---хкх $h-1$, хкх $h-2$. Б яхкс нопедекемхъ $T_h$ лнфмн явхрюрэ, врн кебне онддепебн йнпмъ еярэ $T_{h-1}$, ю опюбне---$T_{h-2}$. Рюйхл напюгнл, япедх бяеу яаюкюмяхпнбюммшу депебэеб бшянрш $h$ мюхлемэьее йнкхвеярбн сгкнб хлеер \emph{тханмюввхебн депебн} онпъдйю $h+1$. (Ял. нопедекемхе депебэеб Тханмюввх б о.~6.2.1.) Хрюй, $$ N\ge F_{h+2}-1 > \phi^{h+2}/\sqrt{5}-2, $$ х рпеаселши пегскэрюр онксвюеряъ рюй фе, йюй якедярбхе хг ренпелш 4.5.3F. \proofend Лш бхдхл, врн онхяй б яаюкюмяхпнбюммнл депебе онрпеасер анкее 25 япюбмемхи, рнкэйн еякх депебн янярнхр хг он йпюимеи лепе $F_{27}-1= 196417$ сгкнб. Пюяялнрпхл реоепэ, врн опнхяундхр, йнцдю мнбши сгек бярюбкъеряъ б яаюкюмяхпнбюммне депебн оняпедярбнл юкцнпхрлю 6.2.2Р. Депебн мю пхя.~20 нярюеряъ яаюкюмяхпнбюммшл, еякх мнбши сгек гюилер леярн ндмнцн хг сгкнб \leaf{4}, \leaf{5}, \leaf{а}, \leaf{7}, \leaf{10} хкх \leaf{13}, мн б дпсцху яксвюъу онрпеасеряъ мейнрнпюъ йнппейрхпнбйю. Рпсдмнярх бнгмхйючр, еякх хлееряъ сгек я онйюгюрекел яаюкюмяхпнбюммнярх $+1$, опюбне онддепебн йнрнпнцн оняке бярюбйх ярюмнбхряъ бшье, хкх еякх онйюгюрекэ яаюкюмяхпнбюммнярх пюбем $-1$ х бшье. ярюмнбхряъ кебне онддепебн. Кецйн онмърэ, врн, б ясымнярх, мюя аеяонйнър кхьэ дбю яксвюъ: \picture{Яксвюх бярюбйх б ЮБК-депебн} %% 539 (Дпсцхе "окнухе" яксвюх лнфмн онксвхрэ, гепйюкэмн нрпюгхб щрх дхюцпюллш нрмняхрекэмн бепрхйюкэмни нях.) Анкэьхлх опълнсцнкэмхйюлх $\alpha$, $\beta$, $\gamma$, $\delta$ нангмювемш онддепебэъ я яннрберярбсчыхлх бшянрюлх. Яксвюи 1 хлеер леярн, еякх мнбши щкелемр сбекхвхк бшянрс опюбнцн онддепебю сгкю $B$ я~$h$ дн~$h+1$, ю яксвюи 2---йнцдю мнбши щкелемр сбекхвхбюер бшянрс кебнцн онддепебю сгкю $B$. Бн брнпнл яксвюе лш хлеел кхан $h=0$ (х рнцдю яюл сгек $X$ ъбкъеряъ мнбшл сгкнл), кхан сгек $X$ хлеер дбю онддепебю я яннрберярбеммшлх бшянрюлх $(h-1, h)$ хкх $(h,h--l).$ Опнярше опенапюгнбюмхъ бняярюмюбкхбючр аюкюмя б нанху яксвюъу, янупюмъъ б рн фе бпелъ яхллерпхвмши онпъднй сгкнб $A$, $B$ х $X$. \picture{Онбнпнрш} Б яксвюе 1 лш опнярн онбнпювхбюел депебн мюкебн, опхйпеокъъ $\beta$ й $A$ блеярн $B$. Щрн опенапюгнбюмхе онднамн опхлемемхч юяянжхюрхбмнцн гюйнмю й юкцеапюхвеяйни тнплске, йнцдю лш гюлемъел $\alpha (\beta\gamma)$ мю $(\alpha\beta)\gamma$. Б яксвюе 2 щрн опндекшбюеряъ дбюфдш: ямювюкю $(X,B)$ онбнпювхбюеряъ мюопюбн, гюрел $(A,X)$---мюкебн. Б нанху яксвюъу мсфмн хглемхрэ б депебе кхьэ меяйнкэйн яяшкнй. Дюкее мнбше депебэъ хлечр бшянрс $h+2$, б рнвмнярх рс фе, врн х дн бярюбйх щкелемрю; якеднбюрекэмн, вюярэ депебю, пюяонкнфеммюъ мюд сгкнл $A$ (еякх рюйнбюъ хлееряъ), нярюеряъ яаюкюмяхпнбюммни. \picture{Депебн пхя. 20, яаюкюмяхпнбюммне оняке бярюбйх мнбнцн йкчвю R} %% 540 Мюопхлеп, еякх лш бярюбкъел мнбши сгек мю леярн \leaf{17} (пхя.~20), рн оняке онбнпнрю онксвхл яаюкюмяхпнбюммне депебн, хгнапюфеммне мю пхя.~21 (яксвюи 1). Гюлерэре, врн мейнрнпше хг онйюгюрекеи яаюкюмяхпнбюммнярх хглемхкхяэ. Дерюкх щрни опнжедспш бярюбйх лнфмн пюгпюанрюрэ пюгкхвмшлх яонянаюлх. Мю оепбши бгцкъд аег бяонлнцюрекэмнцн ярейю ме нанирхяэ, рюй йюй менаундхлн гюонлхмюрэ сгкш, йнрнпше асдср гюрпнмсрш бярюбйни. Мхфе опхбндхряъ юкцнпхрл, б йнрнпнл, опхаецмсб й люкемэйни ухрпнярх, лш наундхляъ аег ярейю, бшхцпшбюъ опх щрнл б яйнпнярх. \alg Ю.(Онхяй, я бярюбйни он яаюкюмяхпнбюммнлс депебс.) Хлееряъ рюакхжю гюохяеи, напюгсчыху яаюкюмяхпнбюммне ахмюпмне депебн. Юкцнпхрл онгбнкъер опнхгбеярх онхяй дюммнцн юпцслемрю $K$. Еякх $K$ б рюакхже мер, б ондундъыел леяре б депебн бярюбкъеряъ мнбши сгек, яндепфюыхи $K$. Опх менаундхлнярх опнхгбндхряъ аюкюмяхпнбйю депебю. Опедонкюцюеряъ (йюй х б юкцнпхрле 6.2.2Р), врн сгкш яндепфюр онкъ |KEY|, |LLINK| х |RLINK|. Йпнле рнцн, хлееряъ мнбне онке |B(P)| = онйюгюрекэ яаюкюмяхпнбюммнярх сгкю |NODE(P)|, р. е. пюгмнярэ бшянр опюбнцн х кебнцн онддепебэеб; щрн онке бяецдю яндепфхр $+1$, $0$ хкх~$-1$. Он юдпеяс |HEAD| пюяонкнфем яоежхюкэмши цнкнбмни сгек; |RLINK (HEAD)| сйюгшбюер мю йнпемэ депебю, a |LLINK (HEAD)| хяонкэгсеряъ дкъ упюмемхъ онкмни бшянрш депебю. Дкъ дюммнцн юкцнпхрлю бшянрю ме хлеер гмювемхъ, мн гмюмхе ее онкегмн дкъ опнжедспш йнмйюремюжхх, наясфдючыеияъ мхфе. Лш опедонкюцюел, врн депебн \emph{меосярн}, р.~е. врн |RLINK (HEAD)\NE \NULL|. Б жекъу сднаярбю нохяюмхъ б юкцнпхрле хяонкэгсеряъ нангмювемхе |LINK (ю, П)| йюй яхмнмхл |LLINK (П)| опх $ю=-1$ х йюй яхмнмхл |RLINK (П)| опх $a=+1$. \st[Мювюкэмюъ сярюмнбйю.] Сярюмнбхрэ $|Р|\asg |HEAD|$, $|S|\asg |P|\asg |RLINK (HEAD)|$. [Сйюгюрекэмюъ оепелеммюъ |P| асдер дбхцюрэяъ бмхг он депебс; |S| асдер сйюгшбюрэ мю леярн, цде лнфер онрпеанбюрэяъ аюкюмяхпнбйю; |T| бяецдю сйюгшбюер мю нржю |S|.] \st[Япюбмемхе.] Еякх $K<|KEY(P)|$, рн оепеирх мю \stp{3}; еякх $K>|KEY(P)|$, рн оепеирх мю \stp{4}; еякх $K=|KEY(P)|$, онхяй сдювмн гюбепьем. \st[Ьюц бкебн.] Сярюмнбхрэ $|Q|\asg |LLINK (П)|$. Еякх $|Q|=|\NULL|$, бшонкмхрэ $|Q|\Asg|AVAIL|$ х $|LLINK(P)|\asg|Q|$; гюрел хдрх мю \stp{5}. Б опнрхбмнл яксвюе, еякх $|B(Q)|\NE|0|$, сярюмнбхрэ $|T|\asg|П|$ х $|S| \asg |Q|$. Мюйнмеж, сярюмнбхрэ $|P|\asg|Q|$ х бепмсрэяъ мю \stp{2}. \st[Ьюц бопюбн.] Сярюмнбхрэ $|Q|\asg |RLINK (П)|$. Еякх $|Q|=|\NULL|$, бшонкмхрэ $|Q|\Asg|AVAIL|$ х $|RLINK (П)|\asg |Q|$; гюрел хдрх мю \stp{5}. %% 541 Б опнрхбмнл яксвюе, еякх $|B|(|Q|)\NE 0$, сярюмнбхрэ $|Р|\asg |П|$ х $|S|\asg |Q|$. Мюйнмеж, сярюмнбхрэ |P\asg Q| х бепмсрэяъ мю \stp{2}. (Онякедмчч вюярэ щрнцн ьюцю лнфмн на╝едхмхрэ я онякедмеи вюярэч ьюцю \stp{3}.) \st[Бярюбйю.] (Лш рнкэйн врн опхянедхмхкх мнбши сгек |NODE (Q)| й депебс; реоепэ ецн онкъ мсфдючряъ б мювюкэмни сярюмнбйе.) Сярюмнбхрэ $|KEY|(|Q|)\asg |K|$, $|LLINK(Q)|\asg |RLINK(Q)|\asg\NULL$, $|B(Q)|\asg 0$. \st[Йнппейрхпнбйю онйюгюрекеи яаюкюмяхпнбюммнярх.] (Реоепэ мскебше онйюгюрекх яаюкюмяхпнбюммнярх лефдс |S| х |Q| мсфмн гюлемхрэ мю $\pm1$.) Еякх $K<|KEY(S)|$, сярюмнбхрэ $|R|\asg |P| \asg |LLINK(S)|$; б опнрхбмнл яксвюе сярюмнбхрэ $|R|\asg |П| \asg |RLINK(S)|$. Гюрел мсфмн 0 хкх анкее пюг онбрнпърэ якедсчысч ноепюжхч, онйю |P| ме ярюмер пюбмшл |Q|: еякх $K<|KEY(P)|$, сярюмнбхрэ $|B(P)|\asg -1$ х $|P|\asg |LLINK(P)|$; еякх $K > |KEY(P)|$, сярюмнбхрэ $|B(P)|\asg +1$ х $|P|\asg |RLINK (П)|$. (Еякх $K= |KEY(П)|$, гмювхр, $|P|=|Q|$, х лнфмн оепеирх й якедсчыелс ьюцс.) \st[Опнбепйю яаюкюмяхпнбюммнярх.] Еякх $K<|KEY (S)|$, сярюмнбхрэ $a\asg -1$; б опнрхбмнл яксвюе $a\asg +1$. Реоепэ бнглнфмш рпх яксвюъ: \medskip \item{i)} Еякх $|Б (S)| = 0$ (депебн ярюкн бшье), сярюмнбхрэ $|Б (S)|\asg a$, $|LLINЙ (HEAD)| \asg |LLINЙ(HEAD)| + 1$; юкцнпхрл гюбепьем. \item{ii} Еякх $|B(S)|=-a$ (депебн ярюкн анкее яаюкюмяхпнбюммшл), сярюмнбхрэ $|B(S)|\asg 0$; юкцнпхрл гюбепьем. \item{iii)} Еякх $|B(S)|=a$ (депебн оепеярюкн ашрэ яаюкюмяхпнбюммшл), опх $|B(R)|=a$ хдрх мю \stp{8}, опх $|B(R)|=-a$ хдрх мю \stp{9}. \medskip \noindent(Яксвюи (iii) яннрберярбсер яхрсюжхх, хгнапюфеммни мю дхюцпюлле (1), опх $a=+1$; |S| х |R| сйюгшбючр яннрберярбеммн мю сгкш $A$ х $B$, a $|LINK|(-a, |S|)$ сйюгшбюер мю $\alpha$ х р.д.) \st[Ндмнйпюрмши онбнпнр.] Сярюмнбхрэ $|P|\asg |R|$, $|LINK| (a, |S|)\asg |LINK|(-a, |R|)$, $|LINK|(-a, |R|)\asg |S|$, $|B|(|S|)\asg |B|(|R|)\asg 0$. Оепеирх мю \stp{10}. \st[Дбсйпюрмши онбнпнр.] Сярюмнбхрэ $|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|$. Реоепэ сярюмнбхрэ $$ (|B|(|S|), |B|(|R|))\asg \cases{ (-a, 0), & еякх $|B|(|P|)=a$;\cr ( 0, 0), & еякх $|B|(|P|)=0$;\cr (0, a), & еякх $|B|(|P|)=-a$;\cr } \eqno(3) $$ гюрел $|B|(|P|)\asg 0$. \st[Онякедмхи ьрпху.] [Лш гюбепьхкх аюкюмяхпсчыее опенапюгнбюмхе нр (1) й (2), |P| сйюгшбюер мю мнбши йнпемэ, %% 542 ю |Р|---мю нржю ярюпнцн йнпмъ.] Еякх $|S|=|RLINK(T)|$, рн сярюмнбхрэ $|RLINK(T)|\asg |P|$; б опнрхбмнл яксвюе $|LLINK(T)|\asg |P|$. \algend Щрнр юкцнпхрл днбнкэмн дкхммши, мн пюгдекъеряъ мю рпх опнярше вюярх: ьюцх Ю1--Ю4 (онхяй), ьюцх Ю5--Ю7 (бярюбйю мнбнцн сгкю), ьюцх Ю8--Ю10 (аюкюмяхпнбйю депебю, еякх нмю мсфмю). \picture{22. Онхяй я бярюбйни он яаюкюмяхпнбюммнлс депебс} Лш гмюел, врн дкъ пюанрш юкцнпхрлю рпеасеряъ нйнкн $C\log N$ едхмхж бпелемх опх мейнрнпнл $C$, мн врнаш гмюрэ, опх йюйху $N$ бшцндмн хяонкэгнбюрэ яаюкюмяхпнбюммше депебэъ, мсфмн нжемхрэ бекхвхмс $C$. Юмюкхг якедсчыеи \MIX-опнцпюллш онгбнкъер онднирх й пеьемхч щрнцн бнопняю. \prog Ю.(Онхяй я бярюбйни он яаюкюмяхпнбюммнлс депебс.) Щрю пеюкхгюжхъ юкцнпхрлю Ю хяонкэгсер якедсчыхи тнплюр сгкнб депебю: \picture{Тнплюр сгкю ЮБК-депебю} %% 543 $|rA|\equiv K$, $|rI1|\equiv|P|$, $|rI2|\equiv |Q|$, $|rI3|\equiv |R|$, $|rI4|\equiv S$, $|rI5|\equiv |Р|$. Опнцпюллю дкъ ьюцнб Ю7--Ю9 дсакхпсеряъ, рюй врн бекхвхмю $a$ б ъбмнл бхде б опнцпюлле ме тхцспхпсер. \code B &EQU &0:1 LLINK &EQU &2:3 RLINK &EQU &4:5 START &LDA &Й & 1 &A1. Мювюкэмюъ сярюмнбйю. &ENT5 &HEAD & 1 &$|Р|\asg |HEAD|$. &LD2 &0,5 (RLINK) & 1 &$|Q|\asg |RLINK(HEAD)|$. &JMP &2F & 1 &Мю Ю2 я $|S|\asg |P| \asg |Q|$ 4М &LD2 &0,1 (RLINK) & Я2 &Ю4. Ьюц бопюбн. $|Q|\asg |RLINK(P)|$ &J2Z &5F & Я2 &Мю Ю5, еякх $|Q|=\NULL$. 1М &LDX &0,2 (Б) & C-1 &$|rX|\asg |B(Q)|$. &JXZ &*+3 & C-1 &Оепеунд, еякх $|B(Q)|=0$. &ENT5 &0,1 & D-1 &$|T|\asg |P|$. 2H &ENT4 &0,2 & D &$|S|\asg |Q|$. &ENT1 &0,2 & Я &$|P|\asg |Q|$. &CMPA &1,1 & Я &Ю2. Япюбмемхе. &JG &4Б & Я &Мю Ю4,еякх $K>|KEY(P)|$. &JE &SUCCESS & Я1 &Бшунд, еякх $Й=|KEY(П)|$. &LD2 &0,1 (LLINK) & C1-S &A3. Ьюц бкебн. $|Q|\asg |LLINK(П)|$. &J2NZ &1Б & C1-S &Оепеунд, еякх $|Q|\ne\NULL$. \noalign{20--29 5М (яйнохпнбюрэ гдеяэ ярпнйх 14---23 опнцпюллш 6.2.2 Р) Ю5. Бярюбйю.} 6H &CMPA &1,4 & 1-S &A6. Koppeйр. онйюгюр. яаюкюмяхп. &JL &*+3 & 1-S &Оепеунд, еякх $K< |KEY(S)|$. &LDS &0,4 (RLINK) & E &$|R|\asg |RLINK(S)|$. &JЛП &*+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 &Мю жхйк япюбмемхъ. 4М &JE &7F &F2+1-S &Мю Ю7, еякх $K=|KEY(P)|$. &STX &0,1 (1:1) & F2 &$|B(P)|\asg +1$ (нм ашк $+0$). &LD1 &0,1 (RLINK) & F2 &$|P|\asg |RLINK(P)|$. 1М &CMPA &1,1 &F+1-S &JGE &4B &F+1-S &Оепеунд, еякх $Й \ge |KEY (P)|$. &STX &0,1 (Б) & F1 &$|Б(П)|\asg -1$. &LD1 &0,1 (LLINK) & F1 &$|P|\asg |LLINK(P)|$. &JMP &1B & F1 &Мю жхйк япюбмемхъ. 7М &LD2 &0,4(B) & 1-S &A7. Опнбепйю яаюкюмяхп. $|rI2|\asg |B(S)|$. &STZ &0,4 (Б) & 1-S &$|B(S)|\asg 0$. &CMPA &1,4 &1-S &JG &A7R &1-S &Мю $a=+1$ ондопнцпюллс, еякх $K>|KEY(S)|$. \endcode (гдеяэ еые йнд б 2 йнкнмйх --- опхдекюрэ) % 50--68 %A7L J2P DONE A7R J2N DONE 1-S Бшунд, еякх $|rl2|=-a$. % J2Z 7F J2Z 6F G+J Оепеунд, еякх |B(S)| ашк мскел. % ENT1 0,3 ENT1 0,3 G $|P|\asg|R|$. % LD2 0,3 (Б) LD2 0,3 (Б) G $|rI2|\asg |B(R)|$. % J2N A8L J2P A8R G Мю. Ю8, еякх $|rI2|=a$. \bye