[JAVA] Albero (quasi) perfettamente bilanciato

[chia19]

Ciao a tutti. Devo creare un metodo che prende un SimpBtree(albero binario) e restituisce true se e solo se l’albero è quasi perfettamente bilanciato (cioè le foglie si trovano tutte ad altezza h o h-1).
Di idee ne ho tante ma non riesco a implementarlo. Ho creato un metodo che mi restituisce true se e solo se l’albero è Perfettamente Bilanciato( cioè le foglie si trovano tutte ad altezza h), ma non riesco a modificarlo in modo che mi restituisca true se l'albero è QUASI perfettamente bilanciato.
Questa era la mia idea: In caso di albero non Perfettamente Bilanciato andavo a controllare se l'albero con altezza h-1 era perfettamente bilanciato. Se l'albero a altezza h-1 è perfettamente bilanciato allora tutto l'albero sarà QUASI perfettamente bilanciato.
Questo è il codice di perfettamente bilanciato:

	public boolean bilanciato(){
		return this.bilanciato1()>=0;
	}
	public int bilanciato1(){
		if(this==EMPTYBTREE)return -1;
		else // è una foglia
			if(left==EMPTYBTREE&&right==EMPTYBTREE)return 0;
		    else // solo uno dei 2 sottoalberi è vuoto
		    	if(left!=EMPTYBTREE&&right==EMPTYBTREE||left==EMPTYBTREE&&right!=EMPTYBTREE)
		    	 	return -1;
		        else//entrambi i sottoalberi sono non vuoti
		          {int h1=left.bilanciato1();
		           if(h1<0)return -1;
		           int h2=right.bilanciato1();
		           if(h2<0)return -1;
		           return (h1==h2)?h1+1:-1;
		          }
	}

Uso una classe di albero binario semplificato:

public class SimpBtree<E>
 {
	private SimpBtree<E> left,right;
	private E root;
	public static final SimpBtree EMPTYBTREE=new SimpBtree();
}

Avete qualche suggerimento? grazieeee!

[alka]

Usa il tag [CODE] per formattare il codice: ho corretto io il post.

[serioja90]

Secondo me, la soluzione più semplice è quella di creare una funzione che calcola l'altezza di un albero binario e applicarla ricorsivamente sul sotto albero sinistro e quello destro, dopodiché verificare se la differenza delle altezze è minore di 1:

public int altezza(){
    if (this==EMPTYTREE){
        return 0;
    }else{
        return 1+Math.max(left.altezza(),right.altezza());
    }
}

public boolean bilanciato(){
    if (this==EMPTYTREE){
        return true;
    }else{
        return Math.abs(left.altezza()-right.altezza())<=1 && left.bilanciato() && right.bilanciato();
    }
}

Il codice non è molto efficace se viene usato per alberi molto grandi, visto che usa la ricorsione in entrambe le funzioni. Comunque spero di esserti stato d'aiuto.

[serioja90]

In alternativa, sempre sfruttando la funzione per il calcolo dell'altezza del albero, potresti modificare la seconda parte del codice in questo modo:

public boolean bilanciato(){
    return aux(this.altezza());
}

public boolean aux(int n){
    if (this==EMPTYTREE){
        return n<=1;
    }else{
        return left.aux(n-1) && right.aux(n-1);
    }
}

In pratica l'altezza del albero viene calcolata soltanto una volta e poi, con la seconda funzione viene verificato se tutte le foglie del albero si trovano all'altezza n, oppure n-1.

[chia19]

grazie tante per l'aiutooooo!!!

[serioja90]

Non c'è di che

[ReDevil88]

Salve,ho visto il primo metodo postato da serioja90 e sto cercando di modificarlo per vedere se un albero è perfettamente bilanciato,mi potete dare qualche consiglio su come fare?
E' possibile che basti sostituire nell'ultima stringa 1 con 0?

[serioja90]

Basta modificare l'ultima istruzione in questo modo:

return (left.altezza()-right.altezza()==0) && left.bilanciato() && right.bilanciato();

Dato che vuoi un albero perfettamente bilanciato, basta verificare che il sottoalbero sinistro sia uguale al sottoalbero destro, per cui la differenza delle loro altezze deve essere uguale a 0.

[ReDevil88]

Ok,gazie serioja90,approffitto per chiedere se in questo caso

public boolean bilanciato(){     return aux(this.altezza()); }  public boolean aux(int n){     if (this==EMPTYTREE){         return n<=1;     }else{         return left.aux(n-1) && right.aux(n-1);     } }

(Cioè nel secondo esempio postato da te)

modificando l'ultima riga di codice così:

return left.aux(n)  && right.aux(n) ;

ottengo un albero binario bilanciato perfettmnete bilanciato
Inoltre non ho ben capito perchè qui:

return n<=1;

viene posto n<=1,cioè se lo voglio ben bilanciato non saprei come porlo

[serioja90]

La funzione aux è una funzione ricorsiva, per cui ad ogni richiamo della funzione devi decrementare il parametro n, per cui nel secondo return ci sono i (n-1), altrimenti otterresti una funzione che non termina mai.

Per quanto riguarda la modifica da fare per ottenere un albero perfettamente bilanciato, devi soltanto modificare il primo return della funzione aux:

return n==0;

Il parametro che viene passato alla funzione aux indica l'altezza del albero.
La funzione, invece, verifica che se gli sottoalberi destro e sinistro hanno altezza n, restituendo alla fine un valore booleano.
Come ho detto in precedenza, la funzione è ricorsiva, per cui richiamando la funzione sui sottoalberi destro e sinistro, viene decrementata anche la loro altezza di uno, per cui (n-1). Alla fine, quando l'albero è vuoto, cioè quando si è arrivato alle foglie dell'albero, devo verificare che n==0, perché ogni foglia deve trovarsi all'altezza n, se voglio un albero perfettamente bilanciato.
Il primo return della funzione è quello che viene fornito quando si arriva ad una foglia dell'albero e il valore restituito viene messo in && con quelli della funzione, quando arriva alle altre foglie. Il risultato della funzione dev'essere un valore booleano, quindi viene restituito il risultato del confronto n==0.

public boolean aux(int n){
    if (this==EMPTYTREE){ 
        return n==0; 
    }else{ 
        return left.aux(n-1) && right.aux(n-1); 
    } 
}

Questa è la funzione aux per verificare se l'albero è perfettamente bilanciato.

Spero di essermi spiegato.