Cieľ cvičenia

V súbore binary_search_tree.py treba doplniť implementáciu tried TreeNode a BinarySearchTree tak, aby:

• data() vrátila koreň vytvoreného stromu,
• sorted_data() vrátila hodnoty stromu zoradené vzostupne,
• duplicitné hodnoty sa v strome zachovali.

Očakávané správanie je vidieť v súbore binary_search_tree_test.py.

Čo je binárny vyhľadávací strom?

Binárny strom sa skladá z uzlov. Každý uzol obsahuje hodnotu (data), odkaz na ľavého potomka (left) a odkaz na pravého potomka (right).

V binárnom vyhľadávacom strome platí pre každý uzol:

ľavý podstrom  <=  hodnota uzla  <  pravý podstrom

V tomto cvičení sa rovnaká hodnota vkladá doľava. Napríklad postupné vloženie hodnôt 4, 2, 6, 1, 3, 5, 7 vytvorí strom:

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

Strom nevzniká tak, že by sme vstupný zoznam najprv zoradili. Jeho tvar určuje poradie, v ktorom hodnoty vkladáme.

Ako strom urýchľuje vyhľadávanie

Ak hľadáme hodnotu x, porovnáme ju s hodnotou aktuálneho uzla:

• ak x == node.data, hodnotu sme našli,
• ak x < node.data, hľadáme iba v ľavom podstrome,
• ak x > node.data, hľadáme iba v pravom podstrome.

Pri každom porovnaní teda zahodíme celú vetvu, v ktorej sa hľadaná hodnota nemôže nachádzať. To je stromová obdoba binárneho vyhľadávania v zoradenom zozname. V tomto cvičení samostatná metóda na vyhľadávanie nie je požadovaná; rovnaké porovnávanie však používa algoritmus vkladania.

Ako vložiť jednu hodnotu

Pri vkladaní novej hodnoty začneme v koreni:

1. Ak strom ešte nemá koreň, nová hodnota sa stane koreňom.
2. Ak je nová hodnota menšia alebo rovná hodnote aktuálneho uzla, pokračujeme doľava.
3. Ak je väčšia, pokračujeme doprava.
4. Keď narazíme na prázdne miesto (None), vytvoríme tam nový TreeNode.

Pre BinarySearchTree(["4", "2", "6"]) teda platí: 4 je koreň, 2 <= 4 ide doľava a 6 > 4 ide doprava.

Vkladanie možno naprogramovať pomocnou rekurzívnou funkciou. Dôležitý je základný prípad: ak je aktuálny uzol None, funkcia musí vrátiť nový uzol. V ostatných prípadoch sa rekurzívne spracuje ľavý alebo pravý podstrom a výsledok sa priradí späť do current.left alebo current.right.

Pozor na konštruktor TreeNode: musí uložiť argumenty do atribútov, napríklad self.data = data, self.left = left a self.right = right. Ak ich vždy nastavíte na None, strom sa síce vytvorí, ale stratí všetky hodnoty.

Ako získať zoradené hodnoty

Na zoradenie stromu použite inorder prechod:

ľavý podstrom -> aktuálny uzol -> pravý podstrom

Pre uvedený strom je výsledok 1, 2, 3, 4, 5, 6, 7. Vlastnosť BST zaručuje, že inorder prechod navštívi hodnoty vo vzostupnom poradí. Keďže duplicitné hodnoty sa vkladajú doľava, prechod ich tiež zachová.

Praktický postup pre sorted_data():

1. vytvorte prázdny zoznam výsledkov,
2. rekurzívne prejdite ľavý podstrom,
3. pridajte hodnotu aktuálneho uzla do zoznamu,
4. rekurzívne prejdite pravý podstrom,
5. vráťte výsledný zoznam.

Pri prázdnom podstrome sa rekurzia okamžite skončí. Tento prípad je dôležitý pre listy aj pre chýbajúcich potomkov.

Rekurzia a zložitosť

Rekurzívna funkcia rieši menší problém rovnakým spôsobom: namiesto celého stromu spracuje ľavý alebo pravý podstrom. Zastaví sa pri None.

• vloženie jednej hodnoty trvá pri vyváženom strome približne O(log n),
• pri úplne naklonenom strome môže trvať O(n),
• inorder prechod celého stromu trvá O(n), pretože každý uzol navštívi raz.

Do výsledku nepridávajte None; None označuje iba prázdne miesto v strome. Taktiež nie je potrebné použiť vstavané sorted(): cieľom cvičenia je využiť práve vlastnosť binárneho vyhľadávacieho stromu.

Na čo si dať pozor

• Hodnoty zo vstupu ukladajte bez zbytočnej konverzie; testy pracujú s reťazcami, napríklad "4".
• Pri rovnosti použite pravidlo <=, aby sa duplikát vložil doľava.
• Pri rekurzívnom vkladaní nezabudnite výsledok priradiť potomkovi: node.left = insert(node.left, value) alebo analógicky doprava.
• data() má vrátiť objekt koreňa, nie jeho hodnotu a nie zoznam.
• sorted_data() má vrátiť nový zoznam hodnôt.
• Pri prázdnom vstupe si overte, čo povoľuje zadanie a testy; základným riešením je koreň None a prázdny výsledný zoznam.

Overenie riešenia

Testy spustíte z priečinka cvičenia príkazom:

python -m unittest -v

Najprv si overte jednoduché prípady:

tree = BinarySearchTree(["4", "2", "6"])
assert tree.data().data == "4"
assert tree.sorted_data() == ["2", "4", "6"]

Potom otestujte listy, duplikáty a hlbší strom. Pomocná metóda assertTreeEqual v testoch porovnáva aj presné umiestnenie ľavých a pravých potomkov, takže nestačí vrátiť iba správne zoradené hodnoty.

Užitočné odkazy na Python manuál

• Triedy a objekty – Python Tutorial – tvorba tried, konštruktor __init__ a atribúty objektu.
• Definovanie funkcií a return – parametre, návratová hodnota a rekurzívne volanie funkcie.
• Porovnávanie hodnôt – operátory <, <= a > použité pri rozhodovaní o smere v strome.
• Zoznamy a metóda append() – pridanie hodnoty do výsledného zoznamu pri inorder prechode.
• Vstavaná funkcia sorted() – referenčný príklad vstavaného triedenia; v tomto cvičení ju však nepoužívame ako náhradu za prechod stromom.
• Vstavaná funkcia len() – užitočná pri vlastnom uvažovaní o počte prvkov a zložitosti algoritmu.

Najdôležitejšie je pochopiť invariant stromu: po každom vložení musia byť hodnoty menšie alebo rovné vľavo a väčšie vpravo. Ak tento invariant platí, inorder prechod automaticky poskytne zoradený výsledok.