BST and Unions

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

Záznam z prednášky

Motivation

(slide) Minulý týždeň sme začínali našu rozpravu o poliach. Hovorili sme, ako jednoducho sa s nimi pracuje, a že sú v pamäti uložené lineárne. Rovnako sme však hovorili o tom, že majú obmedzenia, ktorými sú najmä konštantná veľkosť a rovnaký typ údajov v ňom uložených.
(slide) Problém s veľkosťou sme vyriešili v rámci minulotýždňovej prednášky pomocou dátovej štruktúry zoznam, ktorý bude v pamäti zaberať presne toľko miesta, koľko položiek sa v ňom práve nachádza. Ukázali sme si aj implementáciu základných CRUD operácií, pomocou ktorých je možné so zoznamom manipulovať - pridávať nové prvky, odoberať a aktualizovať existujúce a vyhľadávať. Niektorými operáciami je možné priamo meniť veľkosť zoznamu.
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 využitie aj v iných oblastiach, ako je 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ť operácií pracujúcich s touto dátovou štruktúrou. Aj napriek tomu, že sme úspešne vyriešili problém s veľkosťou zoznamu, zložitosť je stále lineárna . Je teda rovnaká ako v prípade práce s poľom.

\[ O(n) \]
Dnes sa pozrieme na ďalšie možnosti, ktoré nám dátová štruktúra zoznam ponúka. A pozrieme sa aj na to, či pomocou nich nie je možné dosiahnuť lepšiu ako lineárnu zložitosť.

Linked Lists

(slide) 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), pretože obsahuje len jednu referenciu na ďalší prvok zoznamu.
(slide) Jedným z ďalších typov spájaných zoznamov je obojsmerný spájaný zoznam (doubly linked list). A na jeho možnosti sa pozrieme bližšie.

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.
(slide) Pri definovaní štruktúry struct node, ktorá bude reprezentovať jeden uzol obojsmerného spojkového zoznamu, pridáme jednu referenciu navyše na predchádzajúci uzol:
```
struct node {
    int data;
    struct node *next;
    struct node *prev;
};
```

Usages of Doubly Linked Lists

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á táto dátová štruktúra 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 alebo sa len v súbore navigovať oboma smermi
- (slide) 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ť:
  - (slide) takmer ľubovoľná dosková hra
  - plánovač v operačnom systéme, ktorý postupne prideľuje čas spusteným procesom, čím zabezpečuje multitasking
  - striedanie hráčov pri hraní ľubovoľnej hry (ale v niektorých hrách ako Uno môže dôjsť priamo aj k zmene smeru hry)

Complexity of Doubly Linked Lists

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ť.
Zložitosť sa v tomto prípade zlepší z O(n) na O(n/2). Stále je však lineárna.

Trees

Č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) Jedna z definícií toho, čo je to strom, znie:

Tree is a widely used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes (Wikipedia)
(slide) Pozrime sa teda na to, ako taký strom vyzerá a z čoho sa skladá.
- Strom reprezentuje hierarchicky usporiadané údaje a skladá sa z uzlov (nodes) navzájom prepojených pomocou hrán (edges).
- Špeciálnym typom uzla sú koncové uzly, ktoré sa nazývajú listy (leaf nodes).
- Každý uzol má svojich potomkov (child nodes alebo descendent nodes) a svojho rodiča (parent node alebo ancestor node). Potomkov môže byť viacero alebo žiadny, ale rodič môže byť max. jeden.
- Hierarchicky najvyššie umiestnený uzol sa nazýva koreň (root). Tento uzol nemá žiadneho rodiča.
- Potomkovia vytvárajú podstromy (subtree).
- Uzol má svoju hĺbku (depth alebo level), ktorá je reprezentovaná ako vzdialenosť (v počte hrán) medzi koreňovým uzlom a dopytovaným uzlom (napr. hĺbka uzla H je 2, pričom hĺbka koreňa je 0).
- Uzol má svoju výšku (height), ktorá je definovaná ako najdlhšia vzdialenosť (v počte hrán) medzi dopytovaným uzlom a listom stromu (napr. výška uzla I je 0, ale výška koreňa stromu je 3).
- Výšku má aj strom a je definovaná ako výška z jeho koreňového uzla. Čo je ekvivalentom hĺbky najhlbšieho uzla.
Aby sme mali predstavu o takto organizovaných údajoch, pozrime sa na niekoľko príkladov:
- prerekvizity predmetov na univerzite (predmet Programovanie závisí od úspešného ukončenia predmetu Základy programovania a algoritmizácie)
- (slide) prerekvizity inštalačných balíčkov v systémoch, ktoré inštalujú svoj softvér v podobe balíčkov (Linux, JavaScript, Python, …). Na slajde sa napr. nachádzajú závislosti balíčka mc.
- (slide) pavúk športových zápasov
- (slide) reprezentácia súborov a priečinkov na disku
```
prog-2024/
├── ps1/
│   ├── playfair.c
│   ├── playfair.h
│   ├── bmp.c
│   ├── bmp.h
│   ├── main.c
│   └── Makefile
└── README
```

Binárny vyhľadávací strom

(slide) Špeciálny prípad stromu, kde každý uzol má najviac dvoch potomkov, sa nazýva binárny vyhľadávací strom.
```
     8
   /   \
  3     10
 / \      \
1   6      14
   / \     /
  4   7   13
```
Potomkovia sa zvyknú označovať ako pravý a ľavý. Vzhľadom na kontext však môžu mať aj iné názvy:
- menší/väčší - v prípade uchovávania uzlov s hodnotami, ktoré je možné vzájomne porovnávať
- pravda/nepravda - v prípade, že strom reprezentuje napr. jednoduchý dialógový strom
Ako to bude so zložitosťou? Tá samozrejme záleží od operácie, ale ak budeme uvažovať operáciu vyhľadávania, tak priemerný prípad bude O(log n) a najhorší prípad O(n). Aký je to najhorší prípad?
```
    3
   /
  2
 /
1
```
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)
```
  2
 / \
1   3
```

Zoo

(slide) Vytvoríme si jednoduchú implementáciu hry Zoo ako ukážku vytvorenia a manipulácie s binárnym vyhľadávacím stromom. Pravidlá hry sú veľmi jednoduché: počítač sa bude snažiť uhádnuť zviera, ktoré si hráč myslí. Bude sa pýtať otázky, na ktoré môže hráč odpovedať iba áno alebo nie.
(slide) Pomocou BST vytvoríme práve znalosť počítača. Jednotlivé uzly budú reprezentovať otázky a listy stromu budú reprezentovať samotné zvieratá. Ukážka BST, pomocou ktorého bude vedieť počítač rozpoznať líšku, kapra a holuba, sa nachádza na slajde.
```
     Má to štyri nohy?
           /    \
         yes     no
        /          \
      líška   Vie plávať?
                 /    \
               yes     no
              /          \
           kapor        holub
```

The Node

Začneme vytvorením štruktúry, ktorá bude reprezentovať uzol BST. Vzhľadom na BST bude mať štruktúra tieto tri prvky:
- data - reťazec, ktorý bude reprezentovať otázku alebo odpoveď
- yes - referencia na ďalší uzol/podstrom po odpovedi áno, a
- no - referencia na ďalší uzol/podstrom po odpovedi nie.

(slide) Štruktúra bude vyzerať nasledovne:

struct node {
    char* data;
    struct node* yes;
    struct node* no;
};

Creating a New Node

(slide) Prvú funkciu, ktorú urobíme, sa bude volať create_node(). Pomocou tejto funkcie vytvoríme nový uzol. Jej parametrom bude len reťazec - teda buď otázka alebo odpoveď. Prepojenie uzlov bude závisieť od aktuálneho kontextu.

Zdrojový kód funkcie môže vyzerať napríklad takto:

struct node* create_node(char* data){
    struct node* node = calloc(1, sizeof(struct node));
    node->data = data;
    node->yes = NULL;
    node->no = NULL;

    return node;
}

BST Initialization

Keď máme vytvorenú funkciu na vytváranie uzlov, môžeme inicializovať BST. Inicializujeme ho do stavu, ktorý je zobrazený na predchádzajúcom obrázku. Pre vyššiu zreteľnosť budem stále vychádzať len z koreňa stromu (uzol root).

int main(){
    struct node *root = NULL;

    // init
    root = create_node("Ma to styri nohy?");
    root->yes = create_node("liska");
    root->no = create_node("Vie plavat?");
    root->no->yes = create_node("kapor");
    root->no->no = create_node("holub");
}

Let’s Play!

Začneme tým, že vytvoríme jednoduchý dialóg, pomocou ktorého budeme vedieť prejsť BST odhora až nadol.

struct node* ptr = root;
char answer;

while(ptr != NULL){
    // print content
    printf("%s\n", ptr->data);

    // read answer
    scanf(" %c", &answer);
    if(answer == 'a'){
        ptr = ptr->yes;
    }else{
        ptr = ptr->no;
    }
}

Keď program preložíme a spustíme, vieme otestovať prechod stromu cez všetky jeho vetvy jednoduchým odpovedaním “a” na áno alebo čímkoľvek iným na nie.
Teraz urobíme malú modifikáciu. Tento cyklus necháme prechádzať dovtedy, pokiaľ sa v položke .data bude nachádzať otázka. Ak sa bude jednať o uzol s odpoveďou, cyklus a teda aj program ukončíme.
To, či sa jedná o otázku alebo odpoveď, zistíme podľa toho, či sa jedná o list alebo uzol. Ak sa jedná o list, má referencie .yes aj .no nastavené na NULL. To môžeme overiť buď vytvorením funkcie is_leaf(), ktorá dostane ako parameter dotyčný uzol alebo vytvorením samostatnej premennej is_leaf s vhodným výrazom:
```
// is_leaf() as a function
bool is_leaf(struct node* node){
    return node->yes == NULL && node->no == NULL;
}

// is_leaf as a local variable
bool is_leaf = node->yes == NULL && node->no == NULL;
```

Program teda upravíme nasledovne:

// let's play
struct node* ptr = root;
char answer;

// find the leaf/animal
while(!is_leaf(ptr)){
    // print content
    printf("%s\n", ptr->data);

    // read answer
    scanf(" %c", &answer);
    if(answer == 'a'){
        ptr = ptr->yes;
    }else{
        ptr = ptr->no;
    }
}

Ak program spustíme teraz, vieme opäť prejsť jeho vetvami, ale program sa ukončí vždy, keď bude mať vypísať list stromu. Rozšírime teda program tak, aby sa po skončení cyklu opýtal na príslušné zviera a na základe odpovede hráča zhodnotil situáciu:
```
printf("Je to %s?\n", ptr->data);
scanf(" %c", &answer);
if(answer == 'a'){
    printf("Ta ja som genius\n");
}else{
    printf("Ta ja som sunka\n");
}
```
Keď hru spustíme, bude sa správať tak, ako sa má - počítač sa bude pekne pýtať podľa rozhodovacieho stromu, ktorý má uložený v BST. Nakoniec aj zareaguje podľa toho, či uhádol alebo neuhádol myslené zviera.

What Type is the Node?

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).
Ak by sme sa teda snažili reprezentovať osobitne otázku a osobitne odpoveď, resp. zviera samotné, tak otázka by vyzerala rovnako ako aktuálna štruktúra struct node, resp. s drobrnými úpravami v pomenovaní:
```
struct question {
    char* question;
    struct question* yes;
    struct question* no;
};
```
A na reprezentáciu odpovede by sme si vystačili s reťazcom char*:
```
char* animal;
```
Ako teda postupovať, ak by sme chceli zabezpečiť, aby uzol fungoval ako akýsi kontajner, ktorý bude vedieť držať buď otázku alebo odpoveď?

The Union

(slide) Odpoveďou na položenú otázku je union.
Jedna z definícií znie:

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. (Tutorials Point)

How It Works?

(slide) Pozrime sa teda na to, ako sa s úniami pracuje. Pre ilustráciu budeme pracovať s reprezentáciou IP adries.
IP adresu vo verzii 4 poznáme ako kombináciu 4 oktetov, pričom jeden oktet má veľkosť 8b. IPv4 adresa teda v pamäti zaberá 4B.
(slide) Zaujímavé je napr. to, ako rozlične vieme použiť príkaz ping na overenie dostupnosti príslušnej adresy. Ten totiž okrem nám najviac známeho formátu ponúka aj rozličné iné zápisy:
- dot decimal - 127.0.0.1
- dot hexa - 0x7F.0x00.0x00.0x01
- dot octal - 0177.0000.0000.0001
- hexa number - 0x7F000001
- decimal number - 2130706433
- octal number - 017700000001
Ak by sme chceli riešiť jednotlivé reprezentácie “na striedačku”, potrebovali by sme si vytvoriť niekoľko konverzných funkcií. Nebolo by ich síce nutne veľa, pretože kus roboty by spravili aj funkcie ako printf() a scanf(). Tie by nám však pomohli len medzi konverziami formátu výstupu jednej hodnoty. Ako sa však dostať k jednotlivým oktetom?
A tu sa dostávame pomaly k úniám. Ak by sme sa snažili IP adresu reprezentovať číslom, vystačili by sme si s typom uint32_t z knižnice stdint.h:
```
uint32_t ipv4;
ipv4 = 2130706433; // 0x7F000001, 017700000001
```

Ak by sme chceli s IP adresou pracovať na úrovni jej oktetov, mohli by sme vytvoriť štruktúru:

struct ipv4 {
    uint8_t d;
    uint8_t c;
    uint8_t b;
    uint8_t a;
};

struct ipv4 ipv4 = {
    .a = 127,
    .b = 0,
    .c = 0,
    .d = 1
};

alebo jednorozmerné pole štyroch bytov:
```
uint8_t octets[4] = { 1, 0, 0, 127 };
```
Únia nám však umožňuje použiť všetky tieto prístupy naraz, pretože ako definícia hovorí, môže obsahovať mnoho členov (ako štruktúra), ale údaje z nej môžeme vytiahnuť vždy len prostredníctvom jedného nich.

Únia pre reprezentáciu IP adresy teda môže v jazyku C vyzerať nasledovne:

union ip {
    uint32_t as_number;
    uint8_t as_octets[4];
    struct {
        uint8_t d;
        uint8_t c;
        uint8_t b;
        uint8_t a;
    } as_struct;
};

Poznámka

Môžete si všimnúť, že štruktúra v únii nemá názov, ale používa rovno názov položky, cez ktorú bude prístupná. V princípe sa jedná o alternatívny zápis tomuto:

union ip {
    uint32_t as_number;
    uint8_t as_octets[4];
    struct ipv4 as_struct;
};

Použili sme teda anonymnú štruktúru ako súčasť únie. Dokonca nie je nutné anonymnú štruktúru spájať so žiadnou položkou. V tom prípade budú položky štruktúry dostupné priamo, ako keby boli súčasťou únie:

union ip {
    uint32_t as_number;
    uint8_t as_octets[4];
    struct {
        uint8_t d;
        uint8_t c;
        uint8_t b;
        uint8_t a;
    };
};

Použitie únie bude vyzerať nasledovne:

int main(){
    union ip ip;

    // set ip as number
    ip.as_number = 2130706433; // 0x7F000001, 017700000001

    /*
    // set ip as octets
    ip.as_octets[0] = 1;
    ip.as_octets[1] = 0;
    ip.as_octets[2] = 0;
    ip.as_octets[3] = 127;

    // set ip as struct
    ip.as_struct.a = 127;
    ip.as_struct.b = 0;
    ip.as_struct.c = 0;
    ip.as_struct.d = 1;
    */

    // print out
    printf("as octets: %d %d %d %d\n",
        ip.as_octets[3], ip.as_octets[2], ip.as_octets[1],
        ip.as_octets[0]);
    printf("as struct: %d %d %d %d\n",
        ip.as_struct.a, ip.as_struct.b, ip.as_struct.c,
        ip.as_struct.d);
    printf("as number: %d\n", ip.as_number);
}

The Size of the Union

Pozrime sa na to, koľko miesta únia union ip zaberá v pamäti:
```
printf(">> size: %ld\n", sizeof(union ip));
// >> size: 4
```
Ako je možné, že únia zaberá v pamäti len 4B, keď je v nej toľko položiek?

(slide) Definícia hovorí, že únia umožňuje uchovávať rozličné typy údajov v rovnakej časti pamäte. To znamená, že aj keď som IP adresu uložil ako číslo, je uložené na rovnakom mieste, ku ktorému bude pristupovať ako pole oktetov, tak aj štruktúra a samozrejme aj samotný údajový typ unsigned int:

|    ADDR + 0   |    ADDR + 1   |    ADDR + 2   |    ADDR + 3   |
+---------------+---------------+---------------+---------------+
| .as_number                                                    |
+---------------+---------------+---------------+---------------+
| .as_octets[0] | .as_octets[1] | .as_octets[2] | .as_octets[3] |
+---------------+---------------+---------------+---------------+
| .as_struct.d  | .as_struct.c  | .as_struct.b  | .as_struct.a  |
+---------------+---------------+---------------+---------------+

Veľkosť únie závisí od prvkov, ktoré sa v nej nachádzajú. Aktuálne máme úniu, ktorá má síce tri položky, ale všetky majú rovnakú veľkosť. V prípade, že by veľkosť jednotlivých položiek bola rôzna, veľkost únie bude rovnaká, ako je veľkosť jej najväčšieho prvku. To je dané tým, že sa do danej veľkosti musí zmestiť obsah všetkých prvkov únie.
Ak by sme sa pozreli na porovnanie so štruktúrou, tak vieme, že jednotlivé položky štruktúry sa nachádzajú v pamati sekvenčne za sebou. Preto sa výsledná veľkosť štruktúry rovná súčtu veľkostí jednotlivých položiek (plus zarovnanie).

Union in Zoo

Vráťme sa teda k našej hre a pokúsme sa v nej použit úniu. Vytvorenie únie, ktorá bude reprezentovať uzol BST, je jednoduché. Už skôr sme si povedali, že bude mať dvoch členov: otázku a zviera. Upravíme teda pôvodnú štruktúru definujúcu uzol na úniu:
```
union node {
    char* animal;
    struct {
        char* question;
        union node* yes;
        union node* no;
    };
};
```
Síce sme vyriešili problém dvoch rozličných typov uzlov, ale ako rozlíšim, či aktuálny uzol je otázkou alebo zvieraťom?

Polymorphic Union

Na to, aby sme rozlíšili typ aktuálneho uzla potrebujeme samostatnú premennú, ktorá bude súčasťou uzla, a ktorá túto informáciu bude so sebou niesť. Tá však nemôže byť súčasťou únie, pretože ju bezpečne prepíšeme. Musíme teda vytvoriť štruktúru, do ktorej zabalíme ako úniu, tak aj premennú na rozlíšenie typu uzla:
```
struct node {
    enum {
        ANIMAL,
        QUESTION
    } type;
    union {
        char* animal;
        struct {
            char* question;
            struct node* yes;
            struct node* no;
        };
    };
};
```
(slide) Úniu, ktorú sme vytvorili, sa nazýva polymorfická 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.
```
       Connection
     /     |     \
Network   USB   VirtualConnection
```

(slide) Pozrime sa na ukážku takejto únie, ktorá reprezentuje udalosti vstupných zariadení v počítači. Tie sa od seba líšia podľa toho, či sa jedná o klávesnicu alebo myš:

struct input_event {
    enum event_type{
        EventKeyPressed,
        EventKeyReleased,
        EventMousePressed,
        EventMouseMoved,
        EventMouseReleased
    } type;
    union {
        unsigned int key_code;
        struct{
            int x;
            int y;
            unsigned int button_code;
        };
    };
};

Takže podľa ukážky už len vhodne upravíme výsledný kód:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>


struct node {
    enum node_type {
        ANIMAL,
        QUESTION
    } type;
    union {
        char* animal;
        struct {
            char* question;
            struct node* yes;
            struct node* no;
        };
    };
};


struct node* create_animal(char* animal){
    struct node* node = calloc(1, sizeof(struct node));
    node->type = ANIMAL;
    node->animal = animal;

    return node;
}


struct node* create_question(char* question){
    struct node* node = calloc(1, sizeof(struct node));
    node->type = QUESTION;
    node->question = question;
    node->yes = NULL;
    node->no = NULL;

    return node;
}


int main(){
    struct node *root = NULL;

    // init
    root = create_question("Ma to styri nohy?");
    root->yes = create_animal("liska");
    root->no = create_question("Vie plavat?");
    root->no->yes = create_animal("kapor");
    root->no->no = create_animal("holub");

    // let's play
    struct node* ptr = root;
    char answer;

    // find the leaf/animal
    while(ptr->type == QUESTION){
        // print content
        printf("%s\n", ptr->question);

        // read answer
        scanf(" %c", &answer);
        if(answer == 'a'){
            ptr = ptr->yes;
        }else{
            ptr = ptr->no;
        }
    }

    printf("Je to %s?\n", ptr->animal);
    scanf(" %c", &answer);
    if(answer == 'a'){
        printf("Ta ja som genius\n");
    }else{
        printf("Ta ja som sunka\n");
    }
}

Conclusion

Dnes sme si ukázali ďalšiu dátovú štruktúru strom, ktorý sme “odvodili” zo spojkového zoznamu. Ukázali sme si jeho použitie na binárnom vyhľadávacom strome, pomocou ktorého sme vytvorili jednoduchú hru Zoo. Okrem toho sme si predstavili ďalší mocný prvok jazyka C - úniu.
Využitie únií je prehliadané. A pritom ponúkajú možnosti, ktoré pri riešení istých typov problémov značne zjednodušia život. Jednou z možností je napríklad použitie polymorfizmu v jazyku C.