31. Použitie stromov

prezentácia

video prezentácia


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, self.left, self.right = data, left, 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, self.left, self.right = data, left, 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 potomkov) - 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ý potomok 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ý potomok 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 potomkoch, 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 potomkoch, 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 potomkov (ľ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 potomkovia 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, self.left, self.right = data, left, 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
            if vrch.data == '-':
                return hodnota_left - hodnota_right
            if vrch.data == '*':
                return hodnota_left * hodnota_right
            if vrch.data == '/':
                return hodnota_left // hodnota_right
            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 potomkov (namiesto dvojice referencií left a right má každý vrchol zoznam (list) všetkých svojich potomkov 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 = []

    def __init__(self):
        self.root = None

    def __len__(self):
        def pocet_rek(vrch):
            if vrch is None:
                return 0
            return 1 + sum(map(pocet_rek, vrch.child))
        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))
##            if len(vysl) == 1:
##                return vysl[0]
            return '(' + ','.join(vysl) + ')'
        return repr_rek(self.root)

    def pridaj_nahodne(self, *postupnost):
        for hodnota in postupnost:
            if self.root is None:
                self.root = self.Vrchol(hodnota)
            else:
                vrch = self.root
                while True:
                    n = len(vrch.child)
                    i = random.randrange(n+1)
                    if i == n:
                        vrch.child.append(self.Vrchol(hodnota))
                        break
                    vrch = vrch.child[i]

    def kresli(self):
        def kresli_rek(vrch, sir, x, y):
            n = len(vrch.child)
            if n != 0:
                sir0 = sir // n
                x1, y1 = x - sir - sir0, y + 50
                for i in range(n):
                    x1 += 2*sir0
                    self.canvas.create_line(x, y, x1, y1)
                    kresli_rek(vrch.child[i], sir0, 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 14')

        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 =', 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 (potomkovia koreňa),

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

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

  • tretí podstrom je (48,(0,31,(82,28)),72) s hodnotou 48 a s dvoma potomkami 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 potomok-súrodenec

Namiesto zoznamu všetkých potomkov (v atribúte child typu list) si v každom vrchole budeme pamätať len referenciu na prvého potomka (nazveme to child) a referenciu na nasledovného súrodenca (v atribúte sibling). Niekedy sa tejto reprezentácii hovorí aj syn-brat. V každom vrchole teda budú tieto dve referencie:

class Vrchol:
    def __init__(self, data):
        self.data = data
        self.child = None       # prvý potomok
        self.sibling = None     # nasledovný súrodenec

Takejto reprezentácii všeobecného stromu budeme hovoriť potomok-súrodenec (po anglicky child-sibling representation).

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

všeobecný strom

by v reprezentácii potomok-súrodenec vyzeral takto:

potomok-súrodenec

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

potomok-súrodenec 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/31_c3.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. Týždenný projekt

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 Evidence:

class Evidence:
    class Node:
        def __init__(self, name, number):
            self.name, self.number = name, number
            self.left = self.right = None

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

    def insert(self, name, number):
        ...

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

    def __len__(self):
        ...
        return 0

    def printout(self, start=None, stop=None):
        ...

    def save(self, file_name):
        ...

    def max_number(self):
        ...
        return 0

    def total(self):
        ...
        return 0

    def width(self):
        ...
        return 0

    def height(self):
        ...

Metódy

  • __init__(file_name=None) - ak je dané file_name (znakový reťazec), prečíta binárny súbor s týmto menom a vytvorí z neho binárny vyhľadávací strom; hodnoty vkladá v poradí, ako sú v súbore, pomocou metódy insert(...), koreň stromu je v atribúte root

  • insert(name, number) - do stromu vloží pre dané name (meno mesta - znakový reťazec) príslušnú hodnotu number (počet nakazených - celé číslo), ak také meno už v strome existovalo pred tým, potom toto číslo number pripočíta k momentálnej hodnote vo vrchole

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

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

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

  • save(file_name) - uloží strom do binárneho súboru - vrcholy sa uložia v poradí preorder

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

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

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

  • height() - 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 súboru 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 menom name (postupnosť znakov ukončená b'\x00') a za tým nasleduje číslo number (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 (zápise do súboru) najprv zistiť maximálne číslo (pomocou metódy max_number()) 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ť troch bajtov, napríklad takto cislo.to_bytes(3, 'big')


Testovanie

Ak by si spustil tento test:

if __name__ == '__main__':
    e = Evidence()
    e.insert('NI', 7)
    e.insert('BL', 10)
    e.insert('TT', 6)
    e.insert('PO', 1)
    e.insert('BB', 2)
    e.insert('KE', 12)
    e.insert('KO', 7)
    e.printout()
    print('počet vrcholov =', len(e))
    print('výška stromu =', e.height())
    print('šírka stromu =', e.width())
    print('maximálne číslo =', e.max_number())
    print('súčet čísel =', e.total())

vypísalo by sa:

BB 2
BL 10
KE 12
KO 7
NI 7
PO 1
TT 6
počet vrcholov = 7
výška stromu = 3
šírka stromu = 3
maximálne číslo = 12
súčet čísel = 45

A samotný BVS by vyzeral takto:

_images/31_p1.png

Ak ešte zapíšeš:

e.save('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
42 42 00 02
4B 45 00 0C
4B 4F 00 07
54 54 00 06
50 4F 00 01

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 21. apríla, pričom sa v ňom bude nachádzať len jedna definícia triedy Evidence, trieda Node bude vnorená v triede Evidence

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

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

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