Come determinare se un albero binario è bilanciato in Java

1. Panoramica

Gli alberi sono una delle strutture dati più importanti nell'informatica. Di solito siamo interessati a un albero equilibrato, per le sue preziose proprietà . La loro struttura permette di eseguire operazioni come interrogazioni, inserimenti, cancellazioni in tempo logaritmico.

In questo tutorial, impareremo come determinare se un albero binario è bilanciato.

2. Definizioni

Per prima cosa, introduciamo alcune definizioni per assicurarci di essere sulla stessa pagina:

  • Un albero binario - una specie di albero in cui ogni nodo ha zero, uno o due figli
  • Un'altezza di un albero - una distanza massima da una radice a una foglia (uguale alla profondità della foglia più profonda)
  • Un albero equilibrato - una specie di albero in cui per ogni sottostruttura la distanza massima dalla radice a qualsiasi foglia è al massimo maggiore di uno rispetto alla distanza minima dalla radice a qualsiasi foglia

Di seguito possiamo trovare un esempio di albero binario bilanciato. Tre bordi verdi sono una semplice visualizzazione di come determinare l'altezza, mentre i numeri indicano il livello.

3. Oggetti di dominio

Quindi, iniziamo con una classe per il nostro albero:

public class Tree { private int value; private Tree left; private Tree right; public Tree(int value, Tree left, Tree right) { this.value = value; this.left = left; this.right = right; } } 

Per semplicità, supponiamo che ogni nodo abbia un valore intero . Nota che se gli alberi sinistro e destro sono nulli, significa che il nostro nodo è una foglia .

Prima di introdurre il nostro metodo principale vediamo cosa dovrebbe restituire:

private class Result { private boolean isBalanced; private int height; private Result(boolean isBalanced, int height) { this.isBalanced = isBalanced; this.height = height; } }

Così per ogni singola chiamata avremo informazioni su altezza ed equilibrio.

4. Algoritmo

Avendo una definizione di albero equilibrato, possiamo trovare un algoritmo. Quello che dobbiamo fare è controllare la proprietà desiderata per ogni nodo . Può essere ottenuto facilmente con l'attraversamento ricorsivo della ricerca in profondità.

Ora, il nostro metodo ricorsivo verrà richiamato per ogni nodo. Inoltre, terrà traccia della profondità corrente. Ogni chiamata restituirà informazioni sull'altezza e l'equilibrio.

Ora, diamo un'occhiata al nostro metodo approfondito:

private Result isBalancedRecursive(Tree tree, int depth) { if (tree == null) { return new Result(true, -1); } Result leftSubtreeResult = isBalancedRecursive(tree.left(), depth + 1); Result rightSubtreeResult = isBalancedRecursive(tree.right(), depth + 1); boolean isBalanced = Math.abs(leftSubtreeResult.height - rightSubtreeResult.height) <= 1; boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int height = Math.max(leftSubtreeResult.height, rightSubtreeResult.height) + 1; return new Result(isBalanced && subtreesAreBalanced, height); }

Per prima cosa, dobbiamo considerare il caso se il nostro nodo è nullo : restituiremo true (che significa che l'albero è bilanciato) e -1 come altezza.

Quindi, effettuiamo due chiamate ricorsive per la sottostruttura sinistra e destra, mantenendo la profondità aggiornata .

A questo punto, abbiamo i calcoli eseguiti per i figli di un nodo corrente. Ora abbiamo tutti i dati necessari per controllare il saldo:

  • la variabile isBalanced controlla l'altezza per i bambini e
  • substreesAreBalanced indica se anche i sottoalberi sono bilanciati

Infine, possiamo restituire informazioni su equilibrio e altezza. Potrebbe anche essere una buona idea semplificare la prima chiamata ricorsiva con un metodo di facciata:

public boolean isBalanced(Tree tree) { return isBalancedRecursive(tree, -1).isBalanced; }

5. Riepilogo

In questo articolo, abbiamo discusso come determinare se un albero binario è bilanciato. Abbiamo spiegato un approccio di ricerca approfondito.

Come al solito, il codice sorgente con i test è disponibile su GitHub.