Identificar un árbol balanceado
Para poder distinguir un árbol balanceado de uno que no lo es, solo debemos encontrar un nodo con un factor de equilibrio que no sea ni -1, ni 0, ni 1. Si lo encontramos, podremos afirmar que el árbol NO está equilibrado. Ahora te estarás preguntando, ¿y qué es el factor de equilibrio de un nodo? Pues te lo explico de forma fácil.
Factor de equilibrio
El factor de equilibrio de un nodo es:
factor equilibrio = niveles que podemos bajar por la derecha – niveles que podemos bajar por la izquierda
Por ejemplo, el siguiente nodo A, tiene un factor de equilibrio = 2.
En este ejemplo, podemos afirmar que el árbol NO está equilibrado ya que hemos encontrado un nodo (A) con un factor de equilibrio que no es ni -1, ni 0, ni 1.
Veamos ahora este caso:
Ahora el nodo A tiene un factor de equilibrio = 1. ¿Podemos decir que el árbol está balanceado? NO, porque solo hemos comprobado un nodo y, a lo mejor, hay otro que tiene un factor de equilibrio que no está entre [-1, 1].
Resolviendo ejercicio: ¿es el siguiente árbol un árbol balanceado?
Supongamos que nos dan el siguiente árbol binario:
Para saber si está equilibrado, deberemos calcular el factor de equilibrio explicado anteriormente por cada nodo y comprobar que esté entre [-1, 1].
Observamos que el nodo C tiene un factor de equilibrio = 2, por lo tanto, podemos afirmar que el árbol NO está balanceado.
Ejemplos
En esta sección te dejo 2 ejemplos tanto de árboles balanceados como no balanceados. Además, junto a cada nodo está su factor de equilibrio para que puedas comprobar si son o no equilibrados. Si està entre [-1, 1] se marca en verde, si no, se marca en rojo.
Árboles equilibrados
EJEMPLO 1
EJEMPLO 2
Árboles no balanceados
EJEMPLO 1
EJEMPLO 2
