ghostgirl
20-06-2008, 17:17
Ciao a tutti,
ho un esercizio che mi chiede di scrivere un algoritmo per verificare se all'interno di un albero binario un certo valore è ripetuto + volte.
L'algoritmo l'ho scritto in qst modo:
public boolean eRipetuto(AlberoB a,int x){
if(a==null)return false;
if(trovato(x,a.sin()) && trovato(x,a.des()))
return true;
return eRipetuto(a.sin(),x) && eRipetuto(a.des(),x);
}
public boolean trovato(int x,AlberoB a){
if(a==null)return false;
if(a.val()==x)
return true;
return trovato(x,a.sin())&& trovato(x,a.sin());
}
Sperando che la mia soluzione sia giusta, non son certa se è esatto il valore della complessità che ho calcolato.
Per quanto riguarda quella spaziale presumo sia log(n) con n=numero nodi sia nel caso migliore che peggiore.
Per la complessità temporale invece ho pensato che nel caso migliore è costante quindi 1 e in quello peggiore è nlog(n) dato che devo scandire per ogni nodo tutto il sottoalbero di destra e tutto quello di sinistra.
Il mio calcolo è corretto??
Grazie per le risposte
ho un esercizio che mi chiede di scrivere un algoritmo per verificare se all'interno di un albero binario un certo valore è ripetuto + volte.
L'algoritmo l'ho scritto in qst modo:
public boolean eRipetuto(AlberoB a,int x){
if(a==null)return false;
if(trovato(x,a.sin()) && trovato(x,a.des()))
return true;
return eRipetuto(a.sin(),x) && eRipetuto(a.des(),x);
}
public boolean trovato(int x,AlberoB a){
if(a==null)return false;
if(a.val()==x)
return true;
return trovato(x,a.sin())&& trovato(x,a.sin());
}
Sperando che la mia soluzione sia giusta, non son certa se è esatto il valore della complessità che ho calcolato.
Per quanto riguarda quella spaziale presumo sia log(n) con n=numero nodi sia nel caso migliore che peggiore.
Per la complessità temporale invece ho pensato che nel caso migliore è costante quindi 1 e in quello peggiore è nlog(n) dato che devo scandire per ogni nodo tutto il sottoalbero di destra e tutto quello di sinistra.
Il mio calcolo è corretto??
Grazie per le risposte