1. Pokračovanie príbehu s pavúkom Jonášom vzorové riešenie

Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na

Táto úloha voľne nadväzuje na úlohu Pavúčí sklad z prechádzajúceho kola. Odporúčame si preto aspoň letmo prečítať jej zadanie aj vzorové riešenie. Na vyriešenie tejto úlohy to síce nie je nutné, myslíme si však, že vám to vie pomôcť.

Spomínate si ešte na pavúka Jonáša a jeho siete? Ukladal si do nich mušky, ktoré sa mu podarilo chytiť. Dodržiaval pri tom veľmi prísne pravidlá. Z každej mušky viedli dodola najviac dve vlákna – ľavé a pravé. Naviac, pre každú mušku v sieti platilo, že všetky mušky, ktoré boli pod ňou naľavo boli ľahšie ako ona, a všetky mušky, ktoré boli pod ňou napravo boli ťažšie ako ona. Jonášova pavučina teda mohla vyzerať napríklad takto.

Úloha

Keďže Jonáš sa chcel naučiť tkať ešte krajšie siete, vybral sa na skusi do sveta. Ako prvých navštívil svojich bratrancov v Španielsku, kde sa dozvedel, že v móde sú hlboké siete. A keďže nevedel, čo je hĺbka siete, jeho bratranci mu to vysvetlili.

Každá muška v sieti je v nejakej hĺbke. Najvyššia muška v sieti je v hĺbke 0, tie zavesené priamo pod ňou sú v hĺbke 1, tie pod nimi v hĺbke 2 atď.. Presnejšie, muška zavesená priamo pod muškou v hĺbke \(x\) je v hĺbke \(x+1\). Hĺbka siete je potom najväčšia hĺbka, v ktorej je ešte nejaká muška. Na obrázku vyššie teda vidíte sieť hĺbky 3.

1. (2 body) Jonáš by sa chcel pred Španielmi predviesť a čo najrýchlejšie spraviť sieť hĺbky 7. Na začiatku má prázdnu sieť, do ktorej bude postupne pridávať mušky, pričom bude celý čas dodržiavať všetky podmienky uvedené vyššie. Nájdite čo najkratšiu postupnosť mušiek, ktoré keď bude v tomto poradí pridávať do siete, dostane sieť hĺbky 7.

   Pavučinu z prvého obrázku by Jonáš vytvoril, keby mušky pridával v nasledovnom poradí: 42, 29, 15, 68, 3, 35, 55, 47, 24, 30, 100¹. Pri riešení môžete použiť napríklad nasledovný nástroj btv.melezinek.cz/binary-search-tree.html. Keď vedľa tlačidla Insert (po slovensky pridaj) napíšete nejaké číslo a tlačidlo stlačíte, do stromu sa zadané číslo pridá dodržujúc všetky Jonášove podmienky.

Po Španielsku sa Jonáš vybral do Nemecka. Nemecké pavúky sú oveľa praktickejšie a snažia sa tkať svoje siete čo najplytkejšie. Komu by sa totiž chcelo behať celý deň po sieti, keď môže mať všetky mušky poruke, iba pár vlákien od vrchu.

2. (3 body) Jonáš by do svojej pavučiny rád vložil čo najviac mušiek tak, aby vzniknutá sieť mala hĺbku najviac 3. Opäť začína s prázdnou sieťou. Nájdite čo najdlhšiu postupnosť mušiek, ktoré keď bude v tomto poradí pridávať, nevytvorí sieť s hĺbkou 4.

   Rovnako ako v predchádzajúcej úlohe pri riešení použite btv.melezinek.cz/binary-search-tree.html.

Jonáš sa z potuliek svetom vrátil múdrejší. Uvedomil si, že záleží na tom, ako jeho sieť vyzerá. A keďže je od prírody lenivý a za jedlom sa mu chodiť nechce, zapáčil sa mu viac nemecký spôsob stavania pavučín – čím menšia hĺbka, tým lepšie.

Keď sa však pozrel na svoju pavučinu (Obr. 2) zdala sa mu prihlboká. Hlavne vľavo bolo oveľa viac mušiek ako vpravo. Preto mu napadlo presunúť mušku 42 na vrch pavučiny. Výsledok jeho snaženia vidíte na Obr. 3. Teraz ho však zaujíma, či by takýto posun vedel robiť aj všeobecne.

3. (3 body) Navrhnite postup, ktorým bude Jonáš vedieť presunúť mušku priamo naľavo alebo napravo od najvyššej mušky na vrch pavučiny. Nezabudnite zdôvodniť, prečo je vaše riešenie správne.

   Presunutím ľavej mušky dostal Jonáš z obrázku 2 obrázok 3, presunutím pravej mušky mohol zase z obrázku 3 vzniknúť obrázok 2. Dajte si pozor, že obrázok neukazuje všeobecný a ani najťažší prípad, ktorý sa Jonášovi pri presúvaní môže stať.

Ani toto Jonášovi však nestačilo. Prišiel na to, že ak by na vrch pavučiny dal mušku, ktorej váha je v strede medzi všetkými muškami, napravo aj naľavo by bolo rovnako veľa mušiek. V jeho pavučine je to muška s váhou 35, lebo práve päť mušiek je ľahších a práve päť je ťažších. Ako však dostať mušku 35 na vrch siete?

4. (3 body) Jonáš stojí pri niektorej muške v pavučine. Túto mušku by rád presunul na samý vrch pavučiny. Nechce si však pokaziť celú pavučinu a neustále musia v jeho pavučine platiť uvedené podmienky. Pomôžte mu nájsť postup, ktorý mu bude hovoriť, ako preväzovať vlákna tak, aby sa zvolená muška dostala na vrch siete. Nezabudnite, že váš postup musí fungovať pre ľubovoľnú sieť a mušku v nej, nie len pre sieť na obrázku.

Presúvanie mušiek bez konkrétneho plánu je únavné a častokrát zbytočné. Jonáš si preto nakreslil, ako má jeho pavučina vyzerať. Ostáva už len presunúť mušky v jeho sieti. Ako to však spraviť?

5. (4 body) Predstavte si, že máte dva obrázky sietí, ktoré obsahujú tie isté mušky, akurát inak usporiadané. Prvý obrázok ukazuje aktuálny stav siete, druhý ukazuje ako má sieť vyzerať. Popíšte postup, ktorý bude presúvať mušky tak, že zo siete z prvého obrázku vytvorí sieť z druhého obrázku. Samozrejme, váš postup musí fungovať na ľubovoľných dvoch sieťach s tými istými muškam.

   Pri riešení môžete použiť riešenia podúlohy c) a d). Nemôžete však sieť stavať od začiatku. Dovolené máte robiť iba také zmeny, po ktorých bude sieť stále celistvá a bude spĺňať podmienky zadania. To znamená, že môžete presunúť mušku naľavo na vrch siete (ako v podúlohe c)) alebo previazať zopár vlákien, ale nemôžete povedať, že na vrch dáte mušku 27 a zvyšné mušky si zatiaľ niekam odložíte.

   Ako príklad si môžete predstaviť, že Jonášova pavučina vyzerá ako na obrázku 2 a jeho cieľom je ju upraviť tak, aby vyzerala ako na obrázku 1.

---

1. Toto samozrejme nie je jediná postupnosť, ktorá by vytvorila túto pavučinu.↩

Tak ako v predchádzajúcej úlohe, aj tu sme pracovali s binárnymi vyhľadávacími stromami. Tentokrát sme si však mali všímať trochu inú vlastnosť – hĺbku. Poďme si najskôr ukázať ako sa riešili zadané úlohy a na konci vzorového riešenia si povieme, čo má táto úloha spoločné s reálnym použitím takýchto stromov.

Podúloha a.

V tejto podúlohe bolo treba čo najrýchlejšie vytvoriť pavučinu s hĺbkou 7. Najlepšie bolo otvoriť si priloženú stránku a vytvárať nejaké siete. Nie je ťažké prísť na to, že ak chceme použiť čo najmenej mušiek, musí každá nová muška zväčšiť hĺbku siete. Takáto sieť potom bude mať 8 mušiek (netreba zabudnúť na hĺbku 0), čo je naozaj najmenší možný počet.

Ostáva už len nájsť vhodných 8 čísiel – váhy mušiek. Jedno možné riešenie je pridávať vždy mušku, ktorá je ťažšia ako všetky ostatné mušky v sieti. Pri pridávaní takejto mušky totiž Jonáš ide po sieti vždy doprava, pri každom kroku o úroveň hlbšie. Zároveň navštívi všetky mušky a novú pridá napravo od nich, samú do novej hĺbky.

Možná postupnosť mušiek, ktoré má Jonáš do siete pridávať je napríklad: 1, 2, 3, 4, 5, 6, 7 a 8. Samozrejme funguje aj pridávanie mušky, ktorá je ľahšia od ostatných a dokonca sa dá nájsť aj veľa iných riešení. Na obrázku nižšie si môžete pozrieť aj sieť, ktorú by Jonáš dostal, keby mušky pridával v poradí 14, 64, 57, 44, 23, 39, 25 a 37.

Podúloha b.

V tejto podúlohe mal Jonáš presne opačnú úlohu – pridať do siete čo najviac mušiek tak, aby výsledná sieť nemala hĺbku väčšiu ako 3. Na začiatok sme si mohli zobrať obrázok zo zadania. Toto je totiž sieť hĺbky 3, ktorá obsahuje 11 mušiek. A dokonca poznáme aj postupnosť mušiek, ktorých pridanie túto sieť vytvorí.

Je to však najviac mušiek, ktoré v takejto sieti vedia byť? Na obrázku predsa ľahko môžeme vidieť zopár prázdnych miest, do ktorých by sa ešte nejaké mušky zmestili. Presnejšie, v hĺbke 3 by mohli byť ešte 4 ďalšie mušky. Ostáva zistiť, akú váhu by mali mať.

Začnime prvým voľným miestom, ktoré je na obrázku označené A. Čo vieme povedať o váhe mušky, ktorá by mohla byť na tomto mieste? Keďže je naľavo od najvyššej mušky, musí byť ľahšia ako 42. Je však napravo od mušky 29, takže od nej musí byť ťažšia. A musí byť ťažšia aj od mušky 35. Ľubovoľné číslo v intervale \((35, 42)\) by preto malo vyhovovať. A ľahko overíme, že tomu tak naozaj je.

Pre pozíciu B dostaneme interval \((55, 68)\), pre pozíciu C interval \((68,100)\) a pre pozíciu D interval \((100, \infty)\). Ľubovoľné čísla z týchto intervalov budú vyhovovať. Treba ich už len doplniť do postupnosti, teda povedať, kedy má tieto mušky Jonáš pridať.

Môžeme ich dať na začiatok tejto postupnosti? Asi nie. Ak je totiž sieť prázdna, tak pridanie mušky 105 ju zaradí na vrch siete, odkiaľ sa už potom neposunie. Vidíme teda, že ak chce byť muška \(x\) zavesená pod muškou \(y\), tak muška \(y\) musí byť do siete pridaná skôr ako muška \(x\). Naše nové čísla teda musíme zaradiť za čísla, pod ktorými visia. Pri dodržaní tohto pravidla je však jedno kam ich dáme. Jedna možná postupnosť teda je: 42, 29, 15, 68, 3, 35, A=39, 55, 47, 24, 30, B=60, 100, D=105, C=84.

Podúloha c.

V podúlohe c. sme mali načrtnúť postup, ktorý by nám umožnil presunúť mušku, ktorá je zavesená priamo pod najvyššou muškou na vrch siete. Cestou k správnemu riešeniu je nakresliť si dostatočne všeobecne situáciu, ktorá nastáva. Poďme presúvať mušku naľavo na vrch siete. Čo si potrebujeme zaznačiť? Určite mušku \(x\), ktorá je na vrchu, mušku \(y\), ktorá je naľavo od \(x\) a je teda ľahšia. Všetky zvyšné mušky potom vieme rozdeliť do troch skupín – ľahšie ako \(y\) (naľavo od mušky \(y\)), ťažšie ako \(y\) ale ľahšie ako \(x\) (napravo od mušky \(y\)) a ťažšie ako \(x\) (napravo od mušky \(x\)). Mušky v jednej takejto skupine sú vzhľadom na mušky \(x\) a \(y\) úplne rovnaké. Preto aj vo výslednom strome musia všetky skončiť na rovnakej strane od \(x\) a \(y\). Nebudeme preto kresliť všetky tieto mušky zvlášť, ale jednu skupinu si predstavíme ako samostatnú sieť, ktorá bude zavesená pod \(x\) alebo \(y\). Tieto siete si označíme A, B a C.

Vieme, že vo výslednom obrázku musí byť muška \(y\) navrchu. Tak si ju tam nakreslime. Naľavo od nej budú mušky ľahšie. Všetky ľahšie mušky sú však v sieti A. Naľavo od \(y\) preto bude zavesená sieť A. Všetky zvyšné mušky (vrátane \(x\)) sú ťažšie ako \(y\) a preto musia byť od \(y\) napravo.

Navyše vieme, že mušky v sieti \(C\) sú ťažšie ako \(x\) a teda budú napravo od tejto mušky. Ostáva sieť B. O tej vieme, že sú v nej mušky ťažšie ako \(y\) ale ľahšie ako \(x\). Od mušky \(y\) teda musí byť B napravo a od mušky \(x\) naľavo. A práve tieto podmienky spĺňa v našom novom obrázku miesto naľavo od \(x\).

Uvedommte si naviac, že muška \(x\) sa presunula hneď napravo od \(y\). Takže ak by sme chceli vyriešiť opačnú úlohu, kde máme mušku napravo presunúť na vrch, tak stačí spraviť uvedený postup spätne.

Podúloha d.

Jonáš chce na vrch pavučiny presunúť tú mušku v sieti, pri ktorej aktuálne stojí. V predchádzajúcej úlohe sme si ukázali ako dostať mušku susednú s vrchnou mušku na samý vrch. Muška pri ktorej stojí Jonáš však nemusí susediť s vrchnou muškou.

Predstavme si, že k prvému obrázku z príkladu vyššie pridáme mušku \(z\), pod ktorou je na ľavej strane muška \(x\). Ak spravíme uvedené zmeny, muška \(z\) ostane na svojom mieste, akurát na jej ľavej strane bude zrazu muška \(y\). A to isté, ak by boli tieto mušky napravo od \(z\). Pri postupe z podúlohy c. totiž nemeníme nič, čo je vyššie ako mušky, ktoré vymieňame.

Ak si teda zoberieme mušku \(y\), tak tá sa iba posunula na vyššiu úroveň. No a našou úlohou je dostať ju na najvyššiu úroveň – hĺbku 0. Mohli by sme teda tento postup opakovať. Jonáš zakaždým zoberie mušku, ktorú chce dostať na samý vrchol a presunie ju na pozíciu o jedno vyššie pomocou postupu z podúlohy c.. Muška bude postupne stúpať až sa objaví na samom vrchu pavučiny.

Podúloha e.

V podúlohe e. máme dva obrázky sietí. Našou úlohou je navrhnúť postup, vďaka ktorému upravíme prvú sieť na tú druhú. Pritom predpokladáme, že obe siete obsahujú rovnaké mušky.

Vďaka podúlohe d. dokážeme na vrch siete dostať ľubovoľnú mušku. Určite teda vieme spraviť aspoň to, aby sa najvrchnejšie mušky v našich sieťach rovnali. Jednoducho zoberieme sieť, ktorú máme zmeniť, nájdeme v nej mušku, ktorá má byť navrchu a postupne ju presunieme na vrch, tak ako v predchádzajúcej podúlohe.

To však nemusí stačiť. Sieť, ktorú sme vytvorili, sa nemusí rovnať tej, ktorú máme predpísanú ako vzor. Určite sa rovnajú iba vo vrchnej muške. Uvedomme si však nasledovnú vec. V oboch sieťach sú naľavo tie isté mušky. A to isté platí aj o pravej strane. Na vrchu oboch sietí totiž sedí muška \(x\). A všetky ľahšie mušky musia byť naľavo v oboch prípadoch, inak by predsa neplatili zadané podmienky.

Pozrime sa teda na mušky naľavo od \(x\). Tie tvoria vlastnú, menšiu sieť, ktorá je potom pripojená na mušku \(x\). Takže v podstate máme ten istý problém, akurát trochu menší. Máme dve siete (tá naľavo od \(x\) v prvom a tá naľavo od \(x\) v druhom obrázku) a máme ich preusporiadať tak, aby sa rovnali. Naviac si uvedomme, že to, čo robíme v podúlohách c. a d. nemení nič, čo je vyššie ako muška, ktorú presúvame. Takže túto menšiu sieť vieme meniť bez toho, aby sme ovplyvnili mušku \(x\) alebo jej pravú časť.

Tak ako predtým teda môžeme zopakovať náš postup. Pozrieme sa, ktorá muška je naľavo od mušky \(x\) vo vzorovej sieti a túto mušku presunieme na vrch ľavej siete aj v druhom obrázku. Takto docielime, že sa nám rovnajú už dve mušky. Rovnakým spôsobom môžeme však upraviť mušku, ktorá je napravo od mušky \(x\). Takže naše siete sú rovnaké na hĺbke 0 a 1. A teraz môžeme jednoducho pokračovať s muškami v hĺbke 2, 3…

Pár slov na záver

Binárne vyhľadávacie stromy sú pre programátora silný nástroj. Aj tu sa však treba mať na pozore. Ak strom vyzerá tak ako v podúlohe a., všetky operácie na ňom trvajú dlho. Ak sa totiž vrátite k predchádzajúcemu riešeniu, väčšinou sa Jonáš pohyboval toľko krokov, ako hlboký bol zadaný strom. Preto by sa nám páčilo, aby naše stromy vyzerali viac ako stromy v podúlohe b..

To však nie je vždy také jednoduché. Pomôcť si však môžeme takzvanými rotáciami, ktoré ste vymysleli v podúlohe c.. Videli sme, že vďaka nim vieme preskupiť niektoré časti stromu a tak ich lepšie vyvážiť, aby sa nám nestalo, že jedna časť je oveľa hlbšia ako druhá.

To ako presne sa tieto rotácie využívajú je už na ďalšiu úlohu :) Ako však vidíte v podúlohe e., v konečnom dôsledku vďaka nim vieme dostať akýkoľvek tvar, aký si zažiadame.