Week 8

jednosmerné spájané zoznamy, obojsmerné spájané zoznamy, stromy, binárne vyhľadávacie stromy

Intermezzo

Motivácia

  • (slide) Minulý týždeň sme začínali našu rozpravu o poliach, ktoré sú užitočné, jednoducho sa s nimi pracuje, sú v pamäti uložené lineárne, ale majú svoje obmedzenia (typ a konštantná veľkosť).

  • (slide) Problém s veľkosťou sme vyriešili v rámci minulotýždňovej prednášky pomocou dynamického údajového typu zoznam, ktorý bude v pamäti zaberať presne toľko miesta, koľko položiek sa v ňom práve nachádza, pričom pomocou jednoduchých CRUD operácií je možné pridávať nové položky a odstraňovať existujúce a tým jeho veľkosť dynamicky meniť.

  • Zoznam, ktorý sme vytvorili sa volá spojkový alebo spájaný, pretože jednotlivé jeho položky sú vzájomne prepojené (spojené) pomocou referencie na ďalší prvok.

  • (slide) Ukázali sme si tiež, že takto reprezentovaný zoznam má svoje výhody aj v iných oblastiach, ako napr. ukladanie súborov na disku alebo pri prenose údajov v sieti. Takýmto spôsobom je možné teoreticky zabezpečiť uloženie alebo prenesenie akéhokoľvek veľkého súboru.

  • (slide) Jediné, čo je možné pokladať za nevýhodu, je zložitosť, ktorú budú mať algoritmy pracujúce s takto reprezentovanými údajmi. Aj napriek tomu, že sme úspešne vyriešili problém s veľkosťou zoznamu, zložitosť je stále lineárna podobne, ako tomu bolo pri práci s poľom (lineárne vyhľadávanie).

  • Dnes sa pozrieme na ďalšie možnosti, ktoré nám dynamické údajové typy prinášajú a aj na to, či pomocou nich nie je možné dosiahnuť lepšiu ako lineárnu zložitosť.

Linked Lists

  • Existuje niekoľko typov spojkových zoznamov. My sme hovorili o základnom z nich, na ktorom sme si predstavili samotnú myšlienku fungovania spojkových zoznamov. Tento typ by sa dal priamo charakterizovať ako jednosmerný (jednoduchý) spojkový zoznam (singly linked list) (slide), pretože obsahuje len jednu referenciu na ďalší prvok zoznamu.

  • Jedným z ďalších typov spájaných zoznamov je obojsmerný spájaný zoznam (doubly linked list) (slide). A na jeho možnosti sa dnes pozrieme.

Doubly Linked List

  • (slide) Ako je vidno z obrázku, tento typ zoznamu obsahuje dve referencie miesto jednej - okrem referencie na nasledujúci prvok obsahuje aj referenciu na predchádzajúci. Tým pádom sa viem z ľubovoľného miesta zoznamu dostať na jeho koniec ako aj na jeho začiatok. Pri definovaní štruktúrovaného typu to teda budeme reprezentovať jednou referenciou navyše (slide).

  • Minule sme hovorili tiež o tom, že takto reprezentované údaje sa dajú s výhodou použiť aj v prípadoch, keď potrebujeme údaje udržiavať v usporiadanej forme. To isté platí aj pre obojsmerné spájané zoznamy. Nie je to však jediný spôsob, ako sa dá tento dynamický údajový typ využiť.

  • Na čo sa teda zvykne takáto reprezentácia údajov používať? Príklady:

    • vypísať zoznam odzadu (trápne :-)

    • história v prehliadači, resp. v ľubovoľnom programe, ktorá umožňuje prechádzať zoznamom dopredu a dozadu

    • prehrávanie audia/videa, kedy nechcem prehrávať len dopredu, ale občas aj dozadu

    • Za špeciálny prípad obojsmerných spájaných zoznamov je možné považovať aj kruhové spájané zoznamy (circular linked lists), v ktorých je koniec zoznamu prepojený s jeho začiatkom. V tomto prípade teda nebude existovať referencia na prvý prvok, ale na ľubovoľný prvok tohto zoznamu. Príkladom využitia môže byť takmer ľubovoľná dosková hra (slide) alebo plánovač v operačnom systéme, ktorý postupne prideľuje čas spusteným procesom, čím zabezpečuje multitasking alebo striedanie hráčov pri hraní ľubovoľnej hre.

  • Ako je to so zložitosťou? Ak by sme tento typ použili na uchovanie údajov v usporiadanom zozname - vedeli by sme dostať lepší výsledok, ako v prípade jednosmerného spájaného zoznamu? Ak sa totiž zamyslíme nad tým, že by sme miesto ukazovateľa na prvý prvok ukazovali na prostredný prvok zoznamu, zrejme by sme získali polovičnú zložitosť.

Trees

  • Zložitosť sa pri rozdelení obojesmerného zoznamu zlepšila - z O(n) na O(n/2). Čo by sa ale stalo, keby sme začali takýmto spôsobom pristupovať ku každému jednému uzlu?

  • To, čo si treba uvedomiť, je, že obojsmerné spájané zoznamy sa nepoužívajú len vo forme lineárnych zoznamov (či už usporiadaných alebo neusporiadaných) - ktorýkoľvek ukazovateľ na nasledujúci alebo predchádzajúci prvok môže ukazovať na ktorýkoľvek iný prvok. To v praxi znamená, že dva uzly, kde jeden ukazoval na druhý a druhý späť na prvý, vôbec nemusia byť takto organizované. Tým síce dôjde k porušeniu podoby lineárneho zoznamu, ale dokážeme vytvoriť topológiu, resp. strom.

  • (slide)

  • Strom vo všeobecnosti reprezentuje hierarchicky usporiadané údaje.

  • Skladá sa z uzlov a listov (koncové uzly).

  • Myšlienku tejto štruktúry údajov si môžeme reprezentovať na nasledujúcich príkladoch:
    • prerekvizity predmetov na univerzite (predmet Programovanie závisí od úspešného ukončenia predmetu Základy programovania a algoritmizácie)
    • prerekvizity inštalačných balíčkov v systémoch, ktoré inštalujú svoj softvér v podobe balíčkov (Linux, JavaScript, Python, …)
    • (slide) pavúk športových zápasov
    • (slide)reprezentácia súborov a priečinkov na disku

Binárny vyhľadávací strom

  • (slide) špeciálny prípad stromu, kde každý uzol má len dvoch potomkov - pravý a ľavý (menší/väčší, pravda/nepravda, …)

  • Ako to bude so zložitosťou? (priemerný prípad O(log n), najhorší prípad O(n)). Aký je to najhorší prípad?

  • Ak by sme odstránili najhorší prípad a vyvážili strom (hĺbka ľavého podstromu aj hĺbka pravého podstromu by boli rovnaké, tak aj najhorší prípad bude O(log n))

Zoo

  • (slide) Príklad reprezentácie binárneho vyhľadávacieho stromu (zoo.c)

Reprezentácia uzla

  • Začneme tým, že zadefinujeme uzol stromu. Ten bude reprezentovaný štruktúrou, ktorá bude vyzerať nasledovne:

Funkcie na vytvorenie uzlov

Inicializovanie stromu

Let’s play

Typ uzla?

  • Ak sa však pozrieme na výsledok, jeho prevedenie nie je úplne najlepšie. Už teraz vieme povedať, že pomocou jedného uzla sa snažíme reprezentovať dva typy informácií - otázku a odpoveď. A pri aktuálnom prevedení využívame len fakt, že odpoveď je vlastne otázka, ktorá nemá žiadnych potomkov (yes/no referencie sú NULL).

  • Otázkou teda je, ako postupovať, ak by sme chceli zabezpečiť, aby uzol fungoval ako akýsi kontajner, ktorý bude držať buď otázku alebo odpoveď.

Union

  • (slide) A union is a special data type available in C that allows to store different data types in the same memory location. You can define a union with many members, but only one member can contain a value at any given time. Unions provide an efficient way of using the same memory location for multiple-purpose.

  • Ak by sme teda chceli použiť union v tomto prípade, použitie by mohlo vyzerať nasledovne:

  • Príklad union-u, ktorý používame aj my, sa nazýva polymorfický (slide) alebo discriminated (rozlíšený). Je to typ použitia union-u, kedy ho použijeme vo vnútri štruktúry a okrem neho sa v ňom nachádza aj člen štruktúry, ktorý identifikuje typ uloženého prvku union-u.

Additional Resources