7. 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, self.left, self.right = data, left, right

    def __init__(self, postupnost=None):
        self.root = None
        for hodnota in postupnost or []:
            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 rek(vrch):
            if vrch is None:
                return 0
            return 1 + rek(vrch.left) + rek(vrch.right)
        return rek(self.root)

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

    def __contains__(self, hodnota):
        def rek(vrch):
            if vrch is None:
                return False
            return vrch.data == hodnota or rek(vrch.left) or rek(vrch.right)
        return rek(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 (teda rekurzívne) preliezť často 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 14 vrcholov a jeho výška je 5:

../_images/l07_1a.png

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 55

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

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

../_images/l07_1b.png
  • 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 35 - zrejme stačí pozerať ľavý podstrom (tu je jeho koreň 27):

../_images/l07_2a.png

Ak by aj tento náš podstrom mal túto istú vlastnosť (vľavo sú len menšie ako 27 a vpravo len väčšie ako 27), 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 35 a to je väčšie ako koreň podstromu 27, stačí túto hodnotu hľadať v pravom podstrome od vrcholu 27:

../_images/l07_2b.png

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 pokračovať:

../_images/l07_2c.png

Po štvrtom porovnaní môžeme vidieť, že hľadaná hodnota 35 sa v tomto strome nenachádza:

../_images/l07_2d.png

Hľadanie v takomto strome zapíšeme 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 listom stromu

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

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

Porovnajte túto metódu s podobnou v pôvodnom binárnom strome, ktorá pridávala nové vrcholy na náhodné pozície v strome. Môžete vidieť, že tieto dve funkcie sa líšia len v dvoch riadkoch:

class BinarnyStrom:
    ...

    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

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.


Vyhodenie vrcholu zo stromu

Ďalej budeme uvažovať o vyhadzovaní vrcholu BVS tak, aby pre tento strom stále zostala vlastnosť BVS a pritom sme ho nemuseli celý prerábať.

Základnou ideou je zjednodušene toto:

  • nájdeme vyhadzovaný vrchol a ak je to list (nemá potomkov), jednoducho ho vyhodíme (nahradíme None)

  • ak je to vnútorný vrchol s jediným synom, tak tento vrchol môžeme vyhodiť tiež a namiesto neho otcovi nastavíme podstrom s týmto jedným existujúcim synom

  • ak je to vrchol, ktorý má oboch synov, tak v podstrome ľavého syna (tam sú všetci menší, ako vyhadzovaný vrchol) nájdeme vrchol s najväčšou hodnotou (stačí ísť v podstrome stále vpravo, kým sa dá): tento vrchol už určite nemá pravého syna (inak by nebol najväčší), tak ho vyhodíme a jeho hodnotu dáme namiesto pôvodne vyhadzovaného vrcholu

Uvažujme teda metódu vyhod(), ktorá vyhodí zo stromu zadaný prvok (ak sa v strome nachádza), pričom zachová BVS vlastnosť. Budú pritom tieto prípady:

  • vrchol sa tam nenachádza a teda nie je čo robiť

  • vyhadzovaný vrchol je list (nemá žiadnych synov), tak ho stačí zrušiť a teda jeho otcovi nastaviť None

  • vyhadzovaný vrchol má len jedného syna: vrchol vyhodíme a v strome ho nahradíme jeho jediným synom

  • ak má rušený vrchol oboch synov:

    • vyhadzovaný vrchol (nazveme ho vrch) naozaj nevyhodíme, ale nahradíme ho iným obsahom tak, aby nepokazil zvyšok stromu

    • z ľavého podstromu tohoto vrcholu (všetky majú hodnotu menšiu ako vrch) vyberieme najväčšiu a tá sa stane novým obsahom vrch - všetky zvyšné vrcholy v ľavom podstrome majú menšiu hodnotu a v pravom podstrome vrch sú aj tak všetky hodnoty väčšie - preto je táto hodnota dobrým kandidátom, aby nahradila hodnotu vrch

    • maximálna hodnota v BVS sa hľadá veľmi jednoducho: stačí prechádzať po pravých synoch a keď narazíme na vrchol, ktorý už pravého syna nemá, toto je maximálny vrchol:

      max = vrch.left
      while max.right:
          max = max.right
      
    • prekopírujeme obsah tohto vrcholu do vrch a samotný tento vrchol teraz môžeme jednoducho vyhodiť, keďže tento určite nemá pravého syna (buď je to list alebo má iba jedného syna)


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, č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
            hodn1 = hodnota(vrch.left)
            hodn2 = hodnota(vrch.right)
            if vrch.data == '+':
                return hodn1 + hodn2
            if vrch.data == '-':
                return hodn1 - hodn2
            if vrch.data == '*':
                return hodn1 * hodn2
            if vrch.data == '/':
                return hodn1 // hodn2
            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

Prefixový strom - Trie


je stromová dátová štruktúra, v ktorej uchovávame nejakú zadanú množinu reťazcov. Predpokladáme, že v tejto množine budeme potrebovať veľmi rýchlo hľadať buď celé slová alebo ich prefixy (začiatky slov) alebo slová s daným prefixom. Táto stromová štruktúra využíva to, že sa každé takto uložené slovo rozloží na písmená a táto postupnosť písmen potom tvorí cesty ku niektorým vrcholom stromu. Tejto štruktúre sa hovorí Trie (v angličtine sa číta ako slovo „try“) ale niekedy aj prefixový, písmenkový alebo znakový strom. Dá sa nájsť aj s názvom lexikografický strom.

Každý vrchol tohto stromu má toľko podstromov, koľko rôznych písmen z tohto vrcholu pokračuje. Každá takáto hrana k podstromu je označená príslušným písmenom.

Najlepšie to vysvetlíme na takomto príklade: zostrojíme trie, ktorý bude uchovávať túto množinu slov: {bear, bell, bid, bull, buy, sell, stock, stop}.

  • z koreňa stromu budú vychádzať dve hrany (dva podstromy), lebo všetky slová začínajú písmenom 'b' alebo 's':

  • jeden podstrom bude obsahovať všetky slová na 'b': {bear, bell, bid, bull, buy} a druhý slová na 's': {sell, stock, stop}

  • podstrom pre 'b' bude mať toľko synov (podstromov), koľko je rôznych druhých písmen v slovách: sú to 'e', 'i', 'u'

    • takže prvý jeho podstrom bude uchovávať slová s 'e': {bear, bell}

    • druhý slová s 'i': {bid}

    • tretí s 'u': {bull, buy}

  • podobne podstrom pre prvé písmeno 's' sa bude rozvetvovať podľa druhých písmen slov {sell, stock, stop}, teda na dva podstromy 'e', 't':

    • jeho prvý podstrom bude uchovávať slová, ktoré začínajú 's' a druhé písmeno je 'e': {sell}

    • druhý slová s druhým písmenom 't': {stock, stop}

  • takto by sme pokračovali, kým by sme nerozobrali na písmená všetky slová

Zrejme výška stromu je daná dĺžkou najdlhšieho slova, ktoré je uložené v strome, v našom prípade je to slovo 'stock', teda výška je 5. V tomto prípade všetky slová končia v listoch stromu, lebo žiadne z nich nie je prefixom nejakého iného. Toto je v niektorých aplikáciách trie podmienkou: všetky slová musia končiť v listoch stromu a teda žiadne nie je prefixom iného. Inokedy nám to nevadí a vtedy treba nejakú informáciu o tom, že nejaký vnútorný vrchol stromu je koncovým písmenkom nejakého slova. Ak by sme do tohto stromu chceli vložiť aj anglické slovo 'be', museli by sme príslušný vrchol (z ktorého pokračujú zvyšné písmená pre 'bear' a 'bell') nejako označiť (atribút s príznakom konca) alebo by sme na koniec každého slova prilepili nejaký špeciálny koncový znak napríklad '#'.

Vrchol prefixového stromu definujeme najčastejšie takto:

class Vrchol:
    def __init__(self):
        self.data = None
        self.child = []

teda každý vrchol môže obsahovať nejakú informáciu (napríklad, že je to koncový vrchol nejakého slova) a zoznam všetkých svojich podstromov spolu s informáciou, ktorému znaku tento podstrom zodpovedá. Do zoznamu child budeme teda ukladať dvojice (znak, vrch).

Vložiť nové slovo do stromu znamená:

class Trie:

    class Vrchol:
        def __init__(self):
            self.data = None
            self.child = []

    def __init__(self):
        self.root = self.Vrchol()

    def vloz(self, slovo, data=1):
        vrch = self.root
        for znak in slovo:
            for znak1, vrch1 in vrch.child:
                if znak1 == znak:
                    break
            else:
                vrch1 = self.Vrchol()
                vrch.child.append((znak, vrch1))
            vrch = vrch1
        vrch.data = data

Všimnite si, vnútorný for-cyklus, ktorý má else vetvu: príkazy v tejto else vetve sa vykonajú len vtedy, keď samotný for-cyklus preverí všetky možnosti (všetky prvky zoznamu vrch.child) a všetky majú iný ako hľadaný znak. Teda else vetva vo for-cykle sa nevykoná, keď sa z cyklu vyskočí pomocou break.

Slová do stromu pridáme, napríklad takto:

t = Trie()
for slovo in 'bear bell bid bull buy sell stock stop'.split():
    t.vloz(slovo)

Dostávame takýto prefixový strom:

../_images/l07_14.png

Uvedomte si, že vo vrcholoch tohto stromu sa naozaj nenachádzajú tie znaky, ktoré sú tu zobrazené. Presnejšie by bolo, keby sme ich kreslili na hrany stromu, napríklad takto:

../_images/l07_15.png

Pre jednoduchšie vykresľovanie sa častejšie volí vypisovanie znakov vo vrcholoch stromu.

Pomocou rekurzívnej funkcie vieme vygenerovať všetky uložené slová v takomto strome:

class Trie:
    ...

    def all(self, vrch, slovo=''):
        if vrch.data is not None:
            yield slovo
        for znak1, vrch1 in vrch.child:
            yield from self.all(vrch1, slovo + znak1)
for slovo in t.all(t.root):
    print(slovo)

Vieme z toho urobiť iterátor:

class Trie:
    ...

    def __iter__(self):
        return self.all(self.root)

teraz môžeme získať všetky slová z tohto stromu:

list(t)

alebo vypísať:

print(*t)

Vďaka prefixovému stromu vieme veľmi jednoducho získať všetky slová, ktoré majú zadaný prefix:

class Trie:
    ...

    def prefix(self, slovo):
        vrch = self.root
        for znak in slovo:
            for znak1, vrch1 in vrch.child:
                if znak1 == znak:
                    vrch = vrch1
                    break
            else:
                return None
        return self.all(vrch, slovo)

napríklad, môžeme otestovať súbor s anglickými slovami text5.txt:

t = Trie()
with open('text5.txt') as f:
    for w in f.read().split():
        t.vloz(w)
print(len(list(t)))

Vidíme, že sa vytvoril trie s 67527 slovami. Môžeme experimentovať s hľadaním všetkých slov, ktoré majú rovnaký nejaký prefix, napríklad:

>>> print(*t.prefix('tree'))
    tree treehopper treenail trees
>>> print(*t.prefix('trie'))
    tried triennial triennium trier
>>> print(*t.prefix('pyth'))
    pythagoras pythagorean pythagorism pythia pythiaceae pythian pythias
    pythium pythius python pythoness pythonidae pythoninae

Cvičenia


Vyhľadávacie stromy

  1. Zisti, či tento strom spĺňa podmienky BVS (nemusíš to programovať, stačí ručne)

    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. Okrem tejto metódy zapíš aj metódu kontrola(), ktorá vráti True, ak je je binárny strom korektným binárnym vyhľadávacím stromom:

    import tkinter
    from math import inf     # nekonečno
    
    class BVS:
        canvas = None
        ...
    
        def kresli(self):
            ...
    
        def kontrola(self):
            def rek(vrch, min, max):
                if vrch is None:
                    return True
                ...
            return rek(self.root, -inf, inf)
    

    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()
    print(s.kontrola())
    

    Zrejme by sa malo vypísať False. Zmeń zadanie tohto stromu, aby sa vypísalo True.

    Metódu kontrola() môžeš namiesto vnorenej rekurzívnej funkcie riešiť pomocou metódy inorder().


  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 generátory inorder() a preorder() (využi predchádzajúcu prednášku):

    class BVS:
        ...
    
        def inorder(self):
            ...
    
        def preorder(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()
    >>> list(s.inorder()) == 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()
    >>> s1 = BVS(zoz1)
    >>> s1.kresli()
    

    Oba tieto stromy by mali vyzerať rovnako.


  1. * Do triedy BVS doplň metódy vyhod_pom(pred, vrch) a vyhod(hodnota), ktoré umožnia vyhodiť vrchol s danou hodnotou z BVS. Metódy budú fungovať takto:

    • pomocná metóda vyhod_pom(pred, vrch) dostane referenciu na vyhadzovaný vrchol vrch a referenciu na jeho rodiča pred -> metóda korektne vyhodí vrchol vrch, ktorý je listom alebo má iba jedného potomka:

      • ak je tento rodič None, zrejme vrch je koreňom;

      • ak by bola táto metóda zavolaná pre vrchol s dvomi potomkami, vyvolá výnimku TypeError

    • metóda vyhod(hodnota) korektne vyhodí vrchol so zadanou hodnotou z BVS:

      • najprv vyhľadá zadanú hodnotu (podobne ako __contains__) pritom si pre tento nájdený vrchol vrch zapamätá aj jeho rodiča pred, keďže pri vyhadzovaní ho bude potrebovať;

      • ak má nájdený vrchol oboch potomkov, nájde vrchol s maximálnou hodnotou v ľavom podstrome (pritom si zapamátá jeho rodiča ako pred), jeho hodnotu priradí do vrch a maximálny vrchol vyhodí pomocou metódy vyhod_pom;

      • pomocnú metódu vyhod_pom využije aj vtedy, keď vyhadzovaný vrchol je je listom alebo má iba jedného potomka;

      • ak sa zadaná hodnota nenachádza v BVS, metóda vyvolá výnimku KeyError(hodnota)

    Metódu otestuj na stromoch z predchádzajúcich úloh.


  1. * 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/l07_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 zoznamu 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()
    

Prefixové stromy


  1. Nakresli bez počítača prefixový strom pre množinu slov:

    {pes, slon, prasa, tiger, slak, pero, prak, tuja, tik, slina, tunel}
    

    Zisti

    • koľko vrcholov má tento strom

    • koľko je v ňom takých vnútorných vrcholov, v ktorých nekončí žiadne slovo

    • aký je stupeň tohto stromu

      • stupňom vrcholu je počet hrán, ktoré z neho vychádzajú

      • stupňom celého stromu je maximum zo všetkých stupňov vrcholov (binárny strom má stupeň 2)

    • aká množina slov vznikne pre prefix 'sl'


  1. * V triede Trie z prednášky spojazdni a otestuj tieto metódy:

    • vloz

    • all

    • prefix

    • __iter__

    • __len__

    Otestuj ich na niektorých zo súborov: text1.txt, text5.txt, dobs.txt, twain.txt. Napríklad takto:

    t = Trie()
    with open('dobs.txt', encoding='utf-8') as file:
        for slovo in file.read().split():
            t.vloz(slovo)
    print(len(t))
    print(len(list(t)))
    print(list(t.prefix('boh')))
    

    Do triedy Trie pridaj aj metódu na vykreslenie stromu:

    class Trie:
        ...
    
        canvas = None
    
        def kresli(self, vrch=None, znak='"', width=None, x=None, y=None):
    
            def sipka(x1, y1, x2, y2, r=15, farba='black', hrubka=1):
                d = ((x1-x2)**2+(y1-y2)**2)**.5
                xx, yy = (x2-x1)*r/d, (y2-y1)*r/d
                self.canvas.create_line(x1+xx, y1+yy, x2-xx, y2-yy, width=hrubka, fill=farba, arrow='last')
    
            if self.canvas is None:
                self.canvas = tkinter.Canvas(bg='white', width=1000, height=800)
                self.canvas.pack()
            if vrch is None:
                self.canvas.delete('all')
                vrch = self.root
                if width is None: width = int(self.canvas['width'])-20
                if x is None: x = 10
                if y is None: y = 30
            n = len(vrch.child)
            x0 = x + width // 2
            if n > 0:
                width1 = width // n
                for i, (znak1, vrch1) in enumerate(sorted(vrch.child)):
                    sipka(x0, y, x+i*width1+width1//2, y + 50)
                    self.kresli(vrch1, znak1, width1, x+i*width1, y + 50)
            f = 'white' if vrch.data is None else 'lightgray'
            self.canvas.create_oval(x0-15, y-15, x0+15, y+15, fill=f)
            self.canvas.create_text(x0, y, text=znak, font='courier 12 bold')
            if vrch is self.root:
                self.canvas.update()
                self.canvas.after(500)
    

    Môžeš otestovať, napríklad takto:

    t = Trie()
    for slovo in ... slová z úlohy (14) ... :
        t.vloz(slovo)
        t.kresli()
    while slovo:
        slovo = input('zadaj slovo: ')
        t.vloz(slovo)
        t.kresli()
    

7. Týždenný projekt


Implementuj triedu Repository, ktorá sa bude správať podobne ako asociatívne pole. Kľúčmi budú len znakové reťazce a budú sa ukladať do prefixového stromu a asociovaná hodnota sa potom priradí do príslušného vrcholu stromu (atribút value).

Na riešenie úlohy použi tieto deklarácie (sú aj v súbore riesenie.py v LISTe):

class Repository:
    class Node:
        def __init__(self, value=None):    # vrchol prefixového stromu
            self.value = value
            self.child = None    # spájaný zoznam typu Child - spájaný zoznam podstromov

    class Child:
        def __init__(self, char, node=None, next=None):
            self.char = char
            self.node = node     # podstrom typu Node
            self.next = next     # nasledovný prvok spájaného zoznamu

    def __init__(self):
        self.root = None         # prázdny strom
        ...

    def __setitem__(self, key, value):
        ...

    def __getitem__(self, key):
        raise KeyError

    def __delitem__(self, key):
        raise KeyError

    def node_count(self):
        return 0

    def __len__(self):
        return 0

    def __iter__(self):
        yield ...

Prefixový strom bude uchovávať v každom vrchole (typu Node) spájaný zoznam s informáciami o podstromoch. Prvky tohto spájaného zoznamu budú typu Child.

Metódy:

  • __setitem__(key, value) pre daný kľúč priradí príslušnú hodnotu.

  • __getitem__(key) pre daný kľúč vráti príslušnú hodnotu, resp. vyvolá chybu KeyError, ak taký kľúč neexistuje.

  • __delitem__(key) vymaže daný kľúč (resp. vyvolá chybu KeyError), do atribútu value priradí None.

  • node_count() vráti počet vrcholov (typu Node) v celom prefixovom strome: prázdny strom má tento počet 0, strom s jediným kľúčom '' má tento počet 1, strom s jediným kľúčom napr. 'a' má tento počet 2 (aj strom s dvoma kľúčmi '' a 'a' má tento počet 2), atď.

  • __iter__() vráti iterátor všetkých kľúčov v strome, zrejme tieto kľúče môže vrátiť v ľubovoľnom poradí.

Vnorené triedy Repository.Node a Repository.Child nemeň (testovač aj tak použije jeho pôvodnú verziu). Vrcholy v strome, ktoré nereprezentujú kľúč, budú mať v atribúte Node.value hodnotu None.

V inštancii triedy Repository nepoužívaj žiadne attibúty zložených typov (napríklad dict, list, …). Môžeš definovať nejaké pomocné metódy.

Program môžeš testovať, napríklad takto:

if __name__ == '__main__':
    m = Repository()
    for w in 'mama ma emu a ema ma mamu'.split():
        try:
            m[w] = m[w] + 1
        except KeyError:
            m[w] = 1

    print(list(m), m.node_count(), len(m))
    ww = list(m)
    for w in ww:
        del m[w]
        print(w, m.node_count(), len(m))

Výpis potom bude takýto:

['a', 'ema', 'emu', 'ma', 'mamu', 'mama'] 11 6
a 11 5
ema 11 4
emu 11 3
ma 11 2
mamu 11 1
mama 11 0

Aby si mohol spúšťať testy, program ulož do súboru riesenie.py a odovzdaj na úlohový server L.I.S.T.. Na začiatok súboru pridaj tieto tri komentárové riadky (so svojim menom a dátumom):

# 7. zadanie: repository
# autor: Janko Hrasko
# datum: 12.4.2024