====== 10. Stromové struktury ======
===== Strom =====
* Rozšíření spojového seznamu: Každý prvek může mít více //potomků//
* Ustálená terminologie:
* **Kořen (//root node//):** Základní prvek
* **Uzel (//branch node//):** Má aspoň jednoho předka a jednoho potomka
* **List (//leaf node//):** Mají předka, ale ne potomka
Převzato z https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c
==== Binární strom ====
* Každý uzel kromě listů má nejvíce dva potomky
==== Binární vyhledávací strom (binary search tree, BST) ====
* hodnoty v levém podstromě jsou vždy menší než hodnota uzlu a hodnoty v pravém podstromě
* hodnoty v pravém podstromě jsou vždy větší než hodnota uzlu
* BST umožňuje efektivní vyhledávání
=== Algoritmus vyhledávání v BST ===
* Začni v kořeni
* Porovnej vyhledávanou hodnotu s hodnotou v uzlu, podle výsledku porovnání pokračuj dále
* //pokud se rovnají, pak ohlaš nalezení hodnoty//
* //pokud je vyhledávaná hodnota menší než hodnota uzlu, pokračuj uzlem v levém podstromě//
* pokud je vyhledávaná hodnota větší než hodnota v uzlu, pokračuj dalším uzlem v pravém podstromě
Převzato z https://medium.com/@kenneth.jiang/binary-search-trees-c62d3574884f
# inspirovano: https://runestone.academy/runestone/books/published/pythonds/Trees/SearchTreeImplementation.html
# trida pro strom
class BinarySearchTree:
def __init__(self):
''' konstruktor '''
self.root = None
self.size = 0
def length(self):
''' vrati pocet uzlu ve strome'''
return self.size
def put(self,value):
''' metoda pro vlozeni prvku do stromu '''
if self.root: # pokud jiz je koren
self._put(value,self.root)
else: # neni koren, vytvor ho
self.root = TreeNode(value)
self.size = self.size + 1
def _put(self,value,currentNode):
'''rekurzivni metoda pro vlozeni prvku do stromu'''
if value < currentNode.value: # value je mensi nez hodnota daneho uzlu
if currentNode.left != None: # jestli je levy uzel, volej _put pro nej
self._put(value,currentNode.left)
else:
currentNode.left = TreeNode(value)
elif value > currentNode.value: # value je vetsi nez hodnota daneho uzlu
if currentNode.right != None: # jestli je pravy uzel, volej _put pro nej
self._put(value,currentNode.right)
else:
currentNode.right = TreeNode(value)
else: # pokud je value rovna hodnote daneho uzlu, nedelej nic
pass
def print_tree(self):
'''metoda pro tisk stromu'''
level = 1 # uroven
if self.root:
self._print_tree(self.root,level)
{{ :courses:bab37zpr:tutorials:cv12_aplikace_scikit_learn_b221.zip | cv12}}
def _print_tree(self,uzel,level,branch=''):
'''rekurzivni privatni metoda pro tisk stromu'''
if uzel != None:
if uzel.value:
print(" "*(4*level)+branch+str(uzel.value))
if uzel.left:
self._print_tree(uzel.left,level=level+1,branch='L:')
if uzel.right:
self._print_tree(uzel.right,level=level+1,branch='R:')
def __contains__(self, hodnota):
pass # misto pass doplne funkci
# trida pro uzel
class TreeNode:
def __init__(self,value,left=None,right=None):
"konstruktor"
self.value = value
self.left = left
self.right = right
===== Úloha 1 - __contains__ =====
Napište metodu ''%%__contains__%%'' (případně doplňte pomocné metody), která vrátí ''%%True%%'' v případě, že strom obsahuje danou hodnotu, jinak ''%%False%%''. Implementací metody bude možno používat Pythonovský operátor ''%%in%%''.
pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]
bst = BinarySearchTree()
for hodnota in pole:
bst.put(hodnota)
100 in bst
==== Binární min halda (min-heap) ====
* Hodnota každého uzlu je rovna nebo menší než hodnoty potomků -- kořen obsahuje nejmenší hodnotu (min-halda)
* Lze implementovat také naopak (max-halda)
* Níže je provedena jednoduchá implementace pomocí pole
* **Vyjmutí nejmenšího prvku z haldy**: Vyjmeme kořen a poté musíme haldu přeskupit a určit nový kořen
* na místo vyjmutého prvku vložíme prvek nejvíce v pravo (největší)
* poté postupně od kořene procházíme haldu (**bubble-down** postup)
* porovnáme hodnotu uzle a jeho potomků, pokud je menší nebo roven potomkům, pak algoritmus skončí
* jinak vybereme menšího potomka daného uzlu a prohodíme je spolu a pokračujeme od tohoto potomka
* konec nastane pokud dojdeme k listu (uzlu bez potomka)
* **Vložení prvku** Pokud máme existující bínární haldu, vložení prvku se provede takto:
* vložíme prvek na poslední nejpravější místo v poslední úrovni
* poté postupně od tohoto prvku procházíme haldu směrem nahoru (**bottom-up** postup)
* porovnáme hodnotu vloženého prvku s jeho rodičem, pokud je větší, pak skončíme
* pokud ne, pak je prohodíme a postup opakujeme od změněného uzlu rodiče
# Implementace haldy
#
# http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html
# Jan Kybic, 2016
class MinHeap:
""" binarni halda __init__ konstruktor """
def __init__(self):
self.heap = [] # indexujeme od nuly
def bubble_up(self,i):
""" probubla prvek i nahoru, zajisti splneni podminek haldy """
while i>0:
j=(i-1)//2 # index rodice
if self.heap[i] >= self.heap[j]:
break
self.heap[j],self.heap[i]=self.heap[i],self.heap[j]
i = j
def insert(self,k):
""" vloz prvek do haldy """
self.heap+=[k]
self.bubble_up(len(self.heap)-1)
def peek(self):
""" vrati nejmensi prvek """
return self.heap[0]
def size(self):
""" vrati pocet prvku v halde """
return len(self.heap)
def is_empty(self):
""" je halda prazdna? """
return self.size()==0
def bubble_down(self,i):
""" probublej prvek dolu """
n=self.size()
while 2*i+1 < n:
j=2*i+1 # zjisti index mensiho syna
if j+1 < n and self.heap[j] > self.heap[j+1]:
j+=1
if self.heap[i]>self.heap[j]:
self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
i=j
def pop(self):
""" odebere nejmensi prvek a uprav haldu """
element=self.heap[0]
self.heap[0]=self.heap[-1]
self.heap.pop() # smaz posledni prvek
self.bubble_down(0)
return element
def delete(self, pozice):
pass # misto pass doplne funkci
===== Úloha 2 - implementace metody delete =====
Implementujte metodu delete do třídy MinHeap (haldy). Vstupním argumentem metody delete je index daného prvku.
pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]
min_halda = MinHeap()
for hodnota in pole:
min_halda.insert(hodnota)
print(min_halda.heap)
min_halda.pop()
print(min_halda.heap)
min_halda.delete(10)
print(min_halda.heap)
# výstup be měl vypadat následnovně:
#[-12, -11, -12, 9, 1, 10, -7, 11, 31, 42, 31, 80, 25, 7, 6, 21, 14]
#[-12, -11, -7, 9, 1, 10, 6, 11, 31, 42, 31, 80, 25, 7, 14, 21]
#[-12, -11, -7, 9, 1, 10, 6, 11, 31, 42, 21, 80, 25, 7, 14]
===== Úloha 3 - Konstrukce Huffmanova stromu =====
Huffmanův strom umožní stanovit kód podle četnosti výskytů jednotlivých symbolů ve snaze snížit bitový tok https://en.wikipedia.org/wiki/Huffman_coding
Princip je takový, že pokud víme četnost jednotlivých symbolů ve zprávě, např.
''%%a 5%%''
''%%b 9%%''
''%%c 12%%''
''%%d 13%%''
''%%e 16%%''
''%%f 45%%''
Můžeme sestavit strom pomocí kterého je možné stanovit binární kód pro jednotlivé symboly vzhledem k jejich četnosti
Převzato z https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/
Kód pro jednotlivé symboly pak je:
''%%f 0%%''
''%%c 100%%''
''%%d 101%%''
''%%a 1100%%''
''%%b 1101%%''
''%%e 111%%''
Pro řešení použijeme minimální haldu, kterou jsme si představili výše a třídu pro uzel výsledného Huffmanova stromu
# trida ktera predstavuje uzel Huffmanova stromu
class HTNode:
def __init__(self,freq,symbol,left=None,right=None):
"konstruktor"
self.left = left # reference na levy uzel
self.right = right # reference na pravy uzel
self.freq = freq # cetnost vyskytu symbolu
self.symbol = symbol # symbol (a,b,c...)
self.huff = '' # 0 - left, 1 - right (bude pouzito pro stanoveni kodu)
def __gt__(self, dalsi): # specialni funkce pro operator >= na objekty
return self.freq > dalsi.freq
def __ge__(self, dalsi): # specialni funkce pro operator > na objekty
return self.freq >= dalsi.freq
znaky = 'abcdef' # symboly
freq = [5,9,12,13,16,45] # cetnosti
freqznak = list(zip(freq,znaky)) # vytvorime pole n-tic (symbol, cetnost)
print(freqznak)
# zde implementujte reseni
===== Úlohy na doma =====
Projděte si opět všechny implementace stromů ze cvičení a také implementace z přednášky, abyste jim dobře porozumněli