volevamo: Formula Ricorrenza di In-Order metodo di uscita albero binario

Question

io sono un po 'di un inceppamento alla ricerca della formula ripetersi di questo metodo java

void printInorder(Node<T> v) { 
    if(v != null) { 
     printInorder(v.getLeft()); 
     System.out.println(v.getData()); 
     printInorder(v.getRight()); 
    } 
} 

Alcuni criteri:

• sua un albero binario completo (ogni nodo interno ha 2 figli, ogni foglia ha la stessa profondità)
• l'albero ha n nodi e una complessità di O (n)

01.235.164,106 mila

Devo trovare la formula di ricorrenza in relazione allo depth h dell'albero con n knots e come ulteriore vantaggio, ho bisogno di estrapolare la formula esplicita che porta a O (n) da quello.

Ora, questo è quello che ho ottenuto:

d = depth of the tree 
c = constant runtime for execution of the method itself 
d = 1: T(n) = c 
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c 

ho usato l'esempio d = 3 per chiarire le cose per me stesso, sto avendo difficoltà rompendo questo giù ulteriormente. La mia ipotesi è corretta?

---

Edit: tentativo successivo le cose

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number 
d = 1: T(d) = 1 
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1))) 

1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1) 
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2))) 
3: T(h) = n + n + ... + n 
4: T(h) = (h-1)n 
5: T(h) = O(n) 

Perché ogni livello di profondità dell'albero contiene esattamente 2 nodi^(h-1), il fattore h in linea 4 può essere ignorato perché n è più rilevante per il risultato finale.

Answer 1

T (n) = T (n/2) + T (n/2) + 1

• Livello 0 ha 1 operazione.

• Il livello 1 ha 2 operazioni.

• Il livello 2 ha 4 operazioni.

• Il livello k ha 2^k operazioni.

• La profondità dell'albero è lgn.

1 + 2 + ... + 2^lgn =
2^0 + 2^1 + 2^2 + ... + 2^lgn =
(2^(lgn + 1) -1)/(2-1) = 2 * 2^lgn =
2n.

Answer 2

Ecco un approccio alternativo, utilizzando la regola levigatezza (Levitin, The Design & analisi degli algoritmi, 2nd Ed., 481-82), che permette una relazione di ricorrenza come questo per essere rappresentato come esponente invece.

Entrambi gli approcci - avanti o sostituzione all'indietro - è appropriato per questo problema. Trovo la sostituzione all'indietro in molti casi per essere più facile da digerire.