[Algoritmi] ricorrenza negli alberi binari

Messaggioda zio_mangrovia » 02/12/2019, 21:54

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 ?
zio_mangrovia
Senior Member
Senior Member
 
Messaggio: 991 di 1001
Iscritto il: 13/06/2016, 17:42

Re: [Algoritmi] ricorrenza negli alberi binari

Messaggioda apatriarca » 03/12/2019, 23:37

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
Moderatore
Moderatore
 
Messaggio: 5329 di 5373
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: [Algoritmi] ricorrenza negli alberi binari

Messaggioda zio_mangrovia » 04/12/2019, 05:24

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...

Immagine
zio_mangrovia
Senior Member
Senior Member
 
Messaggio: 992 di 1001
Iscritto il: 13/06/2016, 17:42

Re: [Algoritmi] ricorrenza negli alberi binari

Messaggioda vict85 » 16/12/2019, 15:37

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.
vict85
Moderatore
Moderatore
 
Messaggio: 10029 di 10071
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 8 ospiti