search

CS-Swap / Algoritmi-1

Repository destinato alla condivisione di materiale e soluzioni per gli esercizi ed esami assegnati dal Prof. Monti Angelo in preparazione all'esame di Algoritmi 1
8 stars 1 forks source link

Esame - #3 - 8 Set 2021 #78

Open rimaout opened 1 month ago

rimaout commented 1 month ago
image image
Soluzione Prof image
alem1105 commented 1 month ago 
def es(t):
    if t == None:
        return
    if t.left and t.right:
        t.left.key, t.right.key = t.right.key, t.left.key
    es(t.left)
    es(t.right)
rimaout commented 1 month ago

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