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.

from random import randrange as rr

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

    def __init__(self, pole=None):
        self.root = None
        if pole is not None:
            for hodnota in pole:
                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 rr(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(rr(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.

30.1. 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 - 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 (jeho koreň je 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, 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, pole=None):
        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)
                        break
                    vrch = vrch.left
                else:
                    if vrch.right is None:
                        vrch.right = self.Vrchol(hodnota)
                        break
                    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.

30.2. Aritmetický strom

Takýto binárny strom by pre nás mohol byť dobre pochopiteľ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

30.3. 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 každý vrchol mať ľubovoľný počet svojich synov. Zapíšme definíciu triedy aj s niekoľkými užitočnými metódami:

from random import randrange as rr
import tkinter

class VseobecnyStrom:
    canvas = None
    class Vrchol:
        def __init__(self, data):
            self.data = data
            self.syn = []

    def __init__(self):
        self.root = None

    def __len__(self):

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

        return pocet_rek(self.root)

    def __repr__(self):

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

        return repr1(self.root)

    def pridaj_nahodne(self, *pole):

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

        for hodnota in pole:
            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.syn)
            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.syn[i], sir0//2, x1, y1)
            self.canvas.create_oval(x-15, y-15, x+15, y+15, fill='lightgray', outline='')
            self.canvas.create_text(x, y, text=vrch.data, font='consolas 14')

        if self.canvas is None:
            VseobecnyStrom.canvas = tkinter.Canvas(bg='white', width=800, height=400)
            self.canvas.pack()
        self.canvas.delete('all')
        kresli_rek(self.root, 380, 400, 40)

Otestujeme:

strom = VseobecnyStrom()
strom.pridaj_nahodne(*(rr(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. takto:

všeobecný strom

a výpis

pocet vrcholov v strome = 20
strom = (43,(68,(44,(67,(5,(54))),(70,(55)))),(25,(16),(87,(32)),(82)),(17,(41,(95,(53))),(8)),(14,(61)))

keby sme do __repr__() pridali 2 riadky:

def __repr__(self):

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

    return repr1(self.root)

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

>>> strom
(43,(68,(44,(67,(5,54)),(70,55))),(25,16,(87,32),82),(17,(41,(95,53)),8),(14,61))

30.4. Cvičenie

Vyhľadávacie stromy

  1. Zistite, či tento strom spĺňa podmienky BVS
binárny strom
  1. Ručne nakreslite strom, ktorý by vznikol postupným pridávaním
  • týchto hodnôt:
'KE', 'BB', 'PO', 'PE', 'PK', 'BA', 'BS', 'NI', 'SC', 'BL', 'RK', 'BR'
  1. Dopíšte do stromu na obrázku čísla z postupnosti range(1, 21) tak, aby vznikol BVS:
binárny strom
  1. Spojazdnite triedu BVS z prednášky a pridajte do nej metódu na vykreslenie stromu z predchádzajúcej prednášky
  • preverte správnosť vášho riešenia pre strom:
s = BVS()
v = BVS.Vrchol
s.root = v(17, v(3, v(1, None, v(4)), v(5)), v(20, v(19, v(18), v(21)), v(23)))
s.kresli()
  1. Vylepšite inicializáciu __init__() triedy BVS tak, aby mohla mať nepovinný druhý parameter pole - zadaná postupnosť hodnôt, z ktorej sa vytvorí BVS (volaním metódy vloz())
  • funkčnosť otestujte napr.
s = BVS('KE BB PO PE PK BA BS NI SC BL RK BR'.split())
s.kresli()
  1. Do triedy BVS zapíšte metódy min() a max(). Tieto by mali vrátiť minimálnu, resp. maximálnu hodnotu
  • využite 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. Doplňte do triedy BVS metódy inorder_list() a preorder_list() (môžete využiť predchádzajúcu prednášku)
  • prekontrolujte, či inorder postupnosť vracia usporiadanú postupnosť všetkých hodnôt v strome
>>> pole = [... nejaká náhodná postupnosť ...]   # nemali by sa v nej opakovať žiadne hodnoty
>>> s = BVS(pole)
>>> s.inorder_list() == sorted(pole)
True
  • prekontrolujte, či z preorder postupnosti sa dá skonštruovať BVS rovnakého tvaru
>>> 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 preusporiadajte tak, aby BVS, ktorý vznikne postupným pridávaním prvkov tejto preusporiadanej postupnosti, bol skoro úplný. Idea by mohla byť takáto
  • usporiadajte danú postupnosť (napr. pomocou sorted())
  • stredný prvok bude prvý (ďalší) vo výsledku
  • rekurzívne spracuj prvú polovicu (po stredný prvok)
  • rekurzívne spracuje 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. Spojazdnite triedu AritmetickyStrom z prednášky a doplňte do nej metódu na vykresľovanie stromu
  • otestujte na príklade stromu z prednášky
  1. Dopíšte 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
  2. Do inicializácie __init__() dopíšte 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 pole prvkov
  • postupne prechádza prvky poľa:
  • 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
  • otestujte napr.
>>> s = AritmetickyStrom('5 1 3 + * 15 3 / +')

Všeobecné stromy

  1. Do triedy VseobecnyStrom napíšte metódy:
  • preorder() - vráti postupnosť hodnôt v poli (typu list)
  • vyska() - zistí výšku stromu
  • pocet_listov() - zistí počet listov stromu

30.5. Domáce zadanie

Napíšte modul s menom uloha7.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, pole=None):
        self.root = None
        ...

    def vloz(self, data):
        ...

    def inorder_list(self):
        return []

def tree_sort(pole):
    return BVS(pole).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) objavit 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__(pole) z prvkov poľa 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 pole (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 postupnosť všetkých prvkov v strome v tvare pythonovský list; zrejme toto výsledné pole bude obsahovať rovnaké prvky ako pôvodné pole 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 uloha7.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ť:

    # autor: Janko Hrasko
    # uloha: 7. domace zadanie tree_sort
    
  • 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 uloha7.py pridať testovacie riadky, ktoré ale testovač vidieť nebude, napr.:

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

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