1. ¿Qué es un árbol AVL?

Un árbol AVL es un árbol binario de búsqueda (BST) auto‑balanceado. Cada nodo almacena una altura y la diferencia de alturas entre sus sub‑árboles izquierdo y derecho (factor de balance) nunca excede ±1. Gracias a este invariant, las operaciones de inserción, borrado y búsqueda se ejecutan en O(log n) en el peor caso.

• Ventajas: búsquedas rápidas, rendimiento predecible.
• Desventajas: mayor complejidad de código y coste extra de rotaciones.

2. Comparativa rápida con otras estructuras

3. Implementación paso a paso en Python 3.12+

El código está dividido en tres bloques claros: Node, AVLTree (lógica) y Demo (uso). Cada método incluye comentarios y type hints para mayor legibilidad.

3.1. Clase Node

class Node:
    """Representa un nodo del árbol AVL.
    Attributes
    ----------
    key: int | float | str
        Valor almacenado.
    left, right: Node | None
        Hijos izquierdo y derecho.
    height: int
        Altura del sub‑árbol cuyo nodo es raíz.
    """
    __slots__ = ("key", "left", "right", "height")
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # Un nodo hoja tiene altura 1

3.2. Clase AVLTree

class AVLTree:
    """Árbol AVL con inserción, borrado y búsqueda.
    Todas las operaciones mantienen el factor de balance en [-1, 1].
    """
    def __init__(self):
        self.root = None
    # ---------- Utilidades ----------
    def _height(self, node):
        return node.height if node else 0
    def _balance_factor(self, node):
        return self._height(node.left) - self._height(node.right) if node else 0
    def _update_height(self, node):
        node.height = 1 + max(self._height(node.left), self._height(node.right))
    # ---------- Rotaciones ----------
    def _rotate_right(self, y):
        x = y.left
        T2 = x.right
        # Rotación
        x.right = y
        y.left = T2
        # Actualizar alturas
        self._update_height(y)
        self._update_height(x)
        return x
    def _rotate_left(self, x):
        y = x.right
        T2 = y.left
        # Rotación
        y.left = x
        x.right = T2
        # Actualizar alturas
        self._update_height(x)
        self._update_height(y)
        return y
    # ---------- Inserción ----------
    def insert(self, key):
        self.root = self._insert(self.root, key)
    def _insert(self, node, key):
        if not node:
            return Node(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        else:
            # Duplicados no están permitidos en este ejemplo
            return node
        # Actualizar altura y balancear
        self._update_height(node)
        return self._rebalance(node)
    # ---------- Borrado ----------
    def delete(self, key):
        self.root = self._delete(self.root, key)
    def _delete(self, node, key):
        if not node:
            return node
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            # Nodo con un solo hijo o sin hijos
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            # Nodo con dos hijos: obtener el sucesor in‑order
            temp = self._min_value_node(node.right)
            node.key = temp.key
            node.right = self._delete(node.right, temp.key)
        # Actualizar altura y balancear
        self._update_height(node)
        return self._rebalance(node)
    def _min_value_node(self, node):
        current = node
        while current.left:
            current = current.left
        return current
    # ---------- Búsqueda ----------
    def search(self, key):
        return self._search(self.root, key)
    def _search(self, node, key):
        if not node:
            return False
        if key == node.key:
            return True
        return self._search(node.left, key) if key < node.key else self._search(node.right, key)
    # ---------- Rebalanceo ----------
    def _rebalance(self, node):
        balance = self._balance_factor(node)
        # Caso Izquierda‑Izquierda
        if balance > 1 and self._balance_factor(node.left) >= 0:
            return self._rotate_right(node)
        # Caso Izquierda‑Derecha
        if balance > 1 and self._balance_factor(node.left) < 0:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        # Caso Derecha‑Derecha
        if balance < -1 and self._balance_factor(node.right) <= 0:
            return self._rotate_left(node)
        # Caso Derecha‑Izquierda
        if balance < -1 and self._balance_factor(node.right) > 0:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)
        return node
    # ---------- Traversals (para depuración) ----------
    def inorder(self):
        return self._inorder(self.root, [])
    def _inorder(self, node, acc):
        if node:
            self._inorder(node.left, acc)
            acc.append(node.key)
            self._inorder(node.right, acc)
        return acc

3.3. Uso práctico (Demo)

if __name__ == "__main__":
    import random, time
    avl = AVLTree()
    data = random.sample(range(1, 1000), 200)  # 200 claves únicas
    start = time.perf_counter()
    for value in data:
        avl.insert(value)
    insert_time = time.perf_counter() - start
    print(f"Insertado 200 elementos en {insert_time:.6f}s")
    # Verificar búsqueda
    for _ in range(20):
        key = random.choice(data)
        assert avl.search(key)
    # Borrar algunos valores
    for key in data[:50]:
        avl.delete(key)
    print("In‑order después de borrados:", avl.inorder()[:10], "...")

El bloque anterior muestra cómo medir rendimiento y validar la integridad del árbol.

4. Buenas prácticas y consideraciones de rendimiento

• Usar __slots__ en la clase Node reduce la sobrecarga de memoria en árboles grandes.
• Evitar recursión profunda en entornos con límite bajo de pila (p.ej., CPython sys.setrecursionlimit). Para árboles con >10⁶ nodos, considerar una implementación iterativa.
• Persistencia: Si necesitas almacenar el árbol en disco, serializa con pickle o usa formatos como MessagePack y reconstruye la altura en tiempo de carga.
• Comparación con Red‑Black: AVL ofrece lecturas ligeramente más rápidas (mayor balance) a costa de inserciones/borrados más costosos. Elige AVL cuando la carga sea predominantemente de consultas.
• Profiling: Usa cProfile o pyinstrument para identificar cuellos de botella; las rotaciones son el punto crítico.

5. Depuración y troubleshooting

Pasos de diagnóstico:

1. Verifica que _update_height se invoque después de cada modificación.
2. Comprueba que _rebalance devuelva siempre el nodo raíz de la sub‑estructura.
3. Imprime el factor de balance de cada nodo con una función auxiliar:

   def _print_balance(self, node, depth=0):
       if node:
           self._print_balance(node.right, depth+1)
           print('   '*depth, f'{node.key} (h={node.height}, bf={self._balance_factor(node)})')
           self._print_balance(node.left, depth+1)

4. Si el problema persiste, revisa la lógica de los casos de rotación doble (Left‑Right y Right‑Left).

6. Extensiones y casos de uso reales

Los árboles AVL aparecen en:

• Índices de bases de datos embebidas (SQLite utiliza B‑Tree, pero la idea de balanceo es similar).
• Sistemas de archivos en memoria que requieren búsquedas rápidas (p.ej., memcached).
• Implementaciones de priority queues donde las prioridades cambian frecuentemente.

Ejemplo avanzado: AVL con claves compuestas (tupla (fecha, id)) para ordenar logs por timestamp y, en caso de empate, por identificador.

avl.insert((datetime.now(), uuid4()))

7. Compatibilidad, escalabilidad y futuro

La implementación mostrada funciona en cualquier versión de Python ≥3.8. Para CPython se beneficia de PyPy o Cython si el árbol supera los millones de nodos.

En entornos de micro‑servicios donde la latencia es crítica, considera exponer el árbol AVL mediante una API FastAPI y cachear resultados en Redis. La combinación permite:

• Lecturas O(log n) en memoria.
• Persistencia eventual mediante replicación de estado.

Con la llegada de WebAssembly, es posible ejecutar la lógica AVL en navegadores, habilitando estructuras de datos avanzadas del lado del cliente sin depender de servidores.