Esame - #3 - 31 Ott 2021

[rimaout]

Soluzione Prof

[alem1105]

def es(t):
    if t != None:
        if t.left:
            t.key += t.left.key
            es(t.left)
        if t.right:
            t.key += t.right.key
            es(t.right)

[notedo]

def es10(p):
    if p == None:
        return
    if p.left and p.right:
        p.key += p.right.key + p.left.key
    if p.left and not p.right:
        p.key+=p.left.key
    if p.right and not p.left:
        p.key+=p.right.key
    es10(p.left)
    es10(p.right)

[Divine-Sunderer]

def es3(p):
  if p==None:
    return
  if p.left != None:
    p.val += p.left.val
    es3(p.left)
  if p.right != None:
    p.val += p.right.val
    es3(p.right)
  return

[rimaout]

Calcolo costo computazionale

Essendo un albero binario non bilanciato l'equazione di ricorrenza è del tipo: $T(n) = T(k) + T(n-1-k) + \theta(n)$ $T(0) = \theta(1)$

Si risolve con il metodo della sostituzione vedi: #64 o #66