Table of Contents

8. úkol - Binary Search Tree

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).

Inspirujte se například tímto videem: How to Construct a Binary Search Tree.

Implementace

Můžete použít tuto šablonu: bst.py

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:

bst1 = BinarySearchTree()

print(bst1.search(10))
print(bst1.visitedNodes())
print(bst1.min())
print(bst1.max())

vypíše do konzole:

False
0
None
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())

vypíše do konzole:

True
1
True
2
True
3
False
3
MIN: 1
3
MAX: 8
3

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())

vypíše do konzole:

MIN: 1
1
MAX: 8
7

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. samo-vyvažující se stromy.

Bodování

Za správnou implementaci metod insert(), fromArray(), search(), min(), max() a metody visitedNodes() je možné získat celkem 4 body.