Albero Binario Bilanciato in Java

[One2]

Problema:
Dato un albero binario,devo vedere se è bilanciato o no.
La mia idea è quella di contare i livelli dell'albero dal livello 0 al livello n,e vedere se il numero di nodi al livello $n$ è uguale a $2^n$,se lo è bilanciato alterimenti non è bilanciato.Il problema maggiore che riscontro è quello scorrere l'albero fino in fondo per vedere quanrùti livelli ha in tutto.
Mi potete dire se e dove sbaglio,e come faccio a vedere di quanti livelli è composto l'albero?

[Rggb1]

Puoi usare l'algoritmo di visita in larghezza o in profondità, ovviamente.

"One":Mi potete dire se e dove sbaglio,e come faccio a vedere di quanti livelli è composto l'albero?

Ehm, non ho capito... Non vedo nessun codice Java, quindi non posso capire dove sbagli.

[apatriarca]

Ti consiglio di analizzare il bilanciamento dell'albero a livello locale invece che globale. Un metodo è quello di verificare che per ogni nodo dell'albero, i suoi due sottoalberi hanno la stessa profondità o siano diversi per al massimo un livello.

[One2]

Aggiungo che devo creare un programma ricorsivo:
io avevo pensato a questo:
Public static boolean ABR_Bilanciato(SimpBTree t)
{
If (t==EmptyBTree) //se è vuoto esci
Return false;
If((!t.Left().Empty()&&t.Right().Empty())||(t.Left().Empty()&&!t.Right().Empty())) //se è sbilanciato esci
Return false;
Else
ABR_Bilanciato(t.Left());
ABR_Bilanciato(t.Right());
...................................
Così dovrei vedere se NON è bilanciato,il problema ora è trovare una condizione d'uscita nel caso l'albero sia bilanciato

[apatriarca]

Il tuo algoritmo non funziona. Considera il seguente albero:

              A
        B          C
    D      E
 F   G

In base al tuo algoritmo l'albero non è sbilanciato quando è invece evidente che lo sia. La tua condizione può comunque essere riscritta nella forma:

t.Right().Empty() == t.Left().Empty().

[One2]

Ho fatto qualche modifica al programma precedente:


Public static boolean ABR_Bilanciato(SimpBTree t)
{
If (t==EmptyBTree)
Return false;
Else
If((t.Left().Empty()&&t.Right().Empty())||(!t.Left().Empty()&&!t.Right().Empty()))
Return false;
Else
{
Boolean h1=ABR_Bilanciato(t.Left());
Boolean h2=ABR_Bilanciato(t.Right());
If((h1==false)||(h2==false))
Return false;
If((h1==h2)
Return true;
Else
Return false;
}
}

Non credo sia priva di errori,soprattutto riguardo l'uscita dalla ricorsione.
Ho modificato sopratutto la condizione in grassetto...Considerando l'esempio di albero sbilancito fatto precedentememnte da te,io pensavo che If (t==EmptyBTree)(cioè se tè è un albero vuoto) restituisse false quando incontrava il nodo C dell'albero.

[Rggb1]

La condizione in grassetto non va bene. Se la sinistra e la destra son vuote (metodo Empty) ritorna falso aka "non bilanciato"; se la sinistra e la destra NON sono vuote, idem. Direi di ribaltare la condizione, che dici?

PS. Come già suggerito, cerca di usare i tag [$$code$$], inoltre la condizione è equivalente a quella che ti ha suggerito apatriarca prima, che è più concisa e si legge decisamente meglio.

[One2]

Considerando i vostri suggerimenti ho provato a fare qualche modifica,l'ho fatta un po di getto non so se sia corretta

Public static boolean ABR_Bilanciato(SimpBTree<E> t)
{
If (t==EmptyBTree)
Return false;
if(t.Right().Empty() == t.Left().Empty())
Return true;
        Else
        {
              ABR_Bilanciato(t.Left());
	      ABR_Bilanciato(t.Right());
         }
} 

[apatriarca]

Prima di tutto, perché un albero vuoto dovrebbe non essere bilanciato? Comunque ti consiglio di abbandonare questo approccio. Non è possibile affermare se un albero è bilanciato o meno osservando solo se un qualche nodo ha o meno figli. Devi calcolarti per ogni sottoalbero una qualche quantità più utile come il numero di livelli massimi del sottoalbero.

[One2]

Era quello che pensavo di fare all'inizio(nel primo post),ma non riuscivo a trovare il numero di livelli che componevano l'albero.Per vedere il bilanciamento dovrei conoscere il numero dei livelli dell'albero e vedere se all'ultimo livello($n$) ci sono $2^n$ nodi,giusto?
per vedere i livelli avevo pensato di inserire un contatore nell'algoritmo di visita anticipata dell'albero binario:

 VBant(t)
{
  if t==EmptyBtree();
  return(i);
else
{
  VBant(t.Right());
  VBant(t.Left());
   i++;
}}

il valore finale di $i$ dovrebbe essere il valore del livello più alto....

[apatriarca]

Non è detto che un albero bilanciato abbia \(2^h\) nodi (dove \(h\) è l'altezza dell'albero) all'ultimo livello. Non è questa la mia definizione di albero binario. In base a questa definizione solo alberi con \( 2^{h+1}-1 \) nodi potrebbero essere bilanciati.

[One2]

Io devo vedere se un albero è perfettamente bilanciato,non l'ho specificato prima...
da Wiki:

un albero è perfettamente bilanciato se ha tutte le foglie al medesimo livello, ovvero se ogni foglia dell'albero ha la medesima distanza dalla radice.

[apatriarca]

Ok, questo cambia un po' le cose. Per prima cosa non è sufficiente sapere se i due sottoalberi sono perfettamente bilanciati per sapere se l'albero intero lo è. Hai anche bisogno di sapere qual'è la sua altezza. Un albero è perfettamente bilanciato se entrambi i suoi sottoalberi lo sono e hanno la stessa altezza. Prova a partire da questa idea.

[hamming_burst]

Un altro modo di verdere la questione è considerare la definizione ( che è una proprietà intrinseca di un albero perfettamente bilanciato) di un albero completo.
Basta contare i nodi ad ogni livelli, se questi sono tutti potenze di $2$ siamo in un albero perfettamente bilanciato.

Nel caso di vedere se un albero è k-bilanciato si può utilizzare la proprietà il valore assoluto tra il cammino radice-foglia massimo e minimo non sia superiore ad un valore fissato $k$. Nel caso perfettamente bilanciato è ovviamente $0$.

EDIT:
ok, leggendo le risposte precedenti, mi sembra circa era già stata considerata la possibilità di "contare".

[One2]

Ho provato a seguire il metodo consigliato da apatriarca,per ora spero di aver trovato il modo di vedere se i sottoalberi hanno la stessa altezza:

Public static int height(SimpBTree<E> t){

if (t==EmptyBTree)
return 0;
else
{
int HLeft = height(t.Left());
int HRight = height(t.Right());
}
if( HLeft > HRight )
return (HLeft +1);
else
return (HRight +1); 
.........................

se $HLeft==HRight$ ,allora hanno la stessa altezzami potreste dire se è corretto?

[apatriarca]

Sì direi che quel metodo è corretto, ma puoi calcolare l'altezza nella stessa funzione nel quale verifichi che l'albero sia bilanciato. Ovviamente, in questo caso, la ricorsione non sarà effettuata all'interno del metodo pubblico, ma in un metodo privato in cui si calcola sia se il sottoalbero è bilanciato sia l'altezza.

[One2]

Ok,per vedere se un sottoalbero binario è bilanciato devo verificare che:

(!t.Right().Empty()&&(!t.Left().Empty)

???
Per vedere se hanno la stessa altezza devo porre inoltre

if(HLeft==HRight )

???

[apatriarca]

No, ti ho già detto che la prima condizione non serve a niente in questo caso. Devi richiamare il tuo metodo in modo ricorsivo in modo da avere questa risposta.

[One2]

Riferendomi all'intervento di Hamming_burst,ho trovato un vecchio esercizio risolto,credo vada bene:

public int Height(){
    if (this==EmptyBtree()){
        return 0;
    }else
   {
        return 1+Massimo(Left.Height(),Right.Height());
    }
}
public boolean Balance(){
    if (this==EmptyBtree()){
        return true;
    }else{
        return Abs(Left.height()-Right.height ())==0 && Left.Balance() && Right.Balance();
    }
}

Però volevo fare anche il metodo proposto da apatriarca,anche se non ho ancora capito bene come fare la ricorsione