- Codice:
void PreOrder(Node* tree) {
if (tree) {
<esamina il nodo>
PreOrder(tree->left);
PreOrder(tree->right);
}
}
$a$ : tempo per il test: if (tree)
$b$ : tempo per l'esame del nodo
Poi si dice che vale $T(n)=bn+a(n+1)$ e qua arrivano i dubbi
Mi è chiaro che il numero dei nodi essendo $n$, moltiplicando $n$ per il tempo di visita di un nodo $b$ otteniamo $bn$ ma perchè abbiamo $a(n+1)$ invece ?
P.e. se avessi un solo nodo il test verrebbe fatto 3 volte: per il nodo in questione e per il sottoalbero destro e sinistro (anche se sono nulli i test vengono effettuati) per un totale di $3a$. Mentre se seguissi la formula otterrei $2a$.
Come si spiega ?