Search
Převzato z https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c
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.
__contains__
True
False
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
# 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
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
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