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 vrcholmi. 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. Napr.

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.

>>> 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 len 25 vrcholov a jeho hĺbka je len 4:

binárny strom

Skúsme popísať asi akú vlastnosť majú hodnoty vo vrcholoch tohoto 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 a vpravo len väčšie), 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 (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 bol správny BVS.

Vytvorme najprv BVS, priamym priradením vrcholov do root, napr. 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 nepokazilo pravidlo BVS. Ak by sme chceli do nášho malého ukážkového stromu pridať, napr. 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. 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. len pravých synov. Strom sa 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. 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

Takýto binárny strom by pre nás mohol byť 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. '+', '-', '*', '/', 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. 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', outline='')
            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. 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

v reprezentácii syn-brat by to vyzeralo 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', 'BB', 'PO', 'PE', 'PK', 'BA', 'BS', 'NI', 'SC', 'BL', 'RK', 'BR'
      

  1. Dopíš do stromu na obrázku čísla z postupnosti range(1, 21) 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.

    • prever správnosť tohto riešenia pre strom:

      s = BVS()
      v = BVS.Vrchol
      s.root = v(17, v(3, v(1, None, v(2)), v(5)), v(20, v(19, v(18), 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()).

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

      s = BVS('KE BB PO PE PK BA BS NI SC BL 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

      >>> # strom z predchádzajúceho príkladu
      >>> s.max()
      'SC'
      >>> s.min()
      'BA'
      

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

    • prekontroluj, či inorder postupnosť vracia usporiadanú postupnosť všetkých hodnôt v strome, napr. takto

      >>> zoznam = [... nejaká náhodná postupnosť ...]   # nemali by sa v nej opakovať žiadne hodnoty
      >>> s = BVS(zoznam)
      >>> s.inorder_list() == sorted(zoznam)
      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(... nejaká postupnosť ...)
      >>> s.kresli()
      >>> s1 = BVS(s.preorder_list())
      >>> 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. 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)


Aritmetické stromy

  1. Ručne (na papieri) nakresli strom pre 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

    • otestuj na príklade stromu z prednášky


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


  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

    • otestuj napr.

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

Všeobecné stromy

  1. Oprav definíciu triedy VseobecnyStrom tak, aby sa pri inicializácii vrcholov mohli uviesť aj referencie na podstromy. Zrejme inicializácia bude __init__(self, data, *child)

    • napr.

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



7. Domáce zadanie

L.I.S.T.

Napíšte modul s menom riesenie7.py, ktorý bude obsahovať jedinú triedu s ďalšou vnorenou podtriedou, tromi metódami a jednou funkciou:

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

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

    def vloz(self, data):
        ...

    def inorder_list(self):
        return []

def tree_sort(zoznam):
    return BVS(zoznam).inorder_list()

Trieda BVS implementuje binárny vyhľadávací strom a pomocou neho algoritmus, ktorý triedi postupnosť údajov, tzv. tree_soft. Ak by sa mala nejaká hodnota (tzv. kluc) objaviť v BVS viackrát, v strome bude tento kľúč len raz, ale v príslušnom vrchole sa zapamätajú všetky hodnoty s týmto kľúčom presne v tom poradí, ako sa objavili vo vstupnej postupnosti (najlepšie v ďalšom atribúte vrcholu, ktorý bude typu list).

Metódy triedy BVS by mali mať túto funkčnosť (môžete si dodefinovať aj ďalšie pomocné metódy):

  • metóda __init__(postupnost) z prvkov danej postupnosti vytvorí binárny vyhľadávací strom, jeho koreň bude v atribúte root, použite na to metódu vloz();

  • metóda vloz(data) pridá do BVS stromu nový prvok; ak je týmto pridávaným prvkom zoznam (list alebo tuple), tak sa ako kľúč použije len jeho prvý prvok, ale zapamätá sa jeho kompletná hodnota;

  • metóda inorder_list() vráti inorder zoznam (list) všetkých prvkov v strome; zrejme tento výsledný zoznam bude obsahovať rovnaké prvky ako pôvodná postupnosť ale možno v inom poradí; pri testovaní sa môžu objaviť také údaje, pri ktorých môže spadnúť rekurzívna verzia tejto metódy.

Obmedzenia

  • vaše riešenie odovzdajte v súbore riesenie7.py, pričom sa v ňom bude nachádzať len jedna definícia triedy BVS, trieda Vrchol bude vnorená v triede BVS

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

    # 7. zadanie: tree-sort
    # autor: Janko Hrasko
    # datum: 7.4.2019
    
  • zrejme ako autora uvediete svoje meno

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

  • váš program by nemal počas testovania testovačom nič vypisovať (žiadne vaše testovacie print())

Testovanie

Keď budete spúšťať vaše riešenie na svojom počítači, môžete do súboru riesenie7.py pridať testovacie riadky, ktoré ale testovač vidieť nebude, napr.:

if __name__ == '__main__':
    zoz = (10, 20, 30, 5, 15)
    print(tree_sort(zoz))
    zoz = [(10,), (20,), (30,), (5,), (15,)]
    print(tree_sort(zoz))
    zoz = [('b',6), ('d',7), ('e',8), ('a',9), ('b',10),
           ('b',1), ('d',2), ('e',3), ('a',4), ('b',5)]
    print(tree_sort(zoz))
    zoz = ['prvy', ('druhy',), ['treti'], ('stvrty', 1),
           ['piaty', 2], ('siesty', 'x'), ['siedmy', 'y']]
    print(tree_sort(zoz))

Tento test by vám mal vypísať:

[5, 10, 15, 20, 30]
[(5,), (10,), (15,), (20,), (30,)]
[('a', 9), ('a', 4), ('b', 6), ('b', 10), ('b', 1), ('b', 5), ('d', 7), ('d', 2), ('e', 8), ('e', 3)]
[('druhy',), ['piaty', 2], 'prvy', ['siedmy', 'y'], ('siesty', 'x'), ('stvrty', 1), ['treti']]