Conocer la altura, la profundidad, la cantidad de hojas y otros indicadores de un árbol binario ayuda a tomar decisiones de balanceo, ajustar heurísticas de búsqueda y validar que la estructura se mantiene saludable. Este tema recopila las propiedades más utilizadas y ofrece fragmentos de código en Python con la clase ArbolBinarioOrdenado.
Trabajaremos con un modelo simple basado en clases. Si necesitas campos adicionales (por ejemplo, para cachear la altura), puedes agregarlos manteniendo la interfaz.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.izquierdo = None
self.derecho = None
class ArbolBinarioOrdenado:
def __init__(self):
self.raiz = None
def insertar(self, valor):
if self.raiz is None:
self.raiz = Nodo(valor)
return self.raiz
actual = self.raiz
while True:
if valor < actual.valor:
if actual.izquierdo is None:
actual.izquierdo = Nodo(valor)
return actual.izquierdo
actual = actual.izquierdo
else:
if actual.derecho is None:
actual.derecho = Nodo(valor)
return actual.derecho
actual = actual.derechoLa altura de un nodo es la cantidad de aristas en el camino más largo hacia una hoja. La profundidad representa la distancia respecto de la raíz. Calcular la altura completa nos permite estimar la complejidad de las operaciones.
class ArbolBinarioOrdenado:
# ...
def altura(self, nodo=None):
def _altura(n):
if n is None:
return -1 # hojas quedan con altura 0
return 1 + max(_altura(n.izquierdo), _altura(n.derecho))
nodo = self.raiz if nodo is None else nodo
return _altura(nodo)El tamaño del árbol se obtiene sumando la cantidad de nodos en cada subárbol. Para contar hojas, verificamos que un nodo no tenga hijos.
class ArbolBinarioOrdenado:
# ...
def contar_nodos(self, nodo=None):
def _contar(n):
if n is None:
return 0
return 1 + _contar(n.izquierdo) + _contar(n.derecho)
nodo = self.raiz if nodo is None else nodo
return _contar(nodo)
def contar_hojas(self, nodo=None):
def _contar_hojas(n):
if n is None:
return 0
if n.izquierdo is None and n.derecho is None:
return 1
return _contar_hojas(n.izquierdo) + _contar_hojas(n.derecho)
nodo = self.raiz if nodo is None else nodo
return _contar_hojas(nodo)Los nodos internos son aquellos que poseen al menos un hijo. Podemos calcular cuántos hay y, si es necesario, clasificar el grado (cantidad de hijos).
class ArbolBinarioOrdenado:
# ...
def contar_internos(self, nodo=None):
def _contar_internos(n):
if n is None or (n.izquierdo is None and n.derecho is None):
return 0
return 1 + _contar_internos(n.izquierdo) + _contar_internos(n.derecho)
nodo = self.raiz if nodo is None else nodo
return _contar_internos(nodo)El factor de balance se define como la diferencia entre la altura del subárbol izquierdo y el derecho. Un valor cercano a cero indica un árbol equilibrado.
class ArbolBinarioOrdenado:
# ...
def factor_balance(self, nodo=None):
nodo = self.raiz if nodo is None else nodo
if nodo is None:
return 0
return self.altura(nodo.izquierdo) - self.altura(nodo.derecho)El ancho máximo indica cuántos nodos se encuentran en el nivel más poblado. Podemos calcularlo con un recorrido por niveles:
from collections import deque
class ArbolBinarioOrdenado:
# ...
def ancho_maximo(self):
if self.raiz is None:
return 0
cola = deque([self.raiz])
max_ancho = 0
while cola:
nivel_actual = len(cola)
max_ancho = max(max_ancho, nivel_actual)
for _ in range(nivel_actual):
nodo = cola.popleft()
if nodo.izquierdo:
cola.append(nodo.izquierdo)
if nodo.derecho:
cola.append(nodo.derecho)
return max_anchoPara conocer la profundidad de un determinado valor seguimos el mismo camino que en una búsqueda y contamos el número de aristas recorridas.
class ArbolBinarioOrdenado:
# ...
def profundidad_de_valor(self, valor):
nivel = 0
actual = self.raiz
while actual:
if valor == actual.valor:
return nivel
nivel += 1
actual = actual.izquierdo if valor < actual.valor else actual.derecho
return -1 # no encontradoCombinar estas funciones permite monitorear el estado del árbol: si el factor de balance se dispara, se planifica un rebalanceo; si la cantidad de hojas disminuye drásticamente, conviene verificar que la inserción no esté sesgando los datos.
El siguiente programa arma un árbol, calcula todas las medidas y las imprime en consola.
from collections import deque
class Nodo:
def __init__(self, valor):
self.valor = valor
self.izquierdo = None
self.derecho = None
class ArbolBinarioOrdenado:
def __init__(self):
self.raiz = None
def insertar(self, valor):
if self.raiz is None:
self.raiz = Nodo(valor)
return self.raiz
actual = self.raiz
while True:
if valor < actual.valor:
if actual.izquierdo is None:
actual.izquierdo = Nodo(valor)
return actual.izquierdo
actual = actual.izquierdo
else:
if actual.derecho is None:
actual.derecho = Nodo(valor)
return actual.derecho
actual = actual.derecho
def altura(self, nodo=None):
def _altura(n):
if n is None:
return -1
return 1 + max(_altura(n.izquierdo), _altura(n.derecho))
nodo = self.raiz if nodo is None else nodo
return _altura(nodo)
def contar_nodos(self, nodo=None):
def _contar(n):
if n is None:
return 0
return 1 + _contar(n.izquierdo) + _contar(n.derecho)
nodo = self.raiz if nodo is None else nodo
return _contar(nodo)
def contar_hojas(self, nodo=None):
def _contar_hojas(n):
if n is None:
return 0
if n.izquierdo is None and n.derecho is None:
return 1
return _contar_hojas(n.izquierdo) + _contar_hojas(n.derecho)
nodo = self.raiz if nodo is None else nodo
return _contar_hojas(nodo)
def contar_internos(self, nodo=None):
def _contar_internos(n):
if n is None or (n.izquierdo is None and n.derecho is None):
return 0
return 1 + _contar_internos(n.izquierdo) + _contar_internos(n.derecho)
nodo = self.raiz if nodo is None else nodo
return _contar_internos(nodo)
def factor_balance(self, nodo=None):
nodo = self.raiz if nodo is None else nodo
if nodo is None:
return 0
return self.altura(nodo.izquierdo) - self.altura(nodo.derecho)
def ancho_maximo(self):
if self.raiz is None:
return 0
cola = deque([self.raiz])
max_ancho = 0
while cola:
nivel_actual = len(cola)
max_ancho = max(max_ancho, nivel_actual)
for _ in range(nivel_actual):
nodo = cola.popleft()
if nodo.izquierdo:
cola.append(nodo.izquierdo)
if nodo.derecho:
cola.append(nodo.derecho)
return max_ancho
def profundidad_de_valor(self, valor):
nivel = 0
actual = self.raiz
while actual:
if valor == actual.valor:
return nivel
nivel += 1
actual = actual.izquierdo if valor < actual.valor else actual.derecho
return -1
if __name__ == "__main__":
arbol = ArbolBinarioOrdenado()
for valor in [10, 5, 15, 3, 7, 12, 18]:
arbol.insertar(valor)
print(f"Altura: {arbol.altura()}")
print(f"Cantidad de nodos: {arbol.contar_nodos()}")
print(f"Cantidad de hojas: {arbol.contar_hojas()}")
print(f"Nodos internos: {arbol.contar_internos()}")
print(f"Ancho maximo: {arbol.ancho_maximo()}")
buscado = 7
profundidad = arbol.profundidad_de_valor(buscado)
print(f"Profundidad de {buscado}: {profundidad}")