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 (každá hodnota je zde zastoupena tedy maximálně jednou).
Inspirujte se například tímto videem: How to Construct a Binary Search Tree.
Vytvořte soubor bst.py (resp. použijte šablonu bst.py) 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.
Třída BinarySearchTree pak implementuje výše zmíněné metody: insert, fromArray, search, min, max a visitedNodes.
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
False
0
None
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
True
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ů. 5 bodů je za správnou implementaci metod insert, fromArray, search, min, max a metody visitedNodes.