10. Stromové struktury

• 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

• Každý uzel kromě listů má nejvíce dva potomky

• 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í

• 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

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

• 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

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]

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

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