Un albero binario è bilanciato se l'altezza dell'albero è O(Log n) dove n è il numero di nodi. Ad esempio, l'albero AVL mantiene l'altezza O(Log n) assicurandosi che la differenza tra le altezze dei sottoalberi sinistro e destro sia al massimo 1. Gli alberi Rosso-Nero mantengono l'altezza O(Log n) assicurandosi che il numero di nodi neri su ogni percorso dalla radice alla foglia è lo stesso e che non ci sono nodi rossi adiacenti. Gli alberi di ricerca binaria bilanciata sono buoni dal punto di vista delle prestazioni poiché forniscono tempo O (log n) per la ricerca, l'inserimento e l'eliminazione.
Un albero binario bilanciato è un albero binario che segue le 3 condizioni:
- L'altezza dell'albero sinistro e destro per qualsiasi nodo non differisce di più di 1.
- Anche il sottoalbero sinistro di quel nodo è bilanciato.
- Anche il sottoalbero destro di quel nodo è bilanciato.
Un singolo nodo è sempre bilanciato. Viene anche definito albero binario con altezza bilanciata.
stringa ad esso
Esempio :
allineare le immagini nei css
Albero binario bilanciato e sbilanciato
È un tipo di albero binario in cui la differenza tra l'altezza del sottoalbero sinistro e quello destro per ciascun nodo è 0 o 1. Nella figura sopra, il nodo radice avente valore 0 è sbilanciato con una profondità di 2 unità .
Applicazione dell'albero binario bilanciato:
- Alberi AVL
- Albero rosso nero
- Albero di ricerca binaria bilanciata
Vantaggi dell'albero binario bilanciato:
- Gli aggiornamenti non distruttivi sono supportati da un albero binario bilanciato con la stessa efficacia asintotica.
- Le query sull'intervallo e l'iterazione nella giusta sequenza sono rese possibili dall'albero binario bilanciato.