Un arbre binari equilibrat també es coneix com a arbre equilibrat d'alçada. Es defineix com a arbre binari quan la diferència entre l'alçada del subarbre esquerre i el subarbre dret no és superior a m, on m sol ser igual a 1. L'alçada d'un arbre és el nombre d'arestes del camí més llarg entre els el node arrel i el node fulla.
L'arbre de dalt és a arbre de cerca binari . Un arbre de cerca binari és un arbre en què cada node del costat esquerre té un valor més baix que el seu node pare, i el node del costat dret té un valor més alt que el seu node pare. A l'arbre anterior, n1 és un node arrel i n4, n6, n7 són els nodes fulla. El node n7 és el node més allunyat del node arrel. Els n4 i n6 contenen 2 arestes i hi ha tres arestes entre el node arrel i el node n7. Com que n7 és el més allunyat del node arrel; per tant, l'alçada de l'arbre anterior és de 3.
Ara veurem si l'arbre anterior està equilibrat o no. El subarbre esquerre conté els nodes n2, n4, n5 i n7, mentre que el subarbre dret conté els nodes n3 i n6. El subarbre esquerre té dos nodes fulla, és a dir, n4 i n7. Només hi ha una vora entre els nodes n2 i n4 i dues arestes entre els nodes n7 i n2; per tant, el node n7 és el més allunyat del node arrel. L'alçada del subarbre esquerre és 2. El subarbre dret conté només un node fulla, és a dir, n6, i només té una vora; per tant, l'altura del subarbre dret és 1. La diferència entre les altures del subarbre esquerre i el subarbre dret és 1. Com que hem obtingut el valor 1, podem dir que l'arbre anterior és un arbre equilibrat d'altura. Aquest procés de càlcul de la diferència entre les altures s'ha de realitzar per a cada node com n2, n3, n4, n5, n6 i n7. Quan processem cada node, trobarem que el valor de k no és superior a 1, de manera que podem dir que l'arbre anterior és un arbre equilibrat. arbre binari .
A l'arbre anterior, n6, n4 i n3 són els nodes fulla, on n6 és el node més allunyat del node arrel. Hi ha tres arestes entre el node arrel i el node fulla; per tant, l'alçada de l'arbre anterior és 3. Quan considerem n1 com el node arrel, aleshores el subarbre esquerre conté els nodes n2, n4, n5 i n6, mentre que el subarbre conté el node n3. Al subarbre esquerre, n2 és un node arrel, i n4 i n6 són nodes fulla. Entre n4 i n6 nodes, n6 és el node més allunyat del seu node arrel, i n6 té dues arestes; per tant, l'alçada del subarbre esquerre és 2. El subarbre dret té algun fill a la seva esquerra i dreta; per tant, l'alçada del subarbre dret és 0. Com que l'alçada del subarbre esquerre és 2 i el subarbre dret és 0, la diferència entre l'alçada del subarbre esquerre i el subarbre dret és 2. Segons la definició, la diferència entre l'alçada del subarbre esquerre i el subarbre dret no ha de ser superior a 1. En aquest cas, la diferència arriba a ser 2, que és més gran que 1; per tant, l'arbre binari anterior és un arbre de cerca binari desequilibrat.
Per què necessitem un arbre binari equilibrat?
Entenem la necessitat d'un arbre binari equilibrat a través d'un exemple.
L'arbre de dalt és un arbre de cerca binari perquè tots els nodes del subarbre esquerre són més petits que el seu node pare i tots els nodes del subarbre dret són més grans que el seu node pare. Suposem que volem trobar el valor 79 a l'arbre anterior. Primer, comparem el valor del node n1 amb 79; com que el valor de 79 no és igual a 35 i és més gran que 35, passem al node n3, és a dir, 48. Com que el valor 79 no és igual a 48 i 79 és major que 48, per tant ens movem cap a la dreta. fill de 48. El valor del fill dret del node 48 és 79, que és igual al valor que cal cercar. El nombre de salts necessaris per cercar un element 79 és 2 i el nombre màxim de salts necessaris per cercar qualsevol element és 2. El cas mitjà per cercar un element és O(logn).
L'arbre anterior també és un arbre de cerca binari perquè tots els nodes del subarbre esquerre són més petits que el seu node pare i tots els nodes del subarbre dret són més grans que el seu node pare. Suposem que volem trobar el valor 79 a l'arbre anterior. Primer, comparem el valor 79 amb un node n4, és a dir, 13. Com que el valor 79 és més gran que 13, passem al fill dret del node 13, és a dir, n2 (21). El valor del node n2 és 21, que és més petit que 79, de manera que tornem a moure's a la dreta del node 21. El valor del fill dret del node 21 és 29. Com que el valor 79 és més gran que 29, ens movem cap a la dreta. fill del node 29. El valor del fill dret del node 29 és 35, que és més petit que 79, de manera que ens movem al fill dret del node 35, és a dir, 48. El valor 79 és més gran que 48, de manera que passem al fill dret. del node 48. El valor del node fill dret de 48 és 79, que és igual al valor que s'ha de cercar. En aquest cas, el nombre de salts necessaris per cercar un element és 5. En aquest cas, el pitjor dels casos és O(n).
Si augmenta el nombre de nodes, la fórmula utilitzada al diagrama d'arbre1 és més eficient que la fórmula utilitzada al diagrama d'arbre2. Suposem que el nombre de nodes disponibles als dos arbres anteriors és 100.000. Per cercar qualsevol element en un diagrama d'arbre2, el temps necessari és de 100.000 µs, mentre que el temps necessari per cercar un element en un diagrama d'arbre és log(100.000), que és igual a 16,6 µs. Podem observar l'enorme diferència de temps entre dos arbres de dalt. Per tant, concloem que l'arbre binari d'equilibri proporciona una cerca més ràpida que l'estructura de dades de l'arbre lineal.