from tree import *
from IPython.display import display
import random

#  Struktura pro reprezentaci uzlu stromu Tree.
#  'key' je klic uzlu
#  'S' je hodnota S daneho uzlu.
#  'b' urcuje barvu uzlu
#
#  'left' je levy syn, tedy atribut typu Node, pokud syn existuje, jinak None
#  'right' analogicky jako left
class Node:
    def __init__(self):
        self.key = None
        self.S = None
        self.b = None
        self.left = None
        self.right = None

Obecné poznámky

• Třída Tree obsahuje parametr root - kořen stromu.
• Nastovování hodnot do node.S či node.b je často pouze pro účely vizualizace toho, co se ze kterého uzlu vrací a v klasických programech bychom tyto hodnoty nenastavovali, jen je propagovali nahoru pomocí return.
• Sekvence příkazů ret = f(tree); display(tree); return ret ve funkce f, která má vracet něco jiného než strom, je použita rovněž pro účely vizualizace, typicky bychom je nahradili příkazem return f(tree).

Vytvoření ukázkových stromů

small_seq = [3,5,9,None,6,None,None,None,None,12]
small = makeHeap(small_seq)
small

big_seq = random.sample(range(100), 30)
big_seq[4] = None
big_seq[6] = None
big_seq[16] = None
big_seq[23] = None
big_seq[24] = None

big = makeHeap(big_seq);
big

Jednoduchá rekurze bez předávání informací

• každému uzlu se od atributu S přiřadí 0.
• hlavní práci odvádí pomocná funkce fill_zeros_n, která funguje nad jednotlivými uzly

def fill_zeros_n(node):
    if node is None:
        return
    node.S = 0
    fill_zeros_n(node.left)
    fill_zeros_n(node.right)

def fill_zeros(tree):
    fill_zeros_n(tree.root)
    return tree

fill_zeros(small)

Upravit tak, abychom mohli ulozit libovolnou hodnotu

def fill_n(node, value):
    if node is None:
        return
    node.S = value
    fill_n(node.left, value)
    fill_n(node.right, value)

def fill(tree, value):
    fill_n(tree.root, value)
    return tree

fill(small, 3)

Informace zhora dolů

• předává se pomocí parametrů pomocné funkce

def fill_depth_n(node, value):
    if node is None:
        return
    node.S = value
    fill_depth_n(node.left, value + 1)
    fill_depth_n(node.right, value + 1)
    
    
def fill_depth(tree):
    fill_depth_n(tree.root, 0)
    return tree

fill_depth(big)

Rekurzivní volání pro levého a pravého potomka mohou dostat jiné parametry

• Zelená barva uzlu znamená, že má nastaven atribut b na True, červená analogicky pro False, modrá odpovídá node.b == None.
• Zelené jsou ty uzly, jež jsou levým následníkem svého otce.

def fill_direction_n(node, is_left):
    if node is None:
        return
    node.b = is_left
    fill_direction_n(node.left, True)
    fill_direction_n(node.right, False)
    
    
def fill_direction(tree):
    fill_direction_n(tree.root, None)
    return tree

fill_direction(makeHeap(big_seq))

Propagace informací zdola nahoru

• Předává se návratovou hodnotou.
• Pokud hodnotu nijak nevyužijeme, informace je ztracena.

def tree_height_n(node):
    if node is None:
        return -1
    l = tree_height_n(node.left)
    r = tree_height_n(node.right)
    node.S = max(l,r) + 1
    return node.S

def tree_height(tree):
    ret = tree_height_n(tree.root)
    display(tree)
    return ret

tree_height(makeHeap(small_seq))

3

Kombinace - nejprve dolů, potom zpět nahoru

Nejprve špatný pokus

Informace o délce větve se správně spočítá a vrací, nicméně není zachycena v rodiči.

def tree_height_bad_n(node, value):
    if node is None:
        return value-1
    tree_height_bad_n(node.left, value + 1)
    tree_height_bad_n(node.right, value + 1)
    node.S = value
    return node.S
    
    
def tree_height_bad(tree):
    ret = tree_height_bad_n(tree.root, 0)
    display(tree)
    return ret

tree_height_bad(small)

0

Korektní řešení, které hodnoty vrácené z potomků zachytí a zpracuje

def tree_height2_n(node, value):
    if node is None:
        return value-1
    l = tree_height2_n(node.left, value + 1)
    r = tree_height2_n(node.right, value + 1)
    node.S = max(l, r)
    return node.S
    
    
def tree_height2(tree):
    ret = tree_height2_n(tree.root, 0)
    display(tree)
    return ret

tree_height2(small)

3

def has_all_zeros_n(node):
    if node is None:
        return True
    l = has_all_zeros_n(node.left)
    r = has_all_zeros_n(node.right)
    this = node.S == 0
    node.b = this and l and r
    return node.b

def has_all_zeros(tree):
    ret = has_all_zeros_n(tree.root)
    display(tree)
    return ret

big = makeHeap(big_seq)
fill_zeros(big)
has_all_zeros(big)

True

big.root.right.left.right.S = 5
big.root.right.left.left.S = 3
has_all_zeros(big)

False

Informace z potomků je kombinována s aktuálním uzlem

def has_zero_branch_n(node):
    if node is None:
        return True
    l = has_zero_branch_n(node.left)
    r = has_zero_branch_n(node.right)
    this = node.S == 0
    node.b = this and (l or r)
    return node.b

def has_zero_branch(tree):
    ret = has_zero_branch_n(tree.root)
    display(tree)
    return ret

has_zero_branch(big)

True

big.root.left.S = 4
big.root.right.S = 3
has_zero_branch(big)

False

big = makeHeap(big_seq)
fill_depth(big)

def has_even_n(node, value):
    if node is None:
        return True
    l = has_even_n(node.left, value)
    r = has_even_n(node.right, value)
    childern_even = l == r # sude + sude = sude, liche + liche = sude
    if node.S == value:
        node.b = not childern_even
    else:
        node.b = childern_even
    return node.b

def has_even(tree, value):
    ret = has_even_n(tree.root, value)
    display(tree)
    return ret

big = makeHeap(big_seq)
fill_depth(big)
has_even(big, 4)

False

big = makeHeap(big_seq)
big

Inorder

Výsledkem je strom, jehož klíče jsou očíslovány od 1 do $|V|$ v pořadím, jakým prochází inorder průchod. V node.S je uložena hodnota, kterou prve vrací rodiči. Její význam je číslo o jedna větší než poslední, které jsem použil ve svém podstromě. Podstrom každého uzlu je očíslován čísly od vstupní hodnoty value do návratové hodnoty daného rekurzivního volání.

def fix_keys_n(node, value):
    if node is None:
        return value
    l = fix_keys_n(node.left, value)
    node.key = l
    r = fix_keys_n(node.right, l + 1)
    node.S = r
    return node.S

def fix_keys(tree):
    fix_keys_n(tree.root, 1)
    return tree

fix_keys(makeHeap(big_seq))

Kopírujeme uzly (a převracíme pořadí)

def reverse_n(node):
    if node is None:
        return None
    new = Node()
    new.key = node.key
    new.left = reverse_n(node.right)
    new.right = reverse_n(node.left)
    return new

def reverse(tree):
    new_tree = Tree()
    new_tree.root = reverse_n(tree.root)
    return new_tree

display(big, reverse(big))

Hledání prvků ve stromech

Všechny kořeny podstromů, které obsahují nějaký uzel s node.S == value jsou zelené. Funkce vrací True pro stromy, který nějaký takový prvek obsahují. Projde vždy všechny uzly.

def find_all_n(node, value):
    if node is None:
        return False
    here = node.S == value
    l = find_all_n(node.left, value)
    r = find_all_n(node.right, value)
    node.b = here or l or r
    return node.b

def find_all(tree, value):
    ret = find_all_n(tree.root, value)
    display(tree)
    return ret 

find_all(fill_depth(big), 2)

True

Hledá první uzel se zadaným klíčem. Vrací ukazatel na něj. Červeně jsou uzly, které algoritmus neúspěšně prošel, zelený je nalezený uzel a konečně modré jsou uzly, kam se výpočet vůbec nedostal. Všechny uzly projde jen v případě, že se hledaný klíč ve stromě neneachází.

Po nalezení prvku je potřeba tuto informaci propagovat zpět nahoru.

def find_first_n(node, value):
    if node is None:
        return None
    if node.key == value:
        node.b = True
        return node
    node.b = False
    l = find_first_n(node.left, value)
    if l is not None:
        return l
    r = find_first_n(node.right, value)
    return r

def find_first(tree, value):
    ret = find_first_n(tree.root, value)
    display(tree)
    return ret

find_first(makeHeap(big_seq), big_seq[8])

<tree.Node at 0x7f1af422c898>

find_first(makeHeap(big_seq), 26)