[Algoritmi] Verifica Albero Binario Bilanciato

[xneo1]

Salve a tutti,

innanzitutto parto con la definizione di albero binario bilanciato (in altezza):

Un albero binario si dice bilanciato se per ogni nodo il valore assoluto della differenza tra l'altezza del sottoalbero sinistro e l'altezza del sottoalbero destro è minore o uguale ad 1

E' facile realizzare un algoritmo ricorsivo che verifichi che un albero binario sia bilanciato;
eccone una versione in Java

public static boolean bilanciato(Albero a) {
    if(a==null) return true;

    if(Math.abs(altezza(a.sinistro())-altezza(a.destro()))>1) return false;

    return bilanciato(a.sinistro()) && bilanciato(a.destro());
}

I miei dubbi stanno sulla complessita' temporale.

Premesso che la complessità temporale del metodo altezza sia O(n) dove n è il numero di nodi dell'albero,
se l'albero è degenere la complessità temporale di bilanciato è anch'essa O(n),in quando dovrei spendere tempo nel calcolare l'altezza del figlio sinistro e l'altezza del figlio destro (in tutto n-1 nodi) una sola volta e quindi restituire false al secondo if.

Se l'albero è completo, e quindi anche bilanciato, nel calcolare l'altezza dei vari sottoalberi sinistri e destri andrei a contare più volte dei nodi, tuttavia credo che la complessità rimanga comunque lineare però non ne sono molto sicuro.

Grazie

[apatriarca]

Quando si scrive una funzione ricorsiva è possibile fare calcoli sia quando "si scende" nella ricorsione, sia quando "si sale". Implementando il tuo algoritmo in modo da fare operazioni in entrambe le situazioni puoi ridurti ad una complessità O(n). Nel tuo caso la complessità dovrebbe essere maggiore, credo O(nlogn) ma non ci ho pensato più di tanto.

[xneo1]

Non credo sia O(nlogn) perchè ad ogni chiamata ricorsiva, che nel caso di albero completo sono effettivamente logn, non lavoro sempre su n nodi ma su n/2-1.

[apatriarca]

Se consideriamo il costo \(T(n)\) del tuo algoritmo su un albero con n nodi abbiamo che per prima cosa chiami due volte altezza su \(n/2\) nodi. Altezza ha costo lineare in quanto devi visitare per forza tutti i nodi per sapere qual'è la profondità massima. Dopodiché richiami due volte la tua funzione in modo ricorsivo sui due sottoalberi. Per cui hai un'equazione di ricorrenza della forma
\[ T(n) = 2\,T(n/2) + 2\,(n/2) = 2\,T(n/2) + n. \]
Si tratta della stessa equazione di ricorrenza del merge sort e la sua complessità sappiamo essere \(O(n\,\log(n))\).

[xneo1]

In realtà la prima volta calcolo l'altezza su n-1 nodi, n-1/2 sono i nodi del sottoalbero sinistro e altri n-1/2 del sotto albero destro, quindi dovrebbe venire una relazione di ricorrenza del tipo:
T(n)=2T(n-1/2)+2(n-1/2) non so se il risultato è uguale ma qui non posso applicare il Master Theorem.