Binárny vyhľadávací strom

Úloha: Binary Search Tree na Exercisme

Čo sa v cvičení naučíte

Po vyriešení cvičenia budete vedieť:

• vysvetliť, z akých uzlov sa skladá binárny vyhľadávací strom,
• vytvoriť triedu, ktorej objekty obsahujú hodnotu a odkazy na ľavý a pravý podstrom,
• vkladať čísla na správne miesto podľa ich porovnania s hodnotou v uzle,
• používať None na označenie chýbajúceho potomka,
• prechádzať strom rekurzívne,
• implementovať inorder priechod stromom, teda v poradí ľavý podstrom – uzol – pravý podstrom,
• vytvoriť generátor pomocou yield a postupne z neho získavať hodnoty,
• pochopiť, prečo inorder priechod binárneho vyhľadávacieho stromu vráti hodnoty zoradené vzostupne,
• rozlíšiť správne riešenie od riešenia, ktoré funguje iba pre vyvážený alebo iba pre úplný strom.

Čo si musíte preštudovať

Pred riešením si prečítajte celé zadanie na Exercisme. Obsahuje popis dátovej štruktúry aj obrázky, podľa ktorých si môžete skontrolovať, kam sa majú hodnoty vložiť.

Uzol a binárny vyhľadávací strom

Binárny strom je tvorený uzlami. Každý uzol má:

• data – uloženú hodnotu,
• left – odkaz na ľavý podstrom alebo None,
• right – odkaz na pravý podstrom alebo None.

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

• hodnoty v ľavom podstrome sú menšie alebo rovné hodnote uzla,
• hodnoty v pravom podstrome sú väčšie než hodnota uzla.

Preštudujte si pojem strom a binárny vyhľadávací strom. Nakreslite si napríklad postupné vloženie hodnôt 4, 2, 6, 3, 1, 5, 7. Pomôže vám to sledovať, že pri vkladaní sa vždy rozhoduje iba podľa aktuálneho uzla.

Triedy, konštruktor a atribúty objektu

Riešenie má používať triedu BinarySearchTree. Jej konštruktor vytvorí koreňový uzol s danou hodnotou a nastaví left aj right na None.

Zopakujte si:

• definovanie triedy pomocou class,
• metódu __init__,
• parameter self,
• vytváranie a zmenu atribútov objektu.

Užitočné časti Python manuálu:

• Triedy – Python Tutorial,
• mená a objekty,
• referenčná dokumentácia k triedam.

Porovnávanie a podmienky

Metóda insert(data) musí hodnotu vložiť do ľavého alebo pravého podstromu:

1. porovnajte novú hodnotu s self.data,
2. pri hodnote menšej alebo rovnakej pokračujte do left,
3. pri väčšej hodnote pokračujte do right,
4. ak je vybraný potomok None, vytvorte tam nový uzol,
5. inak pokračujte v jeho podstrome.

Zopakujte si relačné operátory <= a > a vetvenie if/else v riadiacich štruktúrach Pythonu. Dôležité je rozhodnúť, kam patria duplicitné hodnoty: podľa zadania patria do ľavého podstromu.

Rekurzia

Pri vkladaní aj pri prechode stromom môžete rovnakú operáciu zopakovať na ľavom alebo pravom potomkovi. To je prirodzený príklad rekurzie: metóda zavolá samu seba na menšom podprobléme.

Pred použitím rekurzie si ujasnite:

• základný prípad – napríklad keď je miesto pre nový uzol prázdne,
• rekurzívny krok – pokračovanie v left alebo right,
• prečo sa v každom kroku približujete k None a rekurzia sa skončí.

Prečítajte si definovanie funkcií a príklad rekurzívnej funkcie. Riešenie možno napísať aj iteratívne pomocou while, ale pri each() treba správne zachovať poradie hodnôt.

Inorder priechod a yield

Metóda each() má vrátiť hodnoty v poradí:

1. najprv všetky hodnoty z left,
2. potom self.data,
3. nakoniec všetky hodnoty z right.

Tento postup sa volá inorder priechod. Ak metóda používa yield, stane sa z nej generátor a hodnoty môže odovzdávať postupne:

for value in tree.each():
    print(value)

Preštudujte si generátory a yield a generátorové funkcie v referenčnej príručke. Všimnite si rozdiel medzi yield, ktoré odovzdá jednu hodnotu, a return, ktoré ukončí funkciu.

Práca s None

Pri vkladaní treba rozlíšiť, či left alebo right ešte neukazuje na uzol. Na to slúži porovnanie s None, napríklad:

if self.left is None:
    # na tomto mieste vytvoríme nový uzol

Používajte is None, nie porovnávanie hodnoty nového uzla s None. Zopakujte si špeciálne hodnoty a konštantu None a booleovské operácie.

Ako postupovať pri riešení

1. Spustite pripravené testy a prečítajte si názvy testovacích prípadov.
2. V konštruktore vytvorte koreňový uzol a nastavte jeho potomkov na None.
3. Nakreslite si strom po niekoľkých volaniach insert() vrátane duplicitnej hodnoty.
4. Implementujte vkladanie: pri prázdnom odkaze vytvorte nový objekt, pri neprázdnom odkaze pokračujte v príslušnom podstrome.
5. Implementujte each() ako inorder priechod. Najprv spracujte ľavý podstrom, potom aktuálny uzol a nakoniec pravý podstrom.
6. Otestujte strom s jedným uzlom, s hodnotami na oboch stranách, s duplicitami a s výrazne nevyváženým stromom.
7. Overte, že výsledok list(tree.each()) je zoradený a že sa v ňom zachovajú aj duplicitné hodnoty.

Na čo si dať pozor

• left a right sú odkazy na ďalšie objekty BinarySearchTree, nie zoznamy hodnôt.
• Pri vkladaní duplicity použite pravidlo zo zadania: duplicitné hodnoty patria doľava.
• each() musí navštíviť aj listové uzly a nesmie preskočiť hodnotu aktuálneho uzla.
• Nezoraďujte výsledok pomocou sorted(). Cvičenie overuje, či viete správne prejsť stromom.
• Strom nemusí byť vyvážený. Riešenie musí fungovať aj vtedy, keď všetky hodnoty postupne skončia iba v ľavom alebo iba v pravom podstrome.
• Pri rekurzii nezabudnite skontrolovať None, inak sa pokúsite zavolať metódu na neexistujúcom podstrome.

Zložitosť

Vkladanie navštívi jednu cestu od koreňa po miesto vloženia. Pri približne vyváženom strome má časovú zložitosť O(log n), pri úplne nevyváženom strome však môže byť O(n). Inorder priechod navštívi každý uzol práve raz, preto má časovú zložitosť O(n).

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

• Python Tutorial – triedy
• Definovanie funkcií a rekurzia
• Podmienky if/else
• Konštanta None
• Generátory a yield
• Výraz yield
• Objekty iterátorov

Súvisiace materiály

• Tree (data structure)
• Binary Search Tree – Wikipedia
• Tree Building na Exercisme
• Zipper na Exercisme

Previous Post Next Post