Un árbol binario equilibrado también se conoce como árbol de altura equilibrada. Se define como árbol binario cuando la diferencia entre la altura del subárbol izquierdo y el subárbol derecho no es mayor que m, donde m suele ser igual a 1. La altura de un árbol es el número de aristas en el camino más largo entre los nodo raíz y el nodo hoja.
El árbol de arriba es un árbol de búsqueda binaria . Un árbol de búsqueda binario es un árbol en el que cada nodo del lado izquierdo tiene un valor más bajo que su nodo padre, y el nodo del lado derecho tiene un valor más alto que su nodo padre. En el árbol anterior, n1 es un nodo raíz y n4, n6, n7 son los nodos hoja. El nodo n7 es el nodo más alejado del nodo raíz. n4 y n6 contienen 2 aristas y existen tres aristas entre el nodo raíz y el nodo n7. Dado que n7 es el más alejado del nodo raíz; por lo tanto, la altura del árbol de arriba es 3.
Ahora veremos si el árbol de arriba está equilibrado o no. El subárbol izquierdo contiene los nodos n2, n4, n5 y n7, mientras que el subárbol derecho contiene los nodos n3 y n6. El subárbol izquierdo tiene dos nodos hoja, es decir, n4 y n7. Sólo hay una arista entre los nodos n2 y n4 y dos aristas entre los nodos n7 y n2; por lo tanto, el nodo n7 es el más alejado del nodo raíz. La altura del subárbol izquierdo es 2. El subárbol derecho contiene solo un nodo hoja, es decir, n6, y tiene solo un borde; por lo tanto, la altura del subárbol derecho es 1. La diferencia entre las alturas del subárbol izquierdo y del subárbol derecho es 1. Como obtuvimos el valor 1, podemos decir que el árbol de arriba es un árbol con altura equilibrada. Este proceso de calcular la diferencia entre las alturas debe realizarse para cada nodo como n2, n3, n4, n5, n6 y n7. Cuando procesamos cada nodo, encontraremos que el valor de k no es más que 1, por lo que podemos decir que el árbol anterior es equilibrado árbol binario .
En el árbol anterior, n6, n4 y n3 son los nodos hoja, donde n6 es el nodo más alejado del nodo raíz. Existen tres aristas entre el nodo raíz y el nodo hoja; por lo tanto, la altura del árbol anterior es 3. Cuando consideramos n1 como el nodo raíz, entonces el subárbol izquierdo contiene los nodos n2, n4, n5 y n6, mientras que el subárbol contiene el nodo n3. En el subárbol izquierdo, n2 es un nodo raíz y n4 y n6 son nodos hoja. Entre los nodos n4 y n6, n6 es el nodo más alejado de su nodo raíz y n6 tiene dos aristas; por lo tanto, la altura del subárbol izquierdo es 2. El subárbol derecho tiene hijos a su izquierda y derecha; por lo tanto, la altura del subárbol derecho es 0. Dado que la altura del subárbol izquierdo es 2 y el subárbol derecho es 0, la diferencia entre la altura del subárbol izquierdo y el subárbol derecho es 2. Según la definición, la diferencia entre la altura del subárbol izquierdo y el subárbol derecho no debe ser mayor que 1. En este caso, la diferencia viene a ser 2, que es mayor que 1; por lo tanto, el árbol binario anterior es un árbol de búsqueda binario desequilibrado.
¿Por qué necesitamos un árbol binario equilibrado?
Entendamos la necesidad de un árbol binario equilibrado a través de un ejemplo.
El árbol anterior es un árbol de búsqueda binario porque todos los nodos del subárbol izquierdo son más pequeños que su nodo padre y todos los nodos del subárbol derecho son mayores que su nodo padre. Supongamos que queremos encontrar el valor 79 en el árbol de arriba. Primero, comparamos el valor del nodo n1 con 79; como el valor de 79 no es igual a 35 y es mayor que 35 entonces nos movemos al nodo n3, es decir, 48. Como el valor 79 no es igual a 48 y 79 es mayor que 48, entonces nos movemos hacia la derecha hijo de 48. El valor del hijo derecho del nodo 48 es 79, que es igual al valor a buscar. El número de saltos necesarios para buscar un elemento 79 es 2 y el número máximo de saltos necesarios para buscar cualquier elemento es 2. El caso promedio para buscar un elemento es O(logn).
El árbol anterior también es un árbol de búsqueda binario porque todos los nodos del subárbol izquierdo son más pequeños que su nodo padre y todos los nodos del subárbol derecho son mayores que su nodo padre. Supongamos que queremos encontrar el valor 79 en el árbol de arriba. Primero, comparamos el valor 79 con un nodo n4, es decir, 13. Dado que el valor 79 es mayor que 13, nos movemos al hijo derecho del nodo 13, es decir, n2 (21). El valor del nodo n2 es 21, que es menor que 79, por lo que nuevamente nos movemos hacia la derecha del nodo 21. El valor del hijo derecho del nodo 21 es 29. Dado que el valor 79 es mayor que 29, nos movemos hacia la derecha. hijo del nodo 29. El valor del hijo derecho del nodo 29 es 35, que es menor que 79, por lo que nos movemos al hijo derecho del nodo 35, es decir, 48. El valor 79 es mayor que 48, por lo que nos movemos al hijo derecho del nodo 48. El valor del nodo secundario derecho de 48 es 79, que es igual al valor a buscar. En este caso, el número de saltos necesarios para buscar un elemento es 5. En este caso, el peor de los casos es O(n).
Si el número de nodos aumenta, la fórmula utilizada en el diagrama de árbol1 es más eficiente que la fórmula utilizada en el diagrama de árbol2. Supongamos que la cantidad de nodos disponibles en los dos árboles anteriores es 100.000. Para buscar cualquier elemento en un diagrama de árbol2, el tiempo necesario es 100.000 µs, mientras que el tiempo necesario para buscar un elemento en el diagrama de árbol es log(100.000), que equivale a 16,6 µs. Podemos observar la enorme diferencia de tiempo entre los dos árboles de arriba. Por lo tanto, concluimos que el árbol binario balanceado proporciona búsquedas más rápidas que la estructura de datos del árbol lineal.