Árboles AVL

De qué trata este capítulo

El capítulo anterior terminó con un cliffhanger: un árbol binario de búsqueda es un contenedor ordenado maravilloso hasta que la entrada ordenada lo degenera en una lista ligada, y a partir de ahí toda operación es O(n). El árbol AVL es la solución, y es el primer árbol de búsqueda auto-balanceado que se inventó. Es un BST común y corriente más una regla: después de cada inserción, revisa si algún nodo quedó demasiado desbalanceado y, si es así, restaura el balance con una rotación — un reacomodo en tiempo constante de un puñado de apuntadores. Esa sola disciplina garantiza que la altura se mantenga en O(log n) para cualquier orden de inserción, y convierte al frágil BST en uno que sí puedes poner en producción. En este capítulo lo construimos, lo vemos rebalancearse en tiempo real con entrada ordenada y medimos la diferencia de más de 100× que hace el balance.

Un poco de historia

El árbol AVL lleva el nombre de sus inventores, los matemáticos soviéticos Georgy Adelson-Velsky y Evgenii Landis, que lo publicaron en 1962 — las iniciales A-V-L son suyas. Fue la primera estructura de datos en garantizar altura logarítmica para un árbol de búsqueda dinámico, y apareció casi de inmediato después del propio árbol binario de búsqueda, porque el problema del balance saltó a la vista en cuanto la gente empezó a insertar datos ordenados. Su idea clave — mantener un invariante de balance de altura en cada nodo y repararlo con rotaciones locales — fundó toda una familia de árboles balanceados, incluyendo el árbol red-black del siguiente capítulo y el árbol B que indexa bases de datos. Sesenta años después, "factor de balance" y "rotación" siguen siendo el vocabulario, y el árbol AVL se sigue enseñando primero, porque su regla de balance es la más estricta y la más clara de la familia.

La intuición

Cada nodo AVL recuerda la altura de su subárbol, y de ahí calculas su factor de balance: la altura de su subárbol izquierdo menos la del derecho. En un árbol balanceado esa diferencia siempre es -1, 0 o +1. En el momento en que una inserción hace que el factor de balance de algún nodo llegue a +2 o -2 — un lado dos niveles más alto que el otro — el árbol lo arregla antes de regresar.

El arreglo es una rotación. Imagina un nodo que quedó cargado a la izquierda porque seguiste insertando valores más chicos. Una rotación a la derecha sube a su hijo izquierdo a tomar su lugar y empuja al nodo hacia abajo para volverlo el hijo derecho de ese hijo — el árbol se inclina para el otro lado, los dos lados se emparejan y, como un hijo izquierdo siempre es menor y un hijo derecho siempre mayor, el orden de búsqueda se conserva por completo. Solo se mueven tres apuntadores, así que una rotación es O(1). En total hay cuatro casos: los simples, cargado a la izquierda y cargado a la derecha, necesitan una sola rotación, y dos casos "zig-zag" (cargado a la izquierda pero con el desbalance en el subárbol derecho del hijo izquierdo, y su espejo) necesitan una rotación doble — primero rotas al hijo para convertirlo en un caso simple, luego rotas el nodo. Inserta, después regresa subiendo y rota donde haga falta, y la altura nunca puede pasar de aproximadamente 1.44·log₂ n.

Complejidad: cómo escala

Como el invariante de balance limita la altura a $O(\log n)$ — con precisión, a lo más alrededor de $1.44\log_2 n$ — toda operación que es O(altura) se vuelve O(log n) garantizado, no solo en promedio. Búsqueda, inserción, eliminación: todas $O(\log n)$, en el peor caso, para cualquier entrada. Inserción y eliminación solo suman O(log n) de trabajo de rebalanceo encima de la búsqueda, ya que cada una hace a lo más una cantidad constante de rotación por nivel al regresar. Las dos gráficas cuentan la historia contra el BST desbalanceado del capítulo anterior, ambos alimentados con entrada ordenada. Los tiempos:

Y la altura que lo provoca — la línea del AVL apenas sube mientras la del BST simple trepa linealmente, porque la entrada ordenada lo construye como una cadena recta:

Con 8000 inserciones ordenadas el árbol AVL se construyó en 20 ms contra los 2130 ms del BST simple — 104 veces más rápido. Y con 100000 nodos, la altura del árbol AVL fue 17 (justo en log₂ n ≈ 16.6) mientras que la del BST simple fue 100000: una línea recta de cien mil nodos contra un árbol frondoso de diecisiete niveles. Esa es la diferencia que hace el balance.

En qué es bueno y en qué no

El árbol AVL es la estructura correcta cuando necesitas un contenedor ordenado con operaciones logarítmicas garantizadas — iteración ordenada, rangos, mínimo, máximo, sucesor — y no puedes descartar entrada ordenada o adversarial (que normalmente no puedes). Es el BST vuelto seguro: todo el poder de consultas ordenadas del capítulo anterior, sin la degeneración. Su balance estricto también significa que es un poco más bajito que árboles balanceados más laxos, así que las búsquedas son un pelín más rápidas, lo que lo hace buena opción para cargas de trabajo con muchas lecturas.

Su costo es la otra cara de esa rigidez. Como insiste en el factor de balance de ±1, rota más seguido en inserciones y eliminaciones que un árbol red-black — el red-black (siguiente capítulo) acepta un balance más laxo para rebalancear menos, cambiando un árbol un poco más alto por actualizaciones más baratas. Así que para cargas con muchas actualizaciones, los árboles red-black suelen ganar, y por eso son ellos, y no los AVL, los que usan la mayoría de las librerías estándar para sus maps ordenados. AVL es el más puro y rígidamente balanceado de la familia; red-black es el compromiso pragmático. Los dos le ganan a un BST desbalanceado por los márgenes de arriba.

Los datos, o las entradas

Tanto la gráfica del duelo como la de altura usan entrada ordenada — 0, 1, 2, … — porque ese es el peor caso que destruye a un BST simple y la demostración más clara de que el AVL lo sobrevive. La animación inserta los siete valores del 1 al 7 en orden, la misma secuencia ordenada, para que veas al árbol rotarse a sí mismo hasta quedar plano en lugar de crecer como cadena.

Constrúyelo, una función a la vez

Las dos rotaciones son el mecanismo — cada una mueve tres apuntadores y recalcula dos alturas, preservando el orden:

def _rotate_right(y):
    """Right rotation: y's left child x rises to the top of this subtree and y sinks
    to become x's right child; x's old right subtree reattaches under y. Only three
    pointers move, heights are recomputed, and — crucially — the BST ordering is
    unchanged, because everything stays on its correct side of every value."""
    x = y.left
    y.left = x.right
    x.right = y
    _update(y)
    _update(x)
    return x


def _rotate_left(x):
    """Left rotation — the exact mirror image, for a right-heavy subtree."""
    y = x.right
    x.right = y.left
    y.left = x
    _update(x)
    _update(y)
    return y

La inserción es una inserción normal de BST con una sola adición: al regresar de la recursión, actualiza alturas y rebalancea:

def insert(self, value, rot=None):
    """O(log n) GUARANTEED: insert like a normal BST, then on the way back up
    update heights and rebalance. Because the recursion returns through every
    ancestor, each one is checked and fixed, and at most one rotation (or double
    rotation) is ever needed to restore balance after an insert."""
    self.root = self._insert(self.root, value, rot)

def _insert(self, node, value, rot):
    if node is None:
        self._n += 1
        return Node(value)
    if value < node.value:
        node.left = self._insert(node.left, value, rot)
    elif value > node.value:
        node.right = self._insert(node.right, value, rot)
    else:
        return node
    _update(node)
    return self._rebalance(node, rot)

Y el rebalanceo es la decisión de cuatro casos — rotación simple para los casos simples, doble para los zig-zags:

def _rebalance(self, node, rot):
    """The four cases. If the node is left-heavy and its left child is right-heavy,
    that's the left-right case: rotate the child left first, turning it into the
    simple left-left case, then rotate the node right. Right-heavy is the mirror.
    A single or double rotation always suffices."""
    bf = _balance(node)
    if bf > 1:                          # left-heavy
        if _balance(node.left) < 0:     # left-right → reduce to left-left
            node.left = _rotate_left(node.left)
        if rot is not None:
            rot.append(node.value)
        return _rotate_right(node)
    if bf < -1:                         # right-heavy
        if _balance(node.right) > 0:    # right-left → reduce to right-right
            node.right = _rotate_right(node.right)
        if rot is not None:
            rot.append(node.value)
        return _rotate_left(node)
    return node

Míralo funcionar

Aquí está el árbol AVL alimentado con la misma entrada exacta que destruyó al BST simple del capítulo anterior: 1, 2, 3, 4, 5, 6, 7 en orden. Verde es un nodo recién insertado; naranja marca un nodo donde acaba de dispararse una rotación para restaurar el balance. Ve paso a paso y observa qué pasa donde el BST simple creó una cadena: inserta 1, 2 — todo bien; inserta 3 y el árbol se inclina a la derecha, así que rota y el 2 se vuelve la raíz; sigue avanzando y cada par de inserciones dispara otra rotación que dobla la cadena creciente de vuelta a una forma balanceada. Siete inserciones ordenadas que habrían construido una lista ligada de altura 7 producen, en cambio, un árbol perfectamente balanceado de altura 3:

El código completo

Las dos versiones en un solo lugar — cámbiate entre ellas. La pestaña desde cero es el árbol AVL, sus rotaciones y su rebalanceo. La pestaña de librería es el BST simple desbalanceado del capítulo anterior — la misma inserción menos las rotaciones — conservado como línea base, para que veas que la única diferencia entre una estructura que se degrada a O(n) y una que garantiza O(log n) son esas pocas líneas de rebalanceo. (El equivalente real en librería es el paquete de terceros sortedcontainers.)

"""The AVL tree — a binary search tree that keeps itself balanced, so its height stays
O(log n) no matter the insertion order, and every operation is guaranteed O(log n).

It's an ordinary BST plus one discipline: after every insert, walk back up to the root
and, wherever a node has become too lopsided (its two subtrees differ in height by more
than one), fix it with a ROTATION — a local rearrangement of a few pointers that
rebalances the subtree while preserving the search-tree ordering. That's the whole idea,
and it's what turns the previous chapter's fragile BST into one you can actually ship.
"""


class Node:
    __slots__ = ("value", "left", "right", "height")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1


def _h(node):
    return node.height if node else 0


def _balance(node):
    """The balance factor: height of the left subtree minus the right. An AVL tree
    keeps this in {-1, 0, +1} at every node; anything beyond means rebalance."""
    return _h(node.left) - _h(node.right) if node else 0


def _update(node):
    node.height = 1 + max(_h(node.left), _h(node.right))


# region: rotations
def _rotate_right(y):
    """Right rotation: y's left child x rises to the top of this subtree and y sinks
    to become x's right child; x's old right subtree reattaches under y. Only three
    pointers move, heights are recomputed, and — crucially — the BST ordering is
    unchanged, because everything stays on its correct side of every value."""
    x = y.left
    y.left = x.right
    x.right = y
    _update(y)
    _update(x)
    return x


def _rotate_left(x):
    """Left rotation — the exact mirror image, for a right-heavy subtree."""
    y = x.right
    x.right = y.left
    y.left = x
    _update(x)
    _update(y)
    return y
# endregion


class AVLTree:
    def __init__(self):
        self.root = None
        self._n = 0

    # region: insert
    def insert(self, value, rot=None):
        """O(log n) GUARANTEED: insert like a normal BST, then on the way back up
        update heights and rebalance. Because the recursion returns through every
        ancestor, each one is checked and fixed, and at most one rotation (or double
        rotation) is ever needed to restore balance after an insert."""
        self.root = self._insert(self.root, value, rot)

    def _insert(self, node, value, rot):
        if node is None:
            self._n += 1
            return Node(value)
        if value < node.value:
            node.left = self._insert(node.left, value, rot)
        elif value > node.value:
            node.right = self._insert(node.right, value, rot)
        else:
            return node
        _update(node)
        return self._rebalance(node, rot)
    # endregion

    # region: rebalance
    def _rebalance(self, node, rot):
        """The four cases. If the node is left-heavy and its left child is right-heavy,
        that's the left-right case: rotate the child left first, turning it into the
        simple left-left case, then rotate the node right. Right-heavy is the mirror.
        A single or double rotation always suffices."""
        bf = _balance(node)
        if bf > 1:                          # left-heavy
            if _balance(node.left) < 0:     # left-right → reduce to left-left
                node.left = _rotate_left(node.left)
            if rot is not None:
                rot.append(node.value)
            return _rotate_right(node)
        if bf < -1:                         # right-heavy
            if _balance(node.right) > 0:    # right-left → reduce to right-right
                node.right = _rotate_right(node.right)
            if rot is not None:
                rot.append(node.value)
            return _rotate_left(node)
        return node
    # endregion

    def __contains__(self, value):
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

    def __len__(self):
        return self._n

    def height(self):
        return _h(self.root)

    def inorder(self):
        out = []

        def rec(node):
            if node is not None:
                rec(node.left)
                out.append(node.value)
                rec(node.right)

        rec(self.root)
        return out

"""Python's standard library has no balanced BST; the third-party
`sortedcontainers.SortedList` is what you'd use in practice (it's actually a list of
lists, not a tree, but offers the same O(log n) ordered operations). So the meaningful
comparison here is against the structure AVL improves on — last chapter's UNBALANCED
BST — to show that self-balancing turns the sorted-input catastrophe back into O(log n).

That plain BST is included below as the reference baseline.
"""


# region: plain_bst
class PlainBSTNode:
    __slots__ = ("value", "left", "right")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class PlainBST:
    """An ordinary binary search tree with NO balancing — the same insert as the AVL
    tree, minus the rotations. On sorted input it degenerates into a linked list, which
    is exactly the O(n)-per-operation disaster the AVL tree's rotations prevent."""

    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return PlainBSTNode(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def __contains__(self, value):
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False
# endregion

Desde cero contra la librería

Este es el raro duelo donde el código desde cero no compite contra una librería en C sino contra su propio hermano desbalanceado — y le gana por dos órdenes de magnitud en la entrada que importa. 104× más rápido con 8000 inserciones ordenadas, y la brecha crece cuadráticamente, porque el BST simple está haciendo trabajo O(n²) frente al O(n log n) del AVL. La gráfica de altura deja la causa al descubierto: 17 contra 100000. Lo impactante es lo poco código que compra eso: el árbol AVL es el BST más el seguimiento de alturas y una docena de líneas de rotación. Esa es toda la lección de los árboles balanceados — una reparación pequeña, local y en tiempo constante, aplicada de forma consistente, convierte una estructura con un peor caso catastrófico en una con una garantía a prueba de balas. Aun así no escribirías esto a mano en Python (usa sortedcontainers), pero ahora sabes exactamente qué cuesta y qué te da estar "balanceado".

Dónde te lo vas a topar de verdad

Los árboles AVL corren donde sea que datos ordenados necesiten actualizaciones y búsquedas garantizadamente rápidas. Son una opción común en índices en memoria de bases de datos y sistemas de archivos, en almacenes clave-valor en memoria que necesitan consultas por rango, y en cualquier map ordenado donde dominen las búsquedas. Su primo cercano, el árbol red-black, mueve std::map/std::set en C++, TreeMap en Java, y el scheduler y el manejo de memoria del kernel de Linux. Y la rotación — el movimiento de rebalanceo local en O(1) que acabas de construir — es la operación fundamental de toda la familia de árboles balanceados; una vez que la entiendes aquí, los árboles red-black, los splay trees y los treaps son variaciones sobre dónde y cuándo aplicarla.

Puntos clave

Un árbol AVL es un árbol binario de búsqueda que mantiene un factor de balance de ±1 en cada nodo, reparando cualquier violación después de una inserción o eliminación con una rotación O(1), lo que garantiza que la altura se quede alrededor de $1.44\log_2 n$ y que toda operación se quede en $O(\log n)$ para cualquier entrada. Es el BST con su falla fatal eliminada, al costo modesto de llevar el registro de las alturas y rotar — 104× más rápido que la versión desbalanceada en la entrada ordenada que importa.

El siguiente capítulo es su hermano más relajado. El árbol red-black garantiza el mismo $O(\log n)$ pero con una regla de balance más laxa impuesta mediante colores de nodo, así que rota menos en las actualizaciones — y por eso, a pesar de la ventaja inicial y el balance más apretado del AVL, el árbol red-black es el que está escondido dentro de la mayoría de los maps ordenados de las librerías estándar.