El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Árboles AVL

Siguiente ►
►

La lección anterior terminó con una medición incómoda: el índice de TaskFlow, construido con ids autoincrementales — el caso más común del mundo real —, degeneraba en una lista y sus O(log n) se evaporaban. El árbol AVL (por sus inventores, Adelson-Velskii y Landis, 1962) es un ABB que se niega a degenerar: tras cada inserción comprueba un número por nodo (el factor de equilibrio) y, si detecta desequilibrio, lo corrige con una rotación — una recolocación local de dos o tres nodos que restaura el equilibrio sin romper la propiedad de búsqueda. El resultado: altura O(log n) garantizada, llegue el dato que llegue y en el orden que llegue. En esta lección entenderás el factor de equilibrio, las cuatro rotaciones (LL, RR, LR, RL) con diagramas paso a paso, implementarás la inserción AVL completa y medirás la diferencia con el experimento exacto que hundió al ABB.

Contenido

  1. El problema, cuantificado: por qué el ABB no basta
  2. Factor de equilibrio: el chivato de cada nodo
  3. Las rotaciones simples: LL y RR
  4. Las rotaciones dobles: LR y RL
  5. Implementación: inserción AVL con rebalanceo recursivo
  6. La revancha: medir ABB vs AVL con ids ordenados
  7. Cuándo compensa un AVL (y qué usan las librerías)

El problema, cuantificado: por qué el ABB no basta

Recapitulemos la herida de 06-04 con números: insertar range(1023) en un ABB produce altura 1022; barajado, ~20; el ideal era 9. El problema no es el ABB como idea — es que su forma queda a merced del orden de llegada, y los datos reales llegan con orden (ids crecientes, fechas, contadores). Un índice cuyo rendimiento depende de la suerte no es un índice: es una lotería.

La idea del AVL: mantener un invariante de equilibrio además del de búsqueda. Concretamente:

En todo nodo, las alturas de sus dos subárboles difieren como máximo en 1.

No exige perfección (eso obligaría a reconstrucciones masivas); exige casi-equilibrio, que es barato de mantener y suficiente: se demuestra que un AVL con n nodos tiene altura menor que 1,45·log₂(n+2) — para el millón de tareas de la tabla de 06-02, altura ≤ 28 en vez de hasta 999 999. O(log n) con garantía matemática, no estadística.

Factor de equilibrio: el chivato de cada nodo

Para vigilar el invariante sin recalcular alturas a cada paso (eso sería O(n) por consulta), cada nodo guarda su altura como atributo, y definimos:

factor de equilibrio (FE) = altura(subárbol izquierdo) − altura(subárbol derecho)

FE Significado
0 Perfectamente equilibrado en este nodo
+1 La izquierda es un nivel más alta: aceptable
−1 La derecha es un nivel más alta: aceptable
+2 Demasiado cargado a la izquierda: rotar
−2 Demasiado cargado a la derecha: rotar

Insertando de uno en uno, el FE solo puede alcanzar ±2 (partíamos de ±1 como mucho y una inserción cambia las alturas en 1); nunca veremos un ±3. Por eso las correcciones son siempre locales y pequeñas.

graph TD
    A["10 (FE=+2) ⚠"] --> B["6 (FE=+1)"]
    A --> Z["(vacío)"]
    B --> C["3 (FE=0)"]
    B --> Y["(vacío)"]

Este árbol (insertar 10, 6, 3) ya viola el invariante en la raíz: izquierda de altura 1, derecha de altura −1 (vacía), FE = +2. En un ABB normal aquí no pasa nada y la degeneración echa a andar; el AVL, en cambio, actúa.

Las rotaciones simples: LL y RR

Una rotación reorganiza un nodo y uno de sus hijos de modo que el hijo sube, el padre baja, y — esto es lo crucial — el orden inorden no cambia, así que la propiedad de búsqueda sobrevive intacta. Hay cuatro casos de desequilibrio, nombrados por dónde cayó el nodo nuevo respecto al nodo desequilibrado: LL, RR, LR y RL.

Caso LL (left-left): FE = +2 y el exceso está en el subárbol izquierdo-izquierdo. Se corrige con una rotación a la derecha: el hijo izquierdo sube a raíz del subárbol, el antiguo padre pasa a ser su hijo derecho, y el subárbol B (los valores entre ambos) cambia de lado:

graph TD
    subgraph "Antes: FE(z)=+2, caso LL"
        Z((z)) --> Y((y))
        Z --> T4[T4]
        Y --> X((x))
        Y --> T3[T3]
        X --> T1[T1]
        X --> T2[T2]
    end
    subgraph "Después: rotación derecha sobre z"
        Y2((y)) --> X2((x))
        Y2 --> Z2((z))
        X2 --> T1b[T1]
        X2 --> T2b[T2]
        Z2 --> T3b[T3]
        Z2 --> T4b[T4]
    end

Comprueba el inorden en ambos: T1, x, T2, y, T3, z, T4. Idéntico — la búsqueda no se entera de nada, pero la altura del conjunto baja en 1. Con el ejemplo 10-6-3: z=10, y=6, x=3; tras rotar, el 6 es la raíz con el 3 y el 10 como hijos. Equilibrio restaurado con tres reasignaciones de referencias: O(1).

Caso RR es el espejo exacto (FE = −2, exceso en derecha-derecha; insertar 3, 6, 10 lo provoca): rotación a la izquierda, el hijo derecho sube. En código, ambas:

def rotar_derecha(z):
    """Caso LL. Devuelve la nueva raíz del subárbol (y)."""
    y = z.izquierdo
    t3 = y.derecho
    y.derecho = z          # el padre baja a hijo derecho
    z.izquierdo = t3       # y su antiguo subárbol derecho (T3) cambia de dueño
    actualizar_altura(z)   # z primero: ahora es el de abajo
    actualizar_altura(y)
    return y

def rotar_izquierda(z):
    """Caso RR. Espejo del anterior. Devuelve la nueva raíz (y)."""
    y = z.derecho
    t2 = y.izquierdo
    y.izquierdo = z
    z.derecho = t2
    actualizar_altura(z)
    actualizar_altura(y)
    return y

El traslado de t3 es el paso que la gente olvida: los valores de T3 están entre y y z (mayores que y, menores que z), y tras la rotación su sitio correcto es el hueco izquierdo de z. Y las alturas se actualizan de abajo arriba: primero z (ahora hijo), luego y (ahora raíz del subárbol).

Las rotaciones dobles: LR y RL

¿Y si el exceso está "en zigzag"? Insertar 10, 3, 6: el 10 tiene FE = +2, pero el nodo nuevo cayó en el subárbol izquierdo-derecho. Una sola rotación derecha no lo arregla (pruébalo en papel: el 3 subiría con FE = −2 — el desequilibrio solo cambia de lado). El caso LR necesita dos movimientos: primero una rotación izquierda sobre el hijo (convierte el zigzag en el caso LL) y después la rotación derecha de siempre sobre el nodo desequilibrado:

graph TD
    subgraph "1. Antes: caso LR"
        Z((10)) --> Y((3))
        Y --> X((6))
    end
    subgraph "2. Rotar izquierda sobre 3"
        Z2((10)) --> X2((6))
        X2 --> Y2((3))
    end
    subgraph "3. Rotar derecha sobre 10"
        X3((6)) --> Y3((3))
        X3 --> Z3((10))
    end

El nieto (6) acaba de raíz del subárbol, con su antiguo abuelo y su antiguo padre como hijos. El caso RL es el espejo (FE = −2 con el exceso en derecha-izquierda; insertar 3, 10, 6): rotación derecha sobre el hijo, luego izquierda sobre el nodo. Resumen de los cuatro casos:

Caso Detección Corrección
LL FE = +2 y FE(hijo izq.) ≥ 0 Rotación derecha
LR FE = +2 y FE(hijo izq.) < 0 Rot. izquierda sobre el hijo + rot. derecha
RR FE = −2 y FE(hijo der.) ≤ 0 Rotación izquierda
RL FE = −2 y FE(hijo der.) > 0 Rot. derecha sobre el hijo + rot. izquierda

Fíjate en que la detección es puramente aritmética: el FE del nodo dice el lado del problema, y el FE del hijo dice si es en línea (simple) o en zigzag (doble).

Implementación: inserción AVL con rebalanceo recursivo

Ensamblemos. La estrategia es la inserción recursiva del ABB con un paso extra al volver de cada llamada: actualizar la altura del nodo y, si su FE se ha salido de [−1, +1], aplicar la rotación del caso correspondiente. Como cada llamada devuelve la (quizá nueva) raíz de su subárbol, el patrón "reasignar al volver" que usamos en _borrar de 06-04 encaja perfecto:

class NodoAVL:
    def __init__(self, clave, valor):
        self.clave = clave
        self.valor = valor
        self.izquierdo = None
        self.derecho = None
        self.altura = 0                  # hoja recién nacida (convención de 06-02)

def altura_de(nodo):
    return nodo.altura if nodo else -1   # el subárbol vacío mide -1

def actualizar_altura(nodo):
    nodo.altura = 1 + max(altura_de(nodo.izquierdo), altura_de(nodo.derecho))

def factor_equilibrio(nodo):
    return altura_de(nodo.izquierdo) - altura_de(nodo.derecho)

class ArbolAVL:
    def __init__(self):
        self.raiz = None

    def insertar(self, clave, valor):
        self.raiz = self._insertar(self.raiz, clave, valor)

    def _insertar(self, nodo, clave, valor):
        # 1) Inserción ABB normal (recursiva)
        if nodo is None:
            return NodoAVL(clave, valor)
        if clave == nodo.clave:
            nodo.valor = valor
            return nodo
        elif clave < nodo.clave:
            nodo.izquierdo = self._insertar(nodo.izquierdo, clave, valor)
        else:
            nodo.derecho = self._insertar(nodo.derecho, clave, valor)

        # 2) Al VOLVER: actualizar altura y comprobar equilibrio
        actualizar_altura(nodo)
        fe = factor_equilibrio(nodo)

        # 3) Los cuatro casos
        if fe > 1 and factor_equilibrio(nodo.izquierdo) >= 0:   # LL
            return rotar_derecha(nodo)
        if fe > 1:                                              # LR
            nodo.izquierdo = rotar_izquierda(nodo.izquierdo)
            return rotar_derecha(nodo)
        if fe < -1 and factor_equilibrio(nodo.derecho) <= 0:    # RR
            return rotar_izquierda(nodo)
        if fe < -1:                                             # RL
            nodo.derecho = rotar_derecha(nodo.derecho)
            return rotar_izquierda(nodo)

        return nodo                       # equilibrado: sin cambios

    def buscar(self, clave):              # ¡idéntico al ABB!
        nodo = self.raiz
        while nodo is not None:
            if clave == nodo.clave:
                return nodo.valor
            nodo = nodo.izquierdo if clave < nodo.clave else nodo.derecho
        return None

Puntos finos, de arriba abajo:

  • Todo pasa al deshacer la recursión: la inserción baja hasta la hoja, y las actualizaciones de altura y las rotaciones suceden camino de vuelta, de la hoja hacia la raíz — justo la dirección en la que el desequilibrio se propaga.
  • Guardar la altura en el nodo hace que factor_equilibrio sea O(1); sin ella, cada comprobación costaría recorrer el subárbol.
  • Un teorema tranquilizador: en una inserción, una sola rotación (simple o doble) restaura el equilibrio de todo el árbol — una vez corregido el primer nodo desequilibrado, los ancestros recuperan su altura previa y no hace falta seguir. (El borrado AVL es menos amable: puede necesitar rotaciones en cascada hasta la raíz, sigue siendo O(log n); su implementación combina _borrar de 06-04 con este mismo rebalanceo y queda fuera del alcance de la lección.)
  • buscar (y en_orden, y rango...) son los mismos del ABB, sin tocar una coma: el AVL es un ABB. Solo cambia quién controla la forma.

Verifiquemos con la secuencia asesina:

avl = ArbolAVL()
for i in range(1, 8):
    avl.insertar(i, f"tarea {i}")

print(avl.raiz.clave)          # 4: ¡la raíz es la mediana, no el 1!
print(altura_de(avl.raiz))     # 2: el mínimo posible con 7 nodos

Insertando 1…7 en orden, el ABB daba altura 6; el AVL da 2, el árbol perfecto. Las rotaciones han ido recolocando: al insertar el 3, la cadena 1-2-3 rota y el 2 sube; al insertar 5, rota el subárbol del 3... El árbol se reconstruye solo, inserción a inserción, sin que el código cliente sepa nada.

La revancha: medir ABB vs AVL con ids ordenados

Repitamos el experimento exacto que condenó al ABB en 06-04 — 2 000 ids autoincrementales — más una búsqueda sobre el resultado:

import timeit

def construir_avl(claves):
    a = ArbolAVL()
    for c in claves:
        a.insertar(c, None)
    return a

ids = list(range(2000))

print(timeit.timeit(lambda: construir(ids), number=5))       # ABB:  ~4 s
print(timeit.timeit(lambda: construir_avl(ids), number=5))   # AVL:  ~0.06 s

abb, avl = construir(ids), construir_avl(ids)
print(timeit.timeit(lambda: abb.buscar(1999), number=10000)) # ~1.9 s  (recorre 2000 nodos)
print(timeit.timeit(lambda: avl.buscar(1999), number=10000)) # ~0.02 s (baja ~11 niveles)
print(altura_abb(abb), altura_de(avl.raiz))                  # 1999  vs  10

Los tiempos concretos variarán en tu máquina, pero la estructura del resultado no: construcción ~70 veces más rápida, búsqueda ~100 veces más rápida, altura 1999 contra 10. Y nota la letra pequeña justa: el AVL paga un sobrecoste constante por inserción (actualizar alturas, comprobar FE, rotar a veces) — con claves aleatorias el ABB simple puede incluso ganarle por poco. Lo que compra el AVL no es velocidad en el caso bueno: es la eliminación del caso malo.

Cuándo compensa un AVL (y qué usan las librerías)

¿Siempre AVL, entonces? Casi, pero con criterio:

  • Compensa cuando las búsquedas y consultas por rango dominan sobre las escrituras, o cuando no controlas el orden de llegada de las claves (o sí lo controlas: ¡y es ordenado!). El AVL es el más rígidamente equilibrado de los árboles auto-balanceados: altura mínima, búsquedas máximamente rápidas.
  • Se queda corto cuando hay muchísimas escrituras: su rigidez obliga a rotar con frecuencia. Para esas cargas existe el árbol rojo-negro, un primo que tolera algo más de desequilibrio (altura ≤ 2·log₂ n) a cambio de rotar menos; es la elección de las librerías estándar — el std::map de C++, el TreeMap de Java — precisamente por ese equilibrio entre lecturas y escrituras. No lo desarrollaremos: las ideas (invariante + rotaciones locales) son las mismas que acabas de aprender, cambia la contabilidad.
  • Python, por cierto, no trae un árbol equilibrado en la biblioteca estándar (su cultura resuelve casi todo con dict + sorted); en el ecosistema existen paquetes como sortedcontainers que cubren el hueco con otra técnica. Ahora entiendes exactamente qué agujero tapan.

Para TaskFlow, la decisión es clara: el índice (prioridad, id) de 06-04 recibe ids autoincrementales a diario — la carga que degenera al ABB. Cambiar ArbolBusqueda() por ArbolAVL() (misma interfaz: insertar, buscar...) le da a TaskFlow un índice ordenado que no se degrada nunca, reciba lo que reciba.

Errores Comunes y Consejos

  • Olvidar actualizar las alturas, o hacerlo en mal orden. Tras una rotación, primero la del nodo que bajó, después la del que subió (el de arriba depende del de abajo). Alturas desactualizadas → FE mentirosos → rotaciones donde no toca. Es el bug número uno de las implementaciones caseras.
  • Perder el subárbol del medio (T2/T3) al rotar. La rotación no es "intercambiar padre e hijo": el subárbol intermedio debe cambiar de progenitor. Si tu árbol pierde nodos tras rotar, es esto.
  • Tratar un caso zigzag con rotación simple. LR y RL necesitan la doble; la simple deja FE = ∓2 al otro lado y, con mala suerte, un bucle de rotaciones estériles. La detección correcta mira el FE del hijo.
  • Olvidar reasignar el resultado: self.raiz = self._insertar(...) y nodo.izquierdo = rotar_izquierda(...). Las rotaciones devuelven la nueva raíz del subárbol; ignorar el retorno deja referencias apuntando al nodo que ya no es raíz.
  • Consejo de verificación: tras cada tanda de inserciones en tus pruebas, comprueba dos invariantes: el inorden sale ordenado (propiedad ABB intacta) y todos los FE están en {−1, 0, +1} (equilibrio). Un test de diez líneas que caza el 95 % de los errores de AVL.

Ejercicios

Ejercicio 1: la traza de las rotaciones

Sin ejecutar código, dibuja el AVL tras insertar, en este orden, las claves 30, 20, 10, 25, 27. Indica qué caso (LL, RR, LR, RL) se dispara en cada rotación y sobre qué nodo. Luego verifícalo con código imprimiendo el inorden y la raíz.

Ejercicio 2: auditor de equilibrio

Escribe es_avl_valido(nodo) que devuelva True si todos los FE del árbol están en {−1, 0, +1}, calculando las alturas por su cuenta (sin fiarse del atributo altura, que es precisamente lo que podría estar mal). Pruébalo sobre el AVL de 1…7 y sobre un ABB degenerado.

Ejercicio 3: el índice indestructible de TaskFlow

Reconstruye el índice (prioridad, id) de 06-04 sobre ArbolAVL, insertando 30 tareas con ids 1…30 y prioridades (i % 3) + 1. Comprueba: (a) que la altura es ≤ 1,45·log₂(32) ≈ 7; (b) que un inorden filtrado devuelve las tareas de prioridad 1 ordenadas por id. (Si añadiste rango al AVL copiándolo del ABB, mejor aún: úsalo.)

Soluciones

Solución 1

Paso a paso:

  1. 30, 20: sin problemas (FE(30) = +1).
  2. 10: cadena 30-20-10, FE(30) = +2 con exceso izquierda-izquierda → LL, rotación derecha sobre 30. Queda 20 como raíz, hijos 10 y 30.
  3. 25: baja a hijo izquierdo de 30. FE(20) = −1, FE(30) = +1: todo en rango, sin rotación.
  4. 27: baja bajo 25, a su derecha. Ahora FE(30) = +2 y el exceso está en izquierda-derecha → LR sobre 30: rotación izquierda sobre 25 (el 27 sube) y derecha sobre 30. El subárbol queda 27 con hijos 25 y 30.

Árbol final: raíz 20, izquierda 10, derecha 27, y bajo 27 los nodos 25 y 30. Verificación:

avl = ArbolAVL()
for c in [30, 20, 10, 25, 27]:
    avl.insertar(c, None)
print(avl.raiz.clave)                        # 20
print(avl.raiz.derecho.clave)                # 27
# inorden: [10, 20, 25, 27, 30] — ordenado, propiedad intacta

Comentario: el paso 4 es el que separa a quien entiende el AVL de quien lo memoriza — la primera intuición ("rotar derecha sobre 30 y ya") deja el árbol igual de desequilibrado. Dibuja siempre el FE del hijo antes de decidir.

Solución 2

def _altura_y_validez(nodo):
    """Devuelve (altura real, es_valido) del subárbol, en una sola pasada."""
    if nodo is None:
        return -1, True
    alt_izq, ok_izq = _altura_y_validez(nodo.izquierdo)
    alt_der, ok_der = _altura_y_validez(nodo.derecho)
    fe = alt_izq - alt_der
    return 1 + max(alt_izq, alt_der), ok_izq and ok_der and abs(fe) <= 1

def es_avl_valido(nodo):
    return _altura_y_validez(nodo)[1]

print(es_avl_valido(avl.raiz))          # True
print(es_avl_valido(construir(list(range(10))).raiz))   # False (ABB degenerado)

Comentario: la función devuelve dos cosas a la vez (altura y veredicto) para que la pasada sea O(n) — la versión ingenua que llama a altura() en cada nodo es O(n²), exactamente la trampa de rendimiento que el atributo altura del AVL evita en producción. Es un postorden puro: la información (alturas) fluye de hijos a padres, como las horas acumuladas de 06-03. Este auditor es el test de diez líneas del consejo final; el auditor gemelo de la propiedad de búsqueda cae en 06-08.

Solución 3

import math

indice = ArbolAVL()
for i in range(1, 31):
    tarea = {"id": i, "titulo": f"Tarea {i}", "prioridad": (i % 3) + 1,
             "estado": "pendiente"}
    indice.insertar((tarea["prioridad"], i), tarea)

# (a) altura garantizada
print(altura_de(indice.raiz))                      # 5 o 6 según la secuencia
print(1.45 * math.log2(32))                        # 7.25: dentro de la garantía

# (b) prioridad 1, ordenadas por id (inorden + filtro)
resultado = []
def en_orden(nodo):
    if nodo is None:
        return
    en_orden(nodo.izquierdo)
    resultado.append(nodo)
    en_orden(nodo.derecho)
en_orden(indice.raiz)
prio1 = [n.valor["id"] for n in resultado if n.clave[0] == 1]
print(prio1)     # [3, 6, 9, 12, 15, 18, 21, 24, 27, 30] — ascendente, garantizado

Comentario: las claves (prioridad, id) llegan con id estrictamente creciente — dentro de cada prioridad, la secuencia que degeneraba al ABB. El AVL ni se inmuta: altura 5-6 con 30 nodos, dentro de la cota 1,45·log₂(n+2). Y el inorden sale agrupado por prioridad y por id dentro de cada grupo, porque así comparan las tuplas. Este es, ya en su versión definitiva, el índice ordenado de TaskFlow: la interfaz de 06-04, la garantía de 06-05.

Conclusión

El AVL cierra la vulnerabilidad que el ABB traía de serie: guardando una altura por nodo, vigilando el factor de equilibrio y corrigiendo con las cuatro rotaciones (LL y RR simples, LR y RL dobles — todas O(1), todas preservando el inorden), garantiza altura O(log n) pase lo que pase — y lo has comprobado con la misma secuencia de ids ordenados que hundía al ABB: altura 10 donde había 1999. TaskFlow tiene por fin un índice ordenado indestructible, y de regalo conoces el mapa del territorio: rojo-negro cuando las escrituras aprietan (la elección de las librerías), y el porqué del hueco en la biblioteca estándar de Python. Pero toda esta lección ha dado por hecho algo: que el árbol entero vive en RAM, donde saltar de un nodo a otro es gratis. ¿Y si las tareas de TaskFlow son millones y viven en disco, donde cada acceso se paga a precio de oro y por bloques? Ahí los árboles binarios — incluso perfectos — hacen demasiados saltos, y hace falta un árbol más bajo y mucho más ancho: el árbol B, el que sostiene las bases de datos, y la próxima lección.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados