Search
Cílem úlohy je implementovat datovou strukturu nazývanou 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 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).
insert()
fromArray()
search()
True
False
min()
max()
None
visitedNodes()
Inspirujte se například tímto videem: How to Construct a Binary Search Tree.
Vytvořte soubor bst.py (resp. použijte šablonu) a v něm následující dvě třídy:
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.
Node
self.value
self.left
self.right
Třída BinarySearchTree pak implementuje výše zmíněné metody: insert(), fromArray(), search(), min(), max() a visitedNodes().
BinarySearchTree
Prázdný strom:
bst1 = BinarySearchTree() print(bst1.search(10)) print(bst1.visitedNodes()) print(bst1.min()) print(bst1.max())
bst1 = BinarySearchTree()
print(bst1.search(10))
print(bst1.visitedNodes())
print(bst1.min())
print(bst1.max())
vypíše do konzole:
False 0 None None
0
Strom odpovídající obrázku nahoře:
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())
bst2 = BinarySearchTree()
bst2.fromArray([5, 3, 1, 4, 7, 6, 8])
print(bst2.search(5))
print(bst2.visitedNodes())
print(bst2.search(7))
print(bst2.search(6))
print(bst2.search(10))
print(“MIN: ” + str(bst2.min()))
print(“MAX: ” + str(bst2.max()))
True 1 True 2 True 3 False 3 MIN: 1 3 MAX: 8 3
1
2
3
MIN: 1
MAX: 8
Nevyvážený strom:
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())
bst3 = BinarySearchTree()
bst3.fromArray([1, 3, 4, 5, 6, 7, 8])
print(“MIN: ” + str(bst3.min()))
print(bst3.visitedNodes())
print(“MAX: ” + str(bst3.max()))
MIN: 1 1 MAX: 8 7
7
Za úlohu je možné získat 5 bodů za správnou implementaci metod insert(), fromArray(), search(), min(), max() a metody visitedNodes().