====== 8. úkol - Binary Search Tree ======

{{ :courses:b6b36zal:internal:binarytree.png?300|}}

Cílem úlohy je implementovat datovou strukturu nazývanou [[https://en.wikipedia.org/wiki/Binary_search_tree |binární vyhledávací strom]]. Na rozdíl od (lineárního) spojového seznamu, v této struktuře může mít každý uzel (node) až dva následovníky: levý a pravý uzel (viz obrázek napravo). Pravidlo pro vytváření nových uzlů je takové, že hodnota levého následovníka je vždy menší než hodnota aktuálního uzlu a naopak hodnota pravého následovníka je vždy větší než hodnota v aktuálním uzlu. Pokud daný uzel nemá nesledovníka/y tak ukazuje levá/pravá/obě reference na [[https://docs.python.org/3.5/library/constants.html#None|None]]. 

Náš binární vyhledávací strom bude umět tyto operace: vkládat nové uzly jednotlivě (metoda ''insert()''), ale i z pole (metoda ''fromArray()''), zjišťovat zdali daný prvek je ve stromu (metoda ''search()'' vracející ''True''/''False''), najít minimální a maximální hodnotu ve stromu (metoda ''min()'' a ''max()''). V případě prázdného stromu metody ''min()'' a ''max()'' vrací ''None''. Na závěr zde bude ještě metoda ''visitedNodes()'', která vrátí počet navštívených uzlů při posledním volání jedné z metod: ''search()'', ''min()'' nebo ''max()''. Tato hodnota také odpovídá hloubce, ve které se hledaný uzel nachází, pokud se ve stromu vyskytuje (první uzel má hloubku rovnou jedné). Strom obsahuje pouze unikátní hodnoty (tedy každá hodnota je zde zastoupena maximálně jednou).

Inspirujte se například tímto videem: [[https://www.youtube.com/watch?v=FvdPo8PBQtc|How to Construct a Binary Search Tree]].

==== Implementace ====

<note tip>Můžete použít tuto šablonu: {{:courses:b6b36zal:zadani:bst.py|}}</note>

Vytvořte soubor bst.py (resp. použijte šablonu) a v něm následující dvě třídy:

----

=== Node ===

Třída ''Node'' reprezentuje jeden uzel ve stromu. Nese tudíž svou hodnotu (int) v proměnné ''self.value'' a reference ''self.left'', ''self.right'' na své potencionální následovníky. Výchozí hodnota pro levého a pravého následovníka bude ''None''.

----

=== BinarySearchTree ===

Třída ''BinarySearchTree'' pak implementuje výše zmíněné metody: ''insert()'', ''fromArray()'', ''search()'', ''min()'', ''max()'' a ''visitedNodes()''.


==== Příklady použití ====
Prázdný strom:
<WRAP center round box 60%>
''bst1 = BinarySearchTree()''\\
\\
''print(bst1.search(10))''\\
''print(bst1.visitedNodes())''\\
''print(bst1.min())''\\
''print(bst1.max())''\\

**vypíše do konzole**:

''False''\\
''0''\\
''None''\\
''None''\\
</WRAP>

Strom odpovídající obrázku nahoře:
<WRAP center round box 60%>
''bst2 = BinarySearchTree()''\\
''bst2.fromArray([5, 3, 1, 4, 7, 6, 8])''\\
\\
''print(bst2.search(5))''\\
''print(bst2.visitedNodes())''\\
''print(bst2.search(7))''\\
''print(bst2.visitedNodes())''\\
''print(bst2.search(6))''\\
''print(bst2.visitedNodes())''\\
''print(bst2.search(10))''\\
''print(bst2.visitedNodes())''\\
''print("MIN: " + str(bst2.min()))''\\
''print(bst2.visitedNodes())''\\
''print("MAX: " + str(bst2.max()))''\\
''print(bst2.visitedNodes())''

**vypíše do konzole**:

''True''\\
''1''\\
''True''\\
''2''\\
''True''\\
''3''\\
''False''\\
''3''\\
''MIN: 1''\\
''3''\\
''MAX: 8''\\
''3''\\
</WRAP>

Nevyvážený strom:
<WRAP center round box 60%>
''bst3 = BinarySearchTree()''\\
''bst3.fromArray([1, 3, 4, 5, 6, 7, 8])''\\
\\
''print("MIN: " + str(bst3.min()))''\\
''print(bst3.visitedNodes())''\\
''print("MAX: " + str(bst3.max()))''\\
''print(bst3.visitedNodes())''

**vypíše do konzole**:

''MIN: 1''\\
''1''\\
''MAX: 8''\\
''7''
</WRAP>

<note tip>
Zamyslete se nad rozdílem mezi druhým a třetím příkladem použití. Oba stromy mají shodné prvky, ale pořadí jejich vkládání do stromu hraje zásadní roli. Při hledání maxima je v případě nevyváženého stromu počet navštívených uzlů podstatně vyšší. Nakreslete si tento strom. Čemu odpovídá? Tento problém nevyvážení řeší tzv. [[https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree|samo-vyvažující se stromy]].
</note>


==== Bodování ====
Za úlohu je možné získat **5 bodů** za správnou implementaci metod ''insert()'', ''fromArray()'', ''search()'', ''min()'', ''max()'' a metody ''visitedNodes()''.