Tras implementar inserciones y eliminaciones, el siguiente paso es vigilar el balance del árbol. Un ABB degradado puede comportarse como una lista enlazada, elevando el costo de búsqueda a O(n). En este tema explicamos cómo detectar desequilibrios, aplicar rotaciones simples o dobles y rearmar el árbol a partir de un recorrido inorden para recuperar el rendimiento. Todo el código está escrito en Python y encapsulado en clases.
Partimos de las clases Nodo y ArbolBinarioOrdenado. Si ya cuentas con métodos de inserción y recorrido, puedes integrarlos sin cambios.
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.derechoEl factor de balance se define como la diferencia entre la altura del subárbol izquierdo y el derecho. Valores muy grandes (por ejemplo, mayores a 1 o menores a -1) indican que la estructura necesita una rotación.
class ArbolBinarioOrdenado:
# ...
def altura(self, nodo=None):
def _altura(n):
if n is None:
return 0
return 1 + max(_altura(n.izquierdo), _altura(n.derecho))
nodo = self.raiz if nodo is None else nodo
return _altura(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)Una rotación simple a la derecha compensa un exceso de nodos en la rama izquierda. La rotación a la izquierda actúa de manera simétrica.
class ArbolBinarioOrdenado:
# ...
def rotar_derecha(self, y):
x = y.izquierdo
sub_derecho = x.derecho
x.derecho = y
y.izquierdo = sub_derecho
return x
def rotar_izquierda(self, x):
y = x.derecho
sub_izquierdo = y.izquierdo
y.izquierdo = x
x.derecho = sub_izquierdo
return ySi la rama pesada está inclinada en dirección opuesta (casos LR o RL), primero se aplica una rotación simple sobre el hijo y luego una rotación en sentido contrario sobre el nodo problemático.
class ArbolBinarioOrdenado:
# ...
def balancear_nodo(self, nodo):
balance = self.factor_balance(nodo)
if (balance > 1):
if self.factor_balance(nodo.izquierdo) < 0:
nodo.izquierdo = self.rotar_izquierda(nodo.izquierdo)
return self.rotar_derecha(nodo)
if (balance < -1):
if self.factor_balance(nodo.derecho) > 0:
nodo.derecho = self.rotar_derecha(nodo.derecho)
return self.rotar_izquierda(nodo)
return nodoA diferencia del ABB simple, algunas variantes (como AVL) balancean cada nodo durante la inserción. La función siguiente muestra una versión sencilla que llama a balancearNodo al regresar de la recursión.
class ArbolBinarioOrdenado:
# ...
def insertar_balanceado(self, nodo, valor):
if nodo is None:
return Nodo(valor)
if valor < nodo.valor:
nodo.izquierdo = self.insertar_balanceado(nodo.izquierdo, valor)
else:
nodo.derecho = self.insertar_balanceado(nodo.derecho, valor)
return self.balancear_nodo(nodo)Cuando el árbol está muy degradado podemos rearmarlo tomando todos los valores, ordenándolos y montando un nuevo ABB balanceado.
class ArbolBinarioOrdenado:
# ...
def _guardar_inorden(self, nodo, destino):
if nodo is None:
return
self._guardar_inorden(nodo.izquierdo, destino)
destino.append(nodo.valor)
self._guardar_inorden(nodo.derecho, destino)
def reconstruir_balanceado(self):
valores = []
self._guardar_inorden(self.raiz, valores)
def _armar(valores, inicio, fin):
if inicio > fin:
return None
medio = (inicio + fin) // 2
nodo = Nodo(valores[medio])
nodo.izquierdo = _armar(valores, inicio, medio - 1)
nodo.derecho = _armar(valores, medio + 1, fin)
return nodo
self.raiz = _armar(valores, 0, len(valores) - 1)En la práctica combinamos ambas técnicas:
El archivo siguiente muestra una inserción balanceada estilo AVL y verifica que el inorden permanezca ordenado tras varias operaciones.
class Nodo:
def __init__(self, valor):
self.valor = valor
self.izquierdo = None
self.derecho = None
class ArbolBinarioOrdenado:
def __init__(self):
self.raiz = None
def altura(self, nodo=None):
def _altura(n):
if n is None:
return 0
return 1 + max(_altura(n.izquierdo), _altura(n.derecho))
nodo = self.raiz if nodo is None else nodo
return _altura(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 rotar_derecha(self, y):
if y is None or y.izquierdo is None:
return y
x = y.izquierdo
sub_derecho = x.derecho
x.derecho = y
y.izquierdo = sub_derecho
return x
def rotar_izquierda(self, x):
if x is None or x.derecho is None:
return x
y = x.derecho
sub_izquierdo = y.izquierdo
y.izquierdo = x
x.derecho = sub_izquierdo
return y
def balancear_nodo(self, nodo):
if nodo is None:
return None
balance = self.factor_balance(nodo)
if balance > 1:
if self.factor_balance(nodo.izquierdo) < 0:
nodo.izquierdo = self.rotar_izquierda(nodo.izquierdo)
return self.rotar_derecha(nodo)
if balance < -1:
if self.factor_balance(nodo.derecho) > 0:
nodo.derecho = self.rotar_derecha(nodo.derecho)
return self.rotar_izquierda(nodo)
return nodo
def insertar_balanceado(self, nodo, valor):
if nodo is None:
return Nodo(valor)
if valor < nodo.valor:
nodo.izquierdo = self.insertar_balanceado(nodo.izquierdo, valor)
else:
nodo.derecho = self.insertar_balanceado(nodo.derecho, valor)
return self.balancear_nodo(nodo)
def insertar(self, valor):
self.raiz = self.insertar_balanceado(self.raiz, valor)
return self.raiz
def imprimir_inorden(self, nodo=None):
def _inorden(n):
if n is None:
return
_inorden(n.izquierdo)
print(n.valor, end=" ")
_inorden(n.derecho)
nodo = self.raiz if nodo is None else nodo
_inorden(nodo)
if __name__ == "__main__":
arbol = ArbolBinarioOrdenado()
for valor in [30, 20, 40, 10, 25, 35, 50, 5, 27]:
arbol.insertar(valor)
print("Inorden tras inserciones balanceadas:")
arbol.imprimir_inorden()
print()
print("Altura final:", arbol.altura())