[Java] Algoritmi

[Gin&&Tonic]

Ragazzi oggi ho fatto l'esame di algoritmi, dove oltre alla varia teoria dovevo scrivere anche un metodo sugli alberi binari.
Volevo sapere se secondo voi è giusto:


Si consideri la seguente interfaccia che descrive alberi binari in cui la parte
informativa di ogni nodo sia un intero.
public interface AlberoBinario{
int val();
AlberoBinario sin();
AlberoBinario des();
}
Implementare il metodo
boolean Verifica(AlberoBinario a);
che restituisce :
*true , se almeno 2 foglie dell'albero hanno valore maggiore o uguale a 0
*false altrimenti


io lo ho implementato in questo modo:


public boolean Verifica(AlberoBinario a){
int c=CalcolaFogliePositive( a );
if(c>=2)return true;
return false;
}


public static int CalcolaFogliePositive( AlberoBinario a ){
if(a!=null){
if(a.destro()==null && a.sinistro()==null) {
if(a.val()>0) return 1;
else return 0;
}
else return CalcolaFogliePositive(a.destro()) + CalcolaFogliePositive(a.sinistro());;

}//if iniziale

else return 0;

}



Mi chiedeva anche la complessità temporale e spaziale(nel caso peggiore), ed ho scritto ad entrambe O(n), dove n sono i nodi dell'albero.
Secondo voi è giusto?

[tuccio`]

sì

ps: spaziale direi O(logn) però.. è ricorsiva.. se si intende lo spazio che occupa nello stack è O(logn)

[Gin&&Tonic]

s

ps: spaziale direi O(logn) però.. è ricorsiva.. se si intende lo spazio che occupa nello stack è O(logn)


perché O(logn)?? .. deve comunque aprire tutti i nodi dell'albero per arrivare a "tutte le foglie".. ??

se mi spieghi perchè è O(log n) mi fai un gran favore.....ho la correzione a giorni

[wingman87]

perché O(logn)?? .. deve comunque aprire tutti i nodi dell'albero per arrivare a "tutte le foglie".. ??

se mi spieghi perchè è O(log n) mi fai un gran favore.....ho la correzione a giorni

Perché in memoria al massimo terrai tutti i nodi che si trovano su un percorso dalla radice a una foglia, non tutti i nodi dell'albero. Il numero di questi nodi è pari al massimo all'altezza dell'albero e se questo è bilanciato la sua altezza è nell'ordine di log(n).
Se non è bilanciato, o se comunque non ci sono assunzioni in tal senso, il caso peggiore è che l'altezza dell'albero sia proprio n e quindi la complessità O(n) sarebbe corretta.

[tuccio`]

ah be' sì ovviamente se non è bilanciato è O(n)

[Gin&&Tonic]

raga scusate.. ma per bilanciato cosa intendete:


che sia un albero binario e quindi ogni nodo ha al più due figli?

o che sia un albero "BinarioBilanciato" e l'altezza del sotto alberoSinistro e sotto alberoDestro di ogni nodo differisca al più di "una unità"??

:eek:

[malocchio]

o che sia un albero "BinarioBilanciato" e l'altezza del sotto alberoSinistro e sotto alberoDestro di ogni nodo differisca al più di "una unità"??

;)

[Gin&&Tonic]

malocchio

deve essere BinarioBilanciato perchè sia O(logn)??
o semplicemente binario??

[tuccio`]

deve esserci un limite all'altezza, come nei b-alberi o negli avl, perché una visita DFS ricorsiva può tenere, al più, nello stack tutte le chiamate del cammino dalla radice a una foglia

se è un semplice alberio binario, e non è specificato niente, tutti i nodi interni potrebbero avere tutti e soli figli sinistri, praticamente degenerando in una lista.. l'altezza quindi sarebbe limitata solo da n

[Gin&&Tonic]

Ok nella mia traccia parlava solo di alberi binari( non era specificato il "bilanciamento tra i vari nodi") , perciò la complessità è O(n) .