30. Použitie stromov


Na minulej prednáške sme naprogramovali triedu BinarnyStrom, ktorá vďaka niekoľkým šikovným metódam zvláda zostrojovať binárne stromy aj s veľa tisícmi vrcholov. Pritom v každom vrchole môže byť ľubovoľná hodnota, nielen číselná, ale aj reťazcová, prípadne by tu mohli byť aj zložitejšie dáta. Trieda BinarnyStrom z predchádzajúcej prednášky:

import random

class BinarnyStrom:
    class Vrchol:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right

    def __init__(self, postupnost=None):
        self.root = None
        if postupnost is not None:
            for hodnota in postupnost:
                self.pridaj_vrchol(hodnota)

    def pridaj_vrchol(self, hodnota):
        if self.root is None:
            self.root = self.Vrchol(hodnota)
        else:
            vrch = self.root
            while True:
                if random.randrange(2):
                    if vrch.left is None:
                        vrch.left = self.Vrchol(hodnota)
                        return
                    vrch = vrch.left
                else:
                    if vrch.right is None:
                        vrch.right = self.Vrchol(hodnota)
                        return
                    vrch = vrch.right

    def __len__(self):
        def pocet(vrch):
            if vrch is None:
                return 0
            return 1 + pocet(vrch.left) + pocet(vrch.right)
        return pocet(self.root)

    def vyska(self):
        def vyska_rek(vrch):
            if vrch is None:
                return -1
            return 1 + max(vyska_rek(vrch.left), vyska_rek(vrch.right))
        return vyska_rek(self.root)

    def __contains__(self, hodnota):
        def nachadza_sa(vrch):
            if vrch is None:
                return False
            return vrch.data == hodnota or nachadza_sa(vrch.left) or nachadza_sa(vrch.right)
        return nachadza_sa(self.root)

Pomocou takto definovanej dátovej štruktúry môžeme teda vytvoriť ľubovoľne veľký strom, napríklad:

>>> s = BinarnyStrom(random.randrange(10000) for i in range(10000))
>>> s.vyska()
17
>>> 5000 in s
False

V tomto strome sa nachádzajú náhodné čísla z intervalu <0, 9999> a aby sme zistili, či sa v ňom nachádza nejaká konkrétna hodnota, musíme postupne (najskôr rekurzívne) preliezť celý strom, teda všetkých 10000 vrcholov.


Binárny vyhľadávací strom

Pozrime sa ale na takýto binárny strom, ktorý obsahuje 25 vrcholov a jeho hĺbka je len 4:

binárny strom

Skúsme popísať akú vlastnosť majú hodnoty vo vrcholoch tohoto konkrétneho stromu:

  • vo všetkých vrcholoch sú rôzne hodnoty - sú to nejaké celé čísla

  • v koreni stromu je číslo 37

  • v ľavom podstrome sú všetky hodnoty menšie ako 37

  • v pravom podstrome sú všetky hodnoty väčšie ako 37

  • teda, ak budeme v tomto strome hľadať nejakú hodnotu, nemusíme pritom prechádzať celý strom, ale len polovicu, podľa toho, či je hľadaná hodnota menšia ako číslo v koreni alebo väčšia

Predpokladajme, že hľadáme číslo 21 - zrejme stačí pozerať ľavý podstrom (tu je jeho koreň 15). Ak by aj tento náš podstrom mal túto istú vlastnosť (vľavo sú len menšie ako 15 a vpravo len väčšie ako 15), nemuseli by sme preliezať celý tento podstrom, ale stačilo by len tú časť, ktorú zistíme po porovnaní s koreňom: keďže hľadané je 21 a to je väčšie ako koreň podstromu 15, stačí túto hodnotu hľadať v pravom podstrome od vrcholu 15.

Keďže tento ukážkový strom je skonštruovaný tak, že vlastnosť „naľavo menšie a napravo väčšie“ platí pre každý vrchol stromu, môžeme hľadanie v takomto strome zapísať takto:

  1. do vrch daj koreň stromu

  2. ak je hodnota vo vrch zhodná s hľadanou hodnotou, môžeš skončiť (našiel)

  3. ak je hodnota vo vrch väčšia ako hľadaná, bude treba pokračovať v ľavom podstrome, teda zmeň vrch na ľavý podstrom

  4. inak sa hľadaná hodnota nachádza v pravom podstrome, teda zmeň vrch na pravý podstrom

  5. ak vrch nie je None pokračuj od kroku (2), inak skonči (nenašiel)

Tento algoritmus je zaujímavý tým, že

  • nie je rekurzívny

  • opakuje sa v ňom nejaká časť: kým nenájdeme hľadanú hodnotu, alebo neprídeme do listu stromu

  • teda netreba hľadanú hodnotu porovnávať so všetkými hodnotami stromu, ale len s hodnotami na nejakej ceste smerom k listu stromu

  • maximálny počet porovnaní (prechodov cyklu) bude teda závisieť od výšky stromu, čo je v našom prípade 4

Binárny strom, ktorý má vlastnosť, že pre každý vrchol stromu platí

  • všetky vrcholy v ľavom podstrome sú menšie ako hodnota v koreni

  • všetky vrcholy v pravom podstrome sú väčšie ako hodnota v koreni

sa nazýva binárny vyhľadávací strom.

Zapíšme základ definície triedy BVS, ktorá bude mať zatiaľ jedinú metódu na hľadanie hodnoty v strome:

class BVS:
    class Vrchol:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right

    def __init__(self):
        self.root = None

    def hladaj(self, hodnota):
        vrch = self.root
        while vrch is not None:
            if vrch.data == hodnota:
                return True
            if vrch.data > hodnota:
                vrch = vrch.left
            else:
                vrch = vrch.right
        return False

Môžete vidieť, že táto nerekurzívna metóda hladaj() je veľmi jednoduchá a preto dobre čitateľná. Horšie je, že zatiaľ to nevieme otestovať, lebo nevieme nejako jednoducho skonštruovať binárny strom, ktorý by mal vlastnosť BVS.

Vytvorme najprv BVS, priamym priradením vrcholov do root, napríklad takto:

v = BVS.Vrchol
s = BVS()
s.root = v(30, v(10, v(3), v(12, v(11), v(17))), v(35, v(32, None, v(34)), v(36)))

Zápis v = BVS.Vrchol tu označuje to, že si vyrobíme skratku v pre volanie BVS.Vrchol. Takto vytvorený strom má tento tvar:

binárny strom

Vidíme, že naozaj každý vrchol stromu spĺňa podmienku BVS. Môžeme otestovať:

>>> s.hladaj(15)
False
>>> s.hladaj(17)
True
>>> s.hladaj(30)
True
>>> s.hladaj(35)
True
>>> s.hladaj(33)
False

Teraz sa zamyslime nad tým, ako môžeme zautomatizovať vytváranie BVS. Predpokladajme, že už máme nejaký BVS a chceme do neho pridať nový vrchol, ale tak, aby aj tento nový strom bol BVS - teda chceme, aby sa nepokazila vlastnosť BVS. Ak by sme chceli do nášho malého ukážkového stromu pridať, napríklad hodnotu 7 a všetky existujúce vrcholy chceme pritom nechať na svojom mieste, budeme hľadať (podobne ako metóda hladaj()) miesto, kde by sme očakávali umiestnenie takejto hodnoty:

  • keďže 7 nie je v koreni stromu, budeme pokračovať vľavo, lebo 7 je menšie ako 30

  • tu má ľavý podstrom svoj koreň 10, čo je opäť viac ako 7, preto sa opäť presúvame vľavo

  • ľavý podstrom vrcholu 10 je strom s koreňom 3 (ten je už bez synov) - keďže 3 je menej ako 7, pridávaná hodnota bude ležať v pravom podstrome 3

  • keďže pravý podstrom vrcholu 3 neexistuje, tu je presne to miesto, kde by sme mohli pripojiť nový vrchol s hodnotou 7

Zapíšme tento postup do algoritmu:

  1. ak koreň neexistuje, vyrobí sa nový koreň s vkladanou hodnotou

  2. inak označme koreň stromu ako vrch a hľadajme miesto na pridanie nového vrcholu

  3. skontrolujme, či pridávaná hodnota sa nenachádza v koreni, teda vrch.data, ak áno, skončíme (nebolo treba pridávať)

  4. ak je pridávaná hodnota menšia ako hodnota v koreni, budeme kontrolovať ľavý smer:

    • ak ľavý syn vrcholu vrch neexistuje, na toto miesto vytvoríme nový vrchol a skončíme

    • inak zmeníme vrch na ľavý podstrom a pokračujeme v (3)

  5. pridávaná hodnota je väčšia ako hodnota v koreni, preto budeme kontrolovať pravý smer:

    • ak pravý syn vrcholu vrch neexistuje, na toto miesto vytvoríme nový vrchol a skončíme

    • inak zmeníme vrch na pravý podstrom a pokračujeme v (3)

V strome to bude vyzerať takto:

binárny strom

Podobne ako metóda hladaj() aj táto je nerekurzívna:

class BVS:
    ...

    def vloz(self, hodnota):
        if self.root is None:
            self.root = self.Vrchol(hodnota)
        else:
            vrch = self.root
            while vrch.data != hodnota:
                if vrch.data > hodnota:
                    if vrch.left is None:
                        vrch.left = self.Vrchol(hodnota)
                        return
                    vrch = vrch.left
                else:
                    if vrch.right is None:
                        vrch.right = self.Vrchol(hodnota)
                        return
                    vrch = vrch.right

Pomocou tejto metódy môžeme BVS z predchádzajúceho príkladu vytvoriť, napríklad takto:

s = BVS()
for i in 30, 10, 35, 3, 12, 32, 36, 11, 17, 34:
    s.vloz(i)

Užitočné vlastnosti BVS

  • inorder postupnosť je vždy vzostupne utriedená postupnosť všetkých hodnôt v strome

  • preorder postupnosť jednoznačne určuje tvar BVS - ak vytvoríme nový strom s vkladaním prvkov v poradí preorder postupnosti, dostávame identický strom

  • minimálny prvok je najľavejší v celom strome, t.j. ak pôjdeme od koreňa po ľavých synoch, tak posledný v trase je minimálny prvok

  • maximálny prvok je najpravejší v celom strome, t.j. ak pôjdeme od koreňa po pravých synoch, tak posledný v trase je maximálny prvok

  • ľubovoľný prvok v strome sa dá nájsť za maximálne toľko krokov, ako je výška stromu

Degenerovaný BVS

Ak by sme vytvárali BVS z utriedenej postupnosti (postupným volaním metódy vloz()), dostávame strom, ktorý obsahuje, napríklad len pravých synov (ľavé podstromy sú prázdne). Binárny strom sa takto zdegeneroval na spájaný zoznam - výška stromu je vlastne počet prvkov mínus 1 - v takomto strome potom hľadanie prvku prechádza celý strom. Degenerovaným stromom pomenujeme aj také BVS, ktoré majú veľkú výšku, napríklad n/2 kde n je počet prvkov stromu.

Ideálne by bolo, keby bol BVS skoro úplný, v ktorom väčšina listov má rovnakú hĺbku (rovnajúcu sa výške stromu). Vtedy je vyhľadávanie prvku veľmi rýchle a netreba na neho viac porovnaní ako je výška stromu, čo je pre skoro úplný strom približne log2 n. Vyrobiť takýto skoro úplný strom je ale už náročnejšia práca.


Aritmetický strom

Pozrite si tento binárny strom, ktorý by mohol byť pre nás dobre čitateľný:

aritmetický strom

V tomto strome sú vo všetkých vnútorných vrcholoch nejaké aritmetické operácie a v listoch sú nejaké čísla (zrejme operandy). Strom na obrázku by mohol zodpovedať takémuto aritmetickému výrazu:

5 * (1 + 3) + 15 / 3

Hoci vo výraze, ktorý je uložený v tomto strome, nie sú žiadne zátvorky, vy si ich viete na správnych miestach domyslieť. Takýmto stromom budeme hovoriť aritmetické stromy. Môžete ich nájsť aj pod názvom binary expression tree (ale aj inde), čiastočne aj ako parse tree.

Môžeme zhrnúť základné vlastnosti takýchto stromov:

  • vo vnútorných vrcholoch sa nachádzajú reťazce binárnych operácií, napríklad '+', '-', '*', '/', ale môže tu byť aj '**' alebo 'and', … ak vieme popísať ich spôsob vyhodnocovania

  • v listoch sú operandy binárnych operácií, najčastejšie sú to celé alebo desatinné čísla, ale mohli by tu byť aj znakové reťazce, ktoré by mohli reprezentovať mená premenných

Takéto aritmetické stromy vieme veľmi jednoducho vyhodnocovať:

  • nájdeme operáciu (vnútorný vrchol), ktorej oba synovia sú už vyhodnotené operandy (listy stromu alebo už vyhodnotené podstromy), v našom príklade je to podstrom 1 + 3

    aritmetický strom
  • vyhodnotí sa táto operácia a celý tento podstrom dostáva hodnotu, ktorá je výsledkom tejto operácie, teda číslo 4

    aritmetický strom
  • teraz sa môže vyhodnocovať aj operácia '*', lebo ľavým operandom je číslo 5 a pravým je hodnota pravého podstromu 4 - výsledkom je teda číslo 20

    aritmetický strom
  • ďalšou operáciou je /, teda podstrom 15 / 3 - táto operácia sa vyhodnotí a výsledkom podstromu je hodnota 5 (tu to môžeme chápať ako celočíselné delenie)

    aritmetický strom
  • na záver sa vyhodnotí operácia '+', ktorá je v koreni celého stromu, lebo už poznáme hodnoty oboch jej podstromov, teda 20 z ľavého podstromu a 5 z pravého - vyhodnotením dostávame výsledok pre celý strom, teda 25

    aritmetický strom

Uvedomte si, že v skutočnosti sa takýmto vyhodnocovaním aritmetický strom nemodifikuje - ten ostáva bez zmeny. Takto len ilustrujeme postup vyhodnocovania.

Celý tento postup môžeme zapísať rekurzívnou metódou vyhodnot() do definície triedy AritmetickyStrom:

class AritmetickyStrom:
    class Vrchol:
        def __init__(self, data, left=None, right=None):
            self.data = data
            self.left = left
            self.right = right

    def __init__(self):
        self.root = None

    def vyhodnot(self):

        def hodnota(vrch):
            if vrch is None:
                raise SyntaxError
            if vrch.left is None and vrch.right is None:
                return vrch.data
            hodnota_left = hodnota(vrch.left)
            hodnota_right = hodnota(vrch.right)
            if vrch.data == '+':
                return hodnota_left + hodnota_right
            elif vrch.data == '-':
                return hodnota_left - hodnota_right
            elif vrch.data == '*':
                return hodnota_left * hodnota_right
            elif vrch.data == '/':
                return hodnota_left // hodnota_right
            else:
                raise SyntaxError

        return hodnota(self.root)

Keďže zatiaľ nevieme vytvoriť aritmetický strom inak ako priamym priradením vrcholov do koreňa stromu (root), musíme to otestovať takto:

>>> v = AritmetickyStrom.Vrchol
>>> s = AritmetickyStrom()
>>> s.root = v('+', v('*', v(5), v('+', v(1), v(3))), v('/', v(15), v(3)))
>>> print('vyhodnotenie =', s.vyhodnot())
vyhodnotenie = 25

Zaujímavý výsledok dostávame, keď z aritmetického stromu vypíšeme jeho preorder, inorder a postorder postupnosti (skopírujeme ich a mierne zmodifikujeme z predchádzajúcej prednášky):

>>> s.preorder()
'+ * 5 + 1 3 / 15 3'
>>> s.inorder()
'5 * 1 + 3 + 15 / 3'
>>> s.postorder()
'5 1 3 + * 15 3 / +'

Dostávame nám známe zápisy prefix, infix a postfix. Hoci asi nie je problém upraviť metódu inorder() tak, aby každý podvýraz (podstrom) ozátvorkovala, napríklad takto:

>>> s.inorder()
'((5 * (1 + 3)) + (15 / 3))'

Tento reťazec by sme prekopírovaním (copy-paste) vedeli nechať vyhodnotiť aj Pythonu:

>>> ((5 * (1 + 3)) + (15 / 3))
25.0

Všeobecný strom

Už vieme, že všeobecný strom je dátová štruktúra podobná binárnym stromom, ale na rozdiel od nich môže mať každý vrchol ľubovoľný počet svojich synov (namiesto dvojice referencií left a right má každý vrchol zoznam (list) všetkých svojich synov v atribúte child). Zapíšme definíciu triedy aj s niekoľkými užitočnými metódami:

import random
import tkinter

class VseobecnyStrom:
    canvas = None
    class Vrchol:
        def __init__(self, data):
            self.data = data
            self.child = []       # zoznam všetkých synov

    def __init__(self):
        self.root = None

    def __len__(self):

        def pocet_rek(vrch):
            if vrch is None:
                return 0
            vysl = 1
            for child in vrch.child:
                vysl += pocet_rek(child)
            return vysl

        return pocet_rek(self.root)

    def __repr__(self):

        def repr_rek(vrch):
            if vrch is None:
                return '()'
            vysl = [repr(vrch.data)]
            for child in vrch.child:
                vysl.append(repr_rek(child))
            return '(' + ','.join(vysl) + ')'

        return repr_rek(self.root)

    def pridaj_nahodne(self, *postupnost):

        def pridaj_vrchol(vrch):
            n = len(vrch.child)
            i = random.randrange(n+1)
            if i == n:
                vrch.child.append(self.Vrchol(hodnota))
            else:
                pridaj_vrchol(vrch.child[i])

        for hodnota in postupnost:
            if self.root is None:
                self.root = self.Vrchol(hodnota)
            else:
                pridaj_vrchol(self.root)

    def kresli(self):

        def kresli_rek(vrch, sir, x, y):
            n = len(vrch.child)
            if n != 0:
                sir0 = 2 * sir // n
            for i in range(n):
                x1, y1 = x - sir + i*sir0 + sir0//2, y + 50
                self.canvas.create_line(x, y, x1, y1)
                kresli_rek(vrch.child[i], sir0//2, x1, y1)
            self.canvas.create_oval(x-15, y-15, x+15, y+15, fill='lightblue', width=0)
            self.canvas.create_text(x, y, text=vrch.data, font='consolas 15')

        if self.canvas is None:
            VseobecnyStrom.canvas = tkinter.Canvas(bg='white', width=600, height=400)
            self.canvas.pack()
        self.canvas.delete('all')
        kresli_rek(self.root, 290, 300, 30)

Otestujeme:

strom = VseobecnyStrom()
strom.pridaj_nahodne(*(random.randrange(100) for i in range(20)))
strom.kresli()
print('pocet vrcholov v strome =', len(strom))
print('strom =')
print(strom)

Náhodný strom môže vyzerať napríklad takto:

všeobecný strom

a potom dostávame takýto výpis:

pocet vrcholov v strome = 20
strom =
(57,(96,(98),(71)),(60,(53),(10),(69,(6))),(48,(0,(31),(82,(28))),(72)),(94,(23),(45,(21))),(99))

keby sme do __repr__() pridali 2 riadky:

class VseobecnyStrom:
    ...

    def __repr__(self):

        def repr_rek(vrch):
            if vrch is None:
                return '()'
            vysl = [repr(vrch.data)]
            for child in vrch.child:
                vysl.append(repr_rek(child))
            if len(vysl) == 1:
                return vysl[0]
            return '(' + ','.join(vysl) + ')'

        return repr_rek(self.root)

dostávame trochu úspornejší (menej zátvoriek) a možno čitateľnejší výpis:

>>> strom
(57,(96,98,71),(60,53,10,(69,6)),(48,(0,31,(82,28)),72),(94,23,(45,21)),99)

Z takéhoto zápisu sa dá teraz spätne skonštruovať celý strom:

  • je to vlastne n-tica, v ktorej je prvý prvok koreň (hodnota 57) a za tým nasledujú podstromy (synovia koreňa),

  • prvý podstrom (syn) je popísaný opäť n-ticou (96,98,71), teda má hodnotu 96 a jeho synovia sú 98 a 71,

  • druhý podstrom je n-tica (60,53,10,(69,6)), teda má hodnotu 60 a jeho synovia sú 53, 10 a (69,6),

  • tretí podstrom je (48,(0,31,(82,28)),72) s hodnotou 48 a dvoma synmi 0 a 72

  • štvrtý podstrom (94,23,(45,21)) s hodnotou 94

  • piaty podstrom tvorí list 99

Toto by sa dalo popísať aj rekurzívnym algoritmom.

Reprezentácia syn-brat

Namiesto zoznamu všetkých synov (v atribúte child typu list) si v každom vrchole budeme pamätať len referenciu na prvého syna (nazveme to child) a referenciu na nasledovného brata (v atribúte sibling). V každom vrchole teda budú tieto dve referencie:

class Vrchol:
    def __init__(self, data):
        self.data = data
        self.child = None       # prvý syn
        self.sibling = None     # nasledovný brat

Takejto reprezentácii všeobecného stromu budeme hovoriť syn-brat (po anglicky Left-child right-sibling binary tree).

Ukážeme to na príklade. Tento všeobecný strom:

všeobecný strom

by v reprezentácii syn-brat vyzeral takto:

syn-brat

Takáto reprezentácia je vlastne binárny strom (vľavo sú prví synovia a vpravo sú nasledovní bratia). Keby sme to zobrazili rovnako ako binárne stromy, vyzeralo by to takto:

syn-brat ako binárny strom

Cvičenia

L.I.S.T.


Vyhľadávacie stromy

  1. Zisti, či tento strom spĺňa podmienky BVS

    binárny strom

  1. Ručne nakresli strom, ktorý by vznikol postupným pridávaním do BVS týchto hodnôt:

    'KE', 'BS', 'PO', 'PE', 'PK', 'BA', 'BL', 'NI', 'SC', 'BB', 'RK', 'BR'
    

  1. Dopíš do stromu na obrázku čísla z postupnosti range(1, 23) tak, aby vznikol BVS:

    binárny strom

  1. Spojazdni triedu BVS z prednášky a pridaj do nej metódu na vykreslenie stromu z predchádzajúcej prednášky:

    import tkinter
    
    class BVS:
        canvas = None
        ...
    
        def kresli(self):
            ...
    

    Prever správnosť tohto riešenia pre strom:

    s = BVS()
    v = BVS.Vrchol
    s.root = v(16, v(3, v(1, None, v(2)), v(5)), v(20, v(19, v(18, v(17)), v(21)), v(23)))
    s.kresli()
    

  1. Vylepši inicializáciu __init__() triedy BVS tak, aby mohla mať nepovinný druhý parameter postupnost - z tejto postupnosti hodnôt vytvorí BVS (volaním metódy vloz()):

    class BVS:
        ...
    
        def __init__(self, postupnost=None):
            ...
    

    Funkčnosť otestuj na strome z (2) úlohy:

    s = BVS('KE BS PO PE PK BA BL NI SC BB RK BR'.split())
    s.kresli()
    

    Vytvor BVS aj z (1) a (3) úlohy.


  1. Do triedy BVS zapíš metódy min() a max(). Tieto by mali vrátiť minimálnu, resp. maximálnu hodnotu v strome. Využi vlastnosť BVS, podľa ktorej je minimálny vrchol najnižší na ceste od koreňa vľavo a maximálny vpravo:

    class BVS:
        ...
    
        def min(self):
            ...
    
        def max(self):
            ...
    

    Otestuj, napríklad:

    >>> s = BVS('KE BS PO PE PK BA BL NI SC BB RK BR'.split())
    >>> s.min()
    'BA'
    >>> s.max()
    'SC'
    

  1. Do triedy BVS doplň metódy inorder_list() a preorder_list() (využi predchádzajúcu prednášku):

    class BVS:
        ...
    
        def inorder_list(self):
            ...
    
        def preorder_list(self):
            ...
    

    Prekontroluj, či inorder postupnosť vracia usporiadanú postupnosť všetkých hodnôt v strome, napríklad takto:

    >>> zoz = [16, 20, 3, 21, 19, 5, 1, 23, 18, 2, 17]
    >>> s = BVS(zoz)
    >>> s.kresli()
    >>> s.inorder_list()
    [1, 2, 3, 5, 16, 17, 18, 19, 20, 21, 23]
    >>> s.inorder_list() == sorted(zoz)
    True
    

    Prekontroluj, či sa z preorder postupnosti nejakého BVS dá skonštruovať iný BVS, ktorý má úplne rovnaký tvar ako pôvodný:

    >>> s = BVS([16, 20, 3, 21, 19, 5, 1, 23, 18, 2, 17])
    >>> s.kresli()
    >>> zoz1 = s.preorder_list()
    >>> zoz1
    [16, 3, 1, 2, 5, 20, 19, 18, 17, 21, 23]
    >>> s1 = BVS(zoz1)
    >>> s1.kresli()
    

    Oba tieto stromy by mali vyzerať rovnako.


  1. (náročnejšia úloha) Danú postupnosť hodnôt preusporiadaj tak, aby BVS, ktorý vznikne postupným pridávaním prvkov tejto preusporiadanej postupnosti, bol skoro úplný. Idea by mohla byť takáto:

    • usporiadaj danú postupnosť (napríklad pomocou sorted())

    • stredný prvok bude prvý (ďalší) vo výsledku

    • rekurzívne spracuj prvú polovicu (po stredný prvok)

    • rekurzívne spracuj druhú polovicu (od stredného prvku)

    Napíš funkciu vyrob_BVS(postupnost), ktorá z danej postupnosti vytvorí (a vráti) BVS, podľa daného návodu (a teda minimálnej výšky):

    def vyrob_BVS(postupnost):
        ...
        return BVS(...)
    

    Napríklad:

    >>> vyrob_BVS('KE BS PO PE PK BA BL NI SC BB RK BR SE NO SK'.split()).kresli()
    

    nakreslí takýto BVS:

    _images/30_24.png

Aritmetické stromy

  1. Ručne (na papieri) nakresli strom pre tento aritmetický výraz:

    6 * 5 + 7 / (4 - 2 * 5)
    

  1. Spojazdni triedu AritmetickyStrom z prednášky a doplň do nej metódu na vykresľovanie stromu:

    import tkinter
    
    class AritmetickyStrom:
        canvas = None
    
        ...
    
        def kresli(self):
            ...
    

    Otestuj na príklade stromu z prednášky:

    v = AritmetickyStrom.Vrchol
    s = AritmetickyStrom()
    s.root = v('+', v('*', v(5), v('+', v(1), v(3))), v('/', v(15), v(3)))
    print('vyhodnotenie =', s.vyhodnot())
    s.kresli()
    

  1. Dopíš metódy prefix(), infix() a postfix() tak, aby vrátili znakový reťazec, pričom infix() ozátvorkuje všetky podvýrazy (podstromy), ktoré obsahujú operácie:

    class AritmetickyStrom:
        ...
    
        def prefix(self):
            ...
    
        def infix(self):
            ...
    
        def postfix(self):
            ...
    

    Otestuj, napríklad:

    v = AritmetickyStrom.Vrchol
    s = AritmetickyStrom()
    s.root = v('+', v('*', v(5), v('+', v(1), v(3))), v('/', v(15), v(3)))
    print('prefix =', s.prefix())
    print('infix =', s.infix())
    print('postfix =', s.postfix())
    

    Vypíše:

    prefix = + * 5 + 1 3 / 15 3
    infix = ((5*(1+3))+(15/3))
    postfix = 5 1 3 + * 15 3 / +
    

  1. Do inicializácie __init__() dopíš parameter postfix (znakový reťazec, ktorý obsahuje postfixový výraz - prvky sú v ňom oddelené medzerou) a metóda z tohto reťazca zkonštruuje aritmetický strom (algoritmus sa podobá vyhodnocovaniu postfixu):

    • vytvorí si pomocný zásobník

    • prerobí vstupný reťazec na zoznam prvkov

    • postupne prechádza prvky zoznamu:

      • ak je prvkom operácia, vyberie z vrchu zásobníka pravý aj ľavý operand, s danou operáciou poskladá malý podstrom (Vrchol(operácia, ľavý, pravý)) a vloží ho na vrch zásobníka

      • inak je prvkom číslo (zatiaľ je to reťazec, ktorý reprezentuje číslo), vyrobí z neho nový vrchol (Vrchol(číslo)) a vloží ho na vrch zásobníka

    • po spracovaní všetkých prvkov poľa je na vrchu zásobníka kompletný aritmetický strom - už ho iba priradí do atribútu root

    Dopíš inicializáciu do triedy:

    class AritmetickyStrom:
        ...
    
        def __init__(self, postfix):
            self.root = None
            ...
    

    Otestuj, napríklad:

    >>> s = AritmetickyStrom('5 1 3 + * 15 3 / +')
    >>> s.kresli()
    

Všeobecné stromy

  1. Oprav definíciu triedy VseobecnyStrom tak, aby sa pri inicializácii vrcholov mohli uviesť aj referencie na podstromy:

    class VseobecnyStrom:
        canvas = None
        class Vrchol:
            def __init__(self, data, *child):
                ...
        ...
    

    Napríklad:

    >>> v = VseobecnyStrom.Vrchol
    >>> s = VseobecnyStrom()
    >>> s.root = v('a', v('b', v('c'), v('d')), v('e', v('f', v('g')), v('h'), v('i'), v('j')))
    >>> s
    ('a',('b','c','d'),('e',('f','g'),'h','i','j'))
    

  1. Do triedy VseobecnyStrom napíš metódy:

    • preorder() - vráti postupnosť hodnôt v poli (typu list)

    • vyska() - zistí výšku stromu

    • pocet_listov() - zistí počet listov stromu

    class VseobecnyStrom:
        ...
    
        def preorder(self):
            ...
    
        def vyska(self):
            ...
    
        def pocet_listov(self):
            ...
    

7. Domáce zadanie

L.I.S.T.


Budeme riešiť problém, pomocou ktorého sa budú dať evidovať počty nakazených nejakým vírusom v rôznych mestách. Využijeme na to binárny vyhľadávací strom a umožníme vytvorené dáta uložiť do binárneho súboru, resp. to z neho prečítať. Kľúčom vo vyhľadávacom strome bude meno mesta.

Vytvor triedu Evidencia:

class Evidencia:
    class Vrchol:
        def __init__(self, meno, cislo):
            self.meno, self.cislo = meno, cislo
            self.left = self.right = None

    def __init__(self, meno_suboru=None):
        self.root = None
        ...

    def vloz(self, meno, cislo):
        ...

    def __getitem__(self, meno):
        ...
        return None

    def __len__(self):
        ...
        return 0

    def vypis(self, od=None, do=None):
        ...

    def uloz(self, meno_suboru):
        ...

    def max_cislo(self):
        ...
        return 0

    def sucet_cisel(self):
        ...
        return 0

    def sirka(self):
        ...
        return 0

    def vyska(self):
        ...

Metódy

  • __init__(meno_suboru=None) - ak je dané meno_suboru, tento binárny súbor prečíta a vytvorí z neho binárny vyhľadávací strom; hodnoty vkladá v poradí, ako sú v súbore, pomocou metódy vloz(...), koreň stromu je v atribúte root

  • vloz(meno, cislo) - do stromu vloží pre dané meno (meno mesta) toto cislo (počet nakazených), ak také meno už v strome existovalo pred tým, potom toto cislo pripočíta k momentálnej hodnote vo vrchole

  • __getitem__(meno) - pre dané meno vráti príslušné cislo alebo None, ak také meno neexistuje

  • __len__() - vráti počet vrcholov v strome

  • vypis(od=None, do=None) - výpis vrcholov v poradí inorder - z každého vrcholu vypíše meno a číslo; ak je daný parameter od, vypisovanie začne až od tohto vrcholu, ak je daný parameter do, výpis skončí pred touto hodnotou; vypis() bez parametrov vypíše všetky vrcholy, vypis(4) začne od vrcholu v poradí 4 (prvé štyri sa vynechajú), vypis(0, 10) vypíše prvých 10 vrcholov

  • uloz(meno_suboru) - uloží strom do binárneho súboru - vrcholy sa uložia v poradí po úrovniach

  • max_cislo() - vráti maximálne číslo zo všetkých vrcholov

  • sucet_cisel() - vráti súčet čísel vo všetkých vrcholoch

  • sirka() - vráti šírku stromu

  • vyska() - vráti výšku stromu

Binárny súbor

Všetky vrcholy z binárneho vyhľadávacieho stromu sú postupne uložené v binárnom súbore. Jeho formát je nasledovný:

  • prvý bajt obsahuje celé číslo - toto číslo určuje, koľko bajtov zaberajú celé čísla v každom vrchole, napríklad, ak je v tomto bajte 1, označuje to, že počty nakazených budú čísla od <1, 255>, ak je v prvom bajte 2, v každom vrchole stromu môže byť číslo z <1, 65535>, atď.

  • ďalej nasleduje popis prvého vrcholu v strome (zrejme to bude koreň): najprv je to meno (postupnosť znakov ukončená b'\x00') a za tým nasleduje cislo (celé číslo, ktoré je uložené v príslušnom počte bajtov)

  • celé čísla, ktoré v každom vrchole vyjadrujú počty prípadov sú v súbore zapísané na najmenší počet bajtov, do ktorého sa zmestia všetky počty vo všetkých vrcholoch stromu, preto treba pri vytváraní súboru najprv zistiť maximálne číslo (pomocou metódy max_cislo) a potrebný počet bajtov zapísať ako prvý bajt súboru; všetky čísla v súbore potom budú zaberať tento maximálny počet, napríklad, ak je v nejakom vrchole hodnota čísla 1000000 (a táto je maximálna), všetky čísla v súbore budú zaberať tri bajty

  • viacbajtové čísla sú v súbore uložené tak, že najnižší bajt je posledný, v prvom bajte je najvyšší bajt, teda z čísla vyrobíme postupnosť bajtov takto:

    >>> cislo = 1000000
    >>> cislo.to_bytes(3, 'big')
    

    z postupnosti troch bajtov vyrobíme celé číslo takto:

    >>> bajty = b'\x01\x23\x45'
    >>> int.from_bytes(bajty, 'big')
    
  • ešte pripomíname, že zo znakového reťazca môžeš vyrobiť postupnosť bajtov takto:

    >>> retazec = 'Modra'
    >>> bytes(retazec, 'utf8')
    

    a z postupnosti bajtov získaš znakový reťazec takto:

    >>> bajty = b'\x42\x4c'
    >>> bajty.decode()
    

Testovanie

Ak by si spustil tento test:

if __name__ == '__main__':
    e = Evidencia()
    e.vloz('NI', 7)
    e.vloz('BL', 10)
    e.vloz('TT', 6)
    e.vloz('PO', 1)
    e.vloz('BB', 2)
    e.vloz('KE', 12)
    e.vloz('KO', 7)
    e.vypis()
    print('pocet vrcholov =', len(e))
    print('vyska stromu =', e.vyska())
    print('sirka stromu =', e.sirka())
    print('maximalne cislo =', e.max_cislo())
    print('sucet cisel =', e.sucet_cisel())

vypísalo by sa:

BB 2
BL 10
KE 12
KO 7
NI 7
PO 1
TT 6
pocet vrcholov = 7
vyska stromu = 3
sirka stromu = 3
maximalne cislo = 12
sucet cisel = 45

A samotný BVS by vyzeral takto:

_images/30_25.png

Ak ešte zapíšeš:

e.uloz('subor.dat')

vyrobí sa presne rovnaký súbor, ako je prvý z testovacích dátových súborov:

01
4E 49 00 07
42 4C 00 0A
54 54 00 06
42 42 00 02
4B 45 00 0C
50 4F 00 01
4B 4F 00 07

Samozrejme, že mená miest nemusia byť len dvojpísmenové - môžu mať ľubovoľnú dĺžku, teda aspoň jeden znak.

Obmedzenia

  • riešenie odovzdaj v súbore riesenie.py najneskôr do 31. mája, pričom sa v ňom bude nachádzať len jedna definícia triedy Evidencia, trieda Vrchol bude vnorená v triede Evidencia

  • prvé tri riadky tohto súboru budú obsahovať:

    # 7. zadanie: Evidencia
    # autor: Janko Hrasko
    # datum: 7.4.2020
    
  • zrejme ako autora uvedieš svoje meno

  • atribút root v triede Evidencia musí obsahovať referenciu na koreň binárneho vyhľadávacieho stromu