Un arbre binari està equilibrat si l'alçada de l'arbre és O(Log n) on n és el nombre de nodes. Per exemple, l'arbre AVL manté l'alçada O(Log n) assegurant-se que la diferència entre les altures dels subarbres esquerre i dret és com a màxim 1. Els arbres vermell-negre mantenen l'alçada O(Log n) assegurant-se que el nombre de nodes negres a cada camí de l'arrel a la fulla és el mateix i que no hi ha nodes vermells adjacents. Els arbres de cerca binària equilibrada són bons pel que fa al rendiment, ja que proporcionen temps O(log n) per cercar, inserir i suprimir.
Un arbre binari equilibrat és un arbre binari que segueix les 3 condicions:
- L'alçada de l'arbre esquerre i dret per a qualsevol node no difereix en més d'1.
- El subarbre esquerre d'aquest node també està equilibrat.
- El subarbre dret d'aquest node també està equilibrat.
Un sol node sempre està equilibrat. També es coneix com a arbre binari d'altura equilibrada.
Exemple :
Arbre binari equilibrat i desequilibrat
És un tipus d'arbre binari en el qual la diferència entre l'alçada del subarbre esquerre i dret per a cada node és 0 o 1. A la figura anterior, el node arrel que té un valor 0 està desequilibrat amb una profunditat de 2 unitats. .
Aplicació de l'arbre binari equilibrat:
- Arbres AVL
- Arbre negre vermell
- Arbre de cerca binari equilibrat
Avantatges de l'arbre binari equilibrat:
- Les actualitzacions no destructives són compatibles amb un arbre binari equilibrat amb la mateixa eficàcia asimptòtica.
- Les consultes d'interval i la iteració en la seqüència correcta són factibles per l'arbre binari equilibrat.