Aiuto analisi complessità sugli alberi

[mutex01]

Buongiorno..
avrei bisogno di un aiuto sull'analisi della complessità di alcuni metodi:

1)// ERIPETUTO, restituisce true se e solo se vi è almeno un nodo n
// nell'albero a
// in cui x appare sia nel sottoalbero destro che nel sottoalbero sinistro

public static boolean eRipetuto(AlberoB<Integer> a, int x) {
if (a.getSin() == null || a.getDes() == null)
return false;

if (presente(a.getSin(), x) && presente(a.getDes(), x))
return true;
return eRipetuto(a.getSin(), x) || eRipetuto(a.getDes(), x);

}

public static boolean presente(AlberoB<Integer> a, int x) {
if (a == null)
return false;
if (a.getVal() == x)
return true;
return presente(a.getSin(), x) || presente(a.getDes(), x);
}

devo fare l'analisi della complessità nel caso migliore e peggiore,temporale e spaziale.

Il mio problema è individuare quale sia il caso migliore..perchè per il caso peggiore ho ragionato ponendo che l'elemento da trovare sia nelle foglie,quindi va controllato tutto l'albero, quindi complessità spaziale: O(n) e temporale(n^2) è corretto???


2)// UGUALI,restituisce true se e solo se gli alberi a e b sono identici,ossia
// sono uno la copia dell'altro//

public static boolean Uguali(AlberoB<Integer> a, AlberoB<Integer> b) {
if ((a == null && b != null) || (a != null && b == null))
return false;
if (a == null && b == null)
return true;
if (a.getVal() != b.getVal())
return false;
return Uguali(a.getSin(), b.getSin()) && Uguali(a.getDes(), b.getDes());
}

Caso migliore: l'albero a e l'albero b presentano valori diversi già nella radice.
TEMPORALE: O(1)
SPAZIALE: O(1)

caso peggiore: gli alberi a e b sono uguali
TEMPORALE: O(n)
SPAZIALE: O(n)

è corretto?


3)// VERIFICAVALORE PARI, restituisce true se e solo se l'albero a contiene un
// intero x
// di valore pari e compreso nell'intervallo [intmin,intmax](si assuma
// intmin<intmax)

public static boolean VerificaValorePari(AlberoB<Integer> a, int valmin,
int valmax) {
if (a == null)
return false;
if (a.getVal() % 2 == 0 && a.getVal() < valmax && a.getVal() > valmin)
return true;
return VerificaValorePari(a.getSin(), valmin, valmax)
|| VerificaValorePari(a.getDes(), valmin, valmax);
}

caso migliore: la radice contiene un valore pari e compreso nell'intervallo
TEMPORALE(1)
SPAZIALE: O(1)

caso peggiore: l'albero non ha elementi pari compresi nelll'intervallo
TEMPORALE: O(n)
SPAZIALE: O(n)


4)// ALTEZZA, calcola l'altezza dell'albero a

public static int Altezza(AlberoB<Integer> a) {
if (a == null)
return 0;
int hs = Altezza(a.getSin());
int hd = Altezza(a.getDes());
if (hs > hd)
return hs + 1;
return hd + 1;
}


caso migliore ????
caso peggiore: l'albero è completo
TEMPORALE: O(nlog2n)
SPAZIALE: O(log2n)


5)SIMMETRICI,restituisce true se e solo se l'albero a e
// l'albero b sono simmetrici

public static boolean Simmetrici(AlberoB<Integer> a, AlberoB<Integer> b) {
if (a == null && b == null)
return true;
if ((a != null && b == null) || (a == null && b != null))
return false;
if (a.getVal() != b.getVal())
return false;
return Simmetrici(a.getSin(), b.getDes())
|| Simmetrici(a.getDes(), b.getSin());


caso migliore ????
caso peggiore ????

grazie a tutti per l'aiuto..