Un albero binario bilanciato è noto anche come albero bilanciato in altezza. Si definisce albero binario quando la differenza tra l'altezza del sottoalbero sinistro e del sottoalbero destro non è superiore a m, dove m è solitamente uguale a 1. L'altezza di un albero è il numero di spigoli sul percorso più lungo tra i nodo radice e nodo foglia.
L'albero sopra è a albero di ricerca binario . Un albero di ricerca binario è un albero in cui ciascun nodo sul lato sinistro ha un valore inferiore rispetto al nodo genitore e il nodo sul lato destro ha un valore superiore rispetto al nodo genitore. Nell'albero sopra, n1 è un nodo radice e n4, n6, n7 sono i nodi foglia. Il nodo n7 è il nodo più lontano dal nodo radice. N4 e n6 contengono 2 bordi ed esistono tre bordi tra il nodo radice e il nodo n7. Poiché n7 è il più lontano dal nodo radice; pertanto, l'altezza dell'albero sopra è 3.
Ora vedremo se l'albero di cui sopra è equilibrato oppure no. Il sottoalbero di sinistra contiene i nodi n2, n4, n5 e n7, mentre il sottoalbero di destra contiene i nodi n3 e n6. Il sottoalbero di sinistra ha due nodi foglia, ovvero n4 e n7. C'è solo un arco tra i nodi n2 e n4 e due archi tra i nodi n7 e n2; pertanto, il nodo n7 è il più lontano dal nodo radice. L'altezza del sottoalbero sinistro è 2. Il sottoalbero destro contiene solo un nodo foglia, cioè n6, e ha un solo bordo; pertanto, l'altezza del sottoalbero destro è 1. La differenza tra le altezze del sottoalbero sinistro e del sottoalbero destro è 1. Poiché abbiamo ottenuto il valore 1, possiamo dire che l'albero sopra è un albero con altezza bilanciata. Questo processo di calcolo della differenza tra le altezze dovrebbe essere eseguito per ciascun nodo come n2, n3, n4, n5, n6 e n7. Quando elaboriamo ciascun nodo, troveremo che il valore di k non è maggiore di 1, quindi possiamo dire che l'albero sopra è un albero bilanciato albero binario .
Nell'albero sopra, n6, n4 e n3 sono i nodi foglia, dove n6 è il nodo più lontano dal nodo radice. Esistono tre bordi tra il nodo radice e il nodo foglia; pertanto, l'altezza dell'albero sopra è 3. Quando consideriamo n1 come nodo radice, il sottoalbero sinistro contiene i nodi n2, n4, n5 e n6, mentre il sottoalbero contiene il nodo n3. Nel sottoalbero di sinistra, n2 è un nodo radice e n4 e n6 sono nodi foglia. Tra i nodi n4 e n6, n6 è il nodo più lontano dal nodo radice e n6 ha due bordi; pertanto, l'altezza del sottoalbero sinistro è 2. Il sottoalbero destro ha dei figli a sinistra e a destra; pertanto, l'altezza del sottoalbero destro è 0. Poiché l'altezza del sottoalbero sinistro è 2 e il sottoalbero destro è 0, quindi la differenza tra l'altezza del sottoalbero sinistro e quello destro è 2. Secondo la definizione, la differenza tra l'altezza del sottoalbero di sinistra e del sottoalbero di destra non deve essere maggiore di 1. In questo caso la differenza diventa 2, che è maggiore di 1; pertanto, l'albero binario sopra è un albero di ricerca binario sbilanciato.
Perché abbiamo bisogno di un albero binario bilanciato?
Capiamo la necessità di un albero binario bilanciato attraverso un esempio.
L'albero sopra è un albero di ricerca binario perché tutti i nodi del sottoalbero sinistro sono più piccoli del nodo genitore e tutti i nodi del sottoalbero destro sono maggiori del nodo genitore. Supponiamo di voler trovare il valore 79 nell'albero sopra. Per prima cosa confrontiamo il valore del nodo n1 con 79; poiché il valore di 79 non è uguale a 35 ed è maggiore di 35 quindi ci spostiamo al nodo n3, cioè 48. Dato che il valore 79 non è uguale a 48 e 79 è maggiore di 48, quindi ci spostiamo a destra figlio di 48. Il valore del figlio destro del nodo 48 è 79 che è uguale al valore da cercare. Il numero di salti richiesti per cercare un elemento 79 è 2 e il numero massimo di salti richiesti per cercare qualsiasi elemento è 2. Il caso medio per cercare un elemento è O(logn).
L'albero sopra è anche un albero di ricerca binario perché tutti i nodi del sottoalbero sinistro sono più piccoli del nodo genitore e tutti i nodi del sottoalbero destro sono maggiori del nodo genitore. Supponiamo di voler trovare il valore 79 nell'albero sopra. Innanzitutto, confrontiamo il valore 79 con un nodo n4, ovvero 13. Poiché il valore 79 è maggiore di 13, ci spostiamo al figlio destro del nodo 13, ovvero n2 (21). Il valore del nodo n2 è 21 che è inferiore a 79, quindi ci spostiamo nuovamente a destra del nodo 21. Il valore del figlio destro del nodo 21 è 29. Poiché il valore 79 è maggiore di 29, ci spostiamo a destra figlio del nodo 29. Il valore del figlio destro del nodo 29 è 35 che è inferiore a 79, quindi ci spostiamo sul figlio destro del nodo 35, ovvero 48. Il valore 79 è maggiore di 48, quindi ci spostiamo sul figlio destro del nodo 48. Il valore del nodo figlio destro di 48 è 79 che è uguale al valore da cercare. In questo caso, il numero di salti richiesti per cercare un elemento è 5. In questo caso, il caso peggiore è O(n).
Se il numero di nodi aumenta, la formula utilizzata nel diagramma ad albero1 è più efficiente della formula utilizzata nel diagramma ad albero2. Supponiamo che il numero di nodi disponibili in entrambi gli alberi sopra sia 100.000. Per cercare qualsiasi elemento in un diagramma ad albero2, il tempo impiegato è 100.000 µs mentre il tempo impiegato per cercare un elemento in un diagramma ad albero è log(100.000) che è pari a 16,6 µs. Possiamo osservare l'enorme differenza di tempo tra i due alberi sopra. Pertanto, concludiamo che l'albero binario di equilibrio fornisce una ricerca più veloce rispetto alla struttura dati dell'albero lineare.