2. Pavúčí sklad vzorové riešenie

Táto úloha v skutočnosti popisovala jeden veľmi známy a skúmaný problém informatiky – binárne vyhľadávacie stromy. Cieľom týchto stromov je skutočne ukladanie a vyhľadávanie čísel (alebo iných hodnôt) a sú často používané v rôznych aplikáciách. Ich rozšírenosť ilustruje aj to, že v množstve programovacích jazykov sú ich natívnou súčasťou (napr. set v C++ alebo dict v Pythone).

Jednotlivé podúlohy vás navádzali na riešenie skutočných problémov, ktoré sa pri binárnych stromoch riešia – hľadanie, vkladanie a vymazávanie hodnôt. A riešenia, ktoré si prezentuje v tomto vzorovom riešení pomerne presne zodpovedajú riešeniam, ktoré sa aj v skutočnosti používajú. Ak ste teda riešili túto úlohu, môžete sa cítiť ako skutočný informatici :)

Začnime tým, že si zopakujeme, čo vieme o Jonášovej pavučine. V Jonášovej pavučine sa nachádza niekoľko mušiek, každá z nich má inú váhu. Naviac, z každej mušky vychádza práve jedno (okrem mušky úplne navrchu) vlákno dohora a najviac dve vlákna dodola – jedno doprava a jedno doľava. A pre každú mušku platí, že všetky mušky, ktoré sú zavesené pod ňou naľavo sú ľahšie ako táto muška a všetky mušky, ktoré sú zavesené pod ňou napravo sú ťažšie ako táto muška. A keďže muška na vrchu siete je špeciálna (lebo z nej nevychádza vlákno dohora), voláme ju Miška.

Podúloha a.

Jonáš stojí na vrchu pavučiny a chce nájsť najľahšiu mušku, ktorú má v pavučine chytenú. Ako to spraví?

Jonáš začína pri muške Miške. Čo vieme o tejto muške? To čo o všetkých ostatných – naľavo od nej sú mušky ľahšie a napravo od nej mušky ťažšie. Ak sa chce teda Jonáš dostať k najľahšej muške, určite musí ísť doľava, vpravo sú totiž všetky mušky ťažšie.

Posuňme teda Jonáša po ľavom vlákne k najbližšej muške. Uvedomme si však, že pre túto mušku platí tá istá vlastnosť a Jonáš je preto v rovnakej situácii – ak pôjde doľava, pôjde k ľahším muškám, ak doprava, tak k muškám ťažším. Opäť sa teda musí posunúť po ľavom vlákne.

Táto situácia sa bude následne opakovať. Od každej mušky bude chcieť ísť Jonáš doľava, lebo vľavo sa nachádzajú ľahšie mušky. Zastaví sa až vtedy, keď doľava už nebude môcť ísť – z mušky pri ktorej stojí nevedie ľavé vlákno. Možno z nej aj vedie vlákno doprava, vpravo sú však iba ťažšie mušky a k tým sa Jonáš nechce dostať. Preto táto muška musí byť najľahšia v celej pavučine.

Všimnite si, že táto situácia mohla nastať kedykoľvek, kľudne aj pri muške Miške. Je ale jasné, že ak z Mišky nevedie vlákno doľava, Miška je najľahšie muška v pavučine.

Jonášov postup: začínajúc pri muške Miške sa vždy posuň dodola po ľavom vlákne k najbližšej muške. Ak v nejakom momente stojíš pri muške, z ktorej doľava už vlákno nevedie, táto muška je najľahšia v celej sieti.

Podúloha b.

V tejto podúlohe chce Jonáš nájsť najľahšiu mušku, ktorá je ťažšia ako muška Miška.

Jonáš opäť začína pri muške Miške. Ktorým smerom sa má vydať? Ak pôjde doľava, dostane sa iba k ľahším muškám, čo nie je dobre. Preto musí ísť vláknom doprava.

Po prvom presune je však Jonáš medzi muškami, ktoré sú všetky ťažšie ako Miška. A k ľahším sa už späť nedostane. Keďže išiel doprava od Mišky, všetky mušky, ktoré stretne budú ťažšie ako ona. Ktorú mušku teda teraz hľadá? No predsa tú najľahšiu. A to, ako nájsť najľahšiu mušku, sme si ukázali už v podúlohe a..

Jediné, čo musí Jonáš teraz robiť je posúvať sa ľavým vláknom dodola, až kým nenarazí na mušku, z ktorej už ľavé vlákno nevedie. Toto bude najľahšia muška ťažšia ako Miška.

Jonášov postup: v prvom kroku sa pohni doprava od Mišky. Následne choď už celý čas iba doľava, až kým nenarazíš na mušku, z ktorej vlákno doľava nevedie. To bude hľadaná muška.

Podúloha c.

Jonáš hľadá v pavučine mušku s váhou presne \(x\). Poprípade má zistiť, že taká muška sa v pavučine nenachádza.

Ako prvé by Jonáš mohol overiť, či vlastne nehľadá mušku Mišku. Porovná teda váhu Mišky s číslom \(x\). Ak sa rovnajú, tak je rád, lebo našiel mušku, ktorú hľadal. Čo však, ak sa nerovnajú?

V takom prípade sa bude musieť pohnúť buď doľava alebo doprava. No a o muškách naľavo vieme, že sú ľahšie ako Miška a o muškách napravo, že sú ťažšie ako Miška. Pozrieme sa teda, či hľadané \(x\) je väčšie alebo menšie ako Miškina váha. Ak je väčšie, pôjdeme doprava, kde sa nachádzajú väčšie čísla, ak je menšie, tak naopak doľava.

Po prvom posunutí, ktoré je navyše jednoznačné, sa ocitáme pri muške s váhou \(y\). Porovnajme teraz toto číslo s číslom \(x\). Ak \(y = x\), tak Jonáš našiel mušku, ktorú hľadal a už sa nemusí viac hýbať. Ak \(x < y\), tak hľadaná muška je ľahšia ako muška, pri ktorej aktuálne stojí a teda sa musí pohnúť doľava. A ak \(x > y\), tak hľadaná muška je ťažšia a musí ísť doprava.

Po každom kroku je teda Jonášov postup pevne daný tým, koľko váži muška, pri ktorej stojí. Porovnanie jej váhy a čísla \(x\) mu totiž povie, ktorým smerom sa má vydať. A keďže nikdy nemá na výber, tak sa nemôže pomýliť. Ak sa taká muška v pavučine nachádza, tak ju určite nájde. Čo ale v prípade, že muška s váhou \(x\) v pavučine nie je?

V takom prípade bude Jonáš cestovať pavučinou, až kým sa niečo nepokazí. Presnejšie, až do momentu, keď mu jeho postup neoznámi, že sa má pohnúť po vlákne, ktoré neexistuje. Predstavte si, že stojí pri muške s váhou \(y\) a \(x < y\). Z mušky \(y\) však vlákno doľava nevedie. Jonáš vie, že v takomto prípade muška s váhou \(x\) v sieti nie je. Ak by tam bola, musela by byť naľavo od \(y\), naľavo od \(y\) však nič nie je.

Jonášov postup: nech stojíš pri muške s váhou \(y\). Ak sa \(y = x\), tak si našiel hľadanú mušku. Ak \(x < y\), tak sa musíš pohnúť po vlákne doľava, ak \(x > y\), tak sa musíš pohnúť po vlákne doprava. Ak vlákno, po ktorom sa máš pohnúť neexistuje, tak vieš, že muška s váhou \(x\) sa v sieti nenachádza.

Podúloha d.

V tejto podúlohe chytil Jonáš mušku s váhou \(x\), stojí s ňou na vrchu pavučiny a chce ju niekam zavesiť. Ako to má spraviť?

Začnime tým, že zistíme, či má byť nová muška naľavo alebo napravo od Mišky. Ako to zistíme? Jednoducho porovnáme číslo \(x\) s váhou Mišky. Ak je \(x\) ľahšie, tak novú mušku musí zavesiť doľava, v opačnom prípade doprava.

Keď sa však daným smerom posunie, dostáva sa do rovnakej situácie. Podľa váhy mušky, pri ktorej stojí sa vie jednoznačne rozhodnúť, či má byť nová muška zavesená vľavo alebo vpravo. Uvedomme si naviac, že tento postup je úplne rovnaký ako postup v podúlohe c.. Tiež v podstate hľadáme umiestnenie mušky s váhou \(x\) v pavučine.

Muška s váhou \(x\) sa však v pavučine ešte nenachádza, však ju tam len chceme pridať. Ako sme si však vraveli, pri postupe z podúlohy c. bude Jonáš postupovať pavučinou, až kým nenarazí na situáciu, v ktorej zistí, že sa má pohnúť po vlákne, ktoré neexistuje. V našom prípade je to však presne miesto, kam má zavesiť jeho novú mušku.

Predstavme si, že stojí pri muške s váhou \(y\) a platí \(y < x\), žiadne vlákno doprava však nevedie. Vidíme, že muška \(x\) by mala byť napravo od mušky \(y\). No a keďže napravo nič nie je, môžeme vytvoriť nové vlákno, ktoré pôjde z \(y\) doprava a na jeho konci bude muška s váhou \(x\).

Overme si už len, že celá sieť je po tomto pridaní v poriadku. Stále platí, že z každej mušky vedú dodola najviac dve vlákna. Pridali sme totiž iba jedno vlákno a aj to na miesto, kde chýbalo. Ostáva skontrolovať, že naľavo od každej mušky sú iba ľahšie mušky a napravo iba ťažšie. Pod muškou \(x\) zatiaľ žiadna ďalšia muška nie je zavesená, takže pre ňu to platí. A pre všetky zvyšné, pod ktorými leží muška \(x\) to platí tiež. V každom kroku sme sa totiž hýbali tak, ako keby tam muška \(x\) už bola. Preto muška \(x\) leží vždy na správnej strane.

Jonášov postup: nech stojíš pri muške s váhou \(y\). Ak \(x < y\), tak sa musíš pohnúť po vlákne doľava, ak \(x > y\), tak sa musíš pohnúť po vlákne doprava. Ak vlákno, po ktorom sa máš pohnúť neexistuje, tak ho vytvor a na jeho koniec zaves mušku \(x\).

Podúloha e.

Pavúk Jonáš zjedol jednu z mušiek a teraz stojí na jej mieste. Potrebuje previazať niektoré vlákna a presunúť nejaké mušky tak, aby jeho pavučina opäť spĺňala všetky požadované podmienky.

Ako už naznačovalo zadanie, zložitosť tejto operácie bude závisieť od toho, koľko vlákien vedie dodola z mušky, ktorú Jonáš zjedol. Ak pod muškou, ktorú zjedol už nie je žiadna ďalšia muška, situácia je jednoduchá. Odstránením tejto mušky sa pavučina vôbec nepokazí.

Poďme sa teda pozrieť na to, čo sa stane, keď z tejto mušky viedlo jedno vlákno, pričom je jedno, či viedlo doprava alebo doľava. Nech zjedená muška mala váhu \(x\) a muška nad ňou váhu \(y\). Ďalej predpokladajme, že \(x < y\), teda z mušky \(y\) viedlo doľava vlákno k muške \(x\). Uvedomme si, že všetky mušky vľavo od \(y\) boli menšie ako \(y\). Preto je nám jedno, či z \(x\) viedlo vlákno doľava alebo doprava. Dôležité je, že všetky mušky pod \(x\) sú aj tak menšie ako \(y\). Keď sme odstránili mušku \(x\), z \(y\) vedie doľava jedno prázdne vlákno, kam sa majú pripojiť mušky menšie ako \(y\). A do \(x\) viedlo zdola jedno vlákno, na ktorom sú zavesené mušky ľahšie ako \(y\). Tieto dve vlákna teda môžeme spojiť v jedno, čím dostaneme súvislú pavučinu, v ktorej stále platia všetky vlastnosti.

Ostáva už len najzložitejšia situácia, v ktorej z odstránenej mušky (nech má váhu \(x\)) vedie vlákno aj doľava aj doprava. Teraz už len tak ľahko nevieme vlákna previazať. Z vrchu totiž vedie iba jedno vlákno, ale dodola vedú dve. Bolo by teda fajn na miesto mušky \(x\) dať nejakú inú mušku zo siete. Ktorú?

Zdá sa logické, aby to bola niektorá z mušiek, ktoré ležia pod \(x\). Mušky pod muškou \(x\) sú rozdelené na dve časti – ľahšie mušky, ktoré sú naľavo a ťažšie mušky, ktoré sú napravo. Predstavme si, že vyberieme niektorú z mušiek napravo a dáme ju na miesto mušky \(x\). Keďže sme ju vybrali z pravej časti, vieme, že je ťažšia ako \(x\). To znamená, že mušky naľavo sú ľahšie ako ona. Čo je super, lebo ľahšie mušky majú byť naľavo. Sú však všetky mušky napravo ťažšie ako táto muška?

Keďže sme vyberali ľubovoľnú mušku z pravej časti, tak nie nutne. Akú mušku musíme z pravej časti vybrať, aby všetky zvyšné mušky napravo boli ťažšie ako ona? No predsa tú najľahšiu. Takže najlepším kandidátom na nahradenie mušky \(x\) je najľahšia muška ťažšia ako \(x\). Hľadať takúto mušku však vieme, ukázali sme si to predsa v podúlohe b..

Riešenie je teraz už jednoduché. Jonáš sa od zjedenej mušky \(x\) posunie doprava a potom ide celý čas doľava, až kým nenájde najľahšiu mušku ťažšiu ako \(x\). Túto mušku musí vybrať z pavučiny a dať ju na miesto mušky \(x\). Uvedomme si však, že z tejto novej mušky vedie dodola najviac jedno vlákno. Nemôže z nej totiž viesť vlákno doľava, lebo by nebola najľahšia. Takže ju vieme ľahko z pavučiny vybrať – to ako odstrániť mušku, z ktorej vedú menej ako dve vlákna sme si popísali vyššie.

Na obrázku sú znázornené všetky tri možné situácie. Červený krížik ukazuje, ktorá muška bola zjedená, červené čiary, ukazujú, ktoré nové vlákna budú pridané a červená šipka znamená presunutie mušky na novú pozíciu.

Jonášov postup: ak z mušky, ktorú zješ nevedie dodola žiadne vlákno, nemusíš nič robiť. Ak z nej vedie práve jedno vlákno, toto vlákno napoj na mušku priamo nad zjedenou muškou. V prípade, že zješ mušku, z ktorej vedú dodola obe vlákna, začni tým že nájdeš najľahšiu mušku, ťažšiu ako zjedená muška. To spravíš tak, že sa posunieš najskôr doprava a potom pôjdeš doľava až kým sa už ďalej doľava nebudeš vedieť pohnúť. Zober mušku, pri ktorej stojíš a uprav pavučinu, ako keby si túto mušku zjedol. Vedie z nej najviac jedno vlákno, takže situácia je ľahká. Túto vybranú mušku nakoniec polož na miesto zjedenej mušky.