Matematicamente.it

Data la seguente relazione di ricorrenza di un albero binario prendendo in esame la visita PreOrder in base al numero dei nodi:

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 ?

Anche a me sembra un errore. Il numero di test è uguale al numero di nodi più il numero di figli nulli (che credo sia tuttavia variabile a seconda della forma dell'albero).

apatriarca ha scritto:Anche a me sembra un errore. Il numero di test è uguale al numero di nodi più il numero di figli nulli (che credo sia tuttavia variabile a seconda della forma dell'albero).

giusto per completezza...

Il numero di figli nulli non dipende dalla forma dell'albero. Infatti ci sono \(2n\) "archi" e \(n-1\) nodi hanno un padre (la radice non ha un padre). Quindi \(n+1\) archi sono senza un destinatario.