Árboles rojo-negro

Lo que cubre este capítulo

El árbol rojo-negro es el árbol de búsqueda balanceado que en realidad ya estás usando, casi siempre sin saberlo: es lo que vive dentro de std::map, del TreeMap de Java y del scheduler del kernel de Linux. Igual que el árbol AVL garantiza O(log n), pero impone el balance de una forma más astuta: pinta cada nodo de rojo o negro y obedece cuatro reglas de coloreo que, juntas, mantienen el camino más largo de la raíz a una hoja en a lo más el doble del más corto. Esa garantía más relajada significa que se rebalancea con menos frecuencia que un AVL, que es exactamente por lo que las librerías lo prefieren para mapas ordenados de propósito general. Este capítulo construye la inserción usando la famosa formulación funcional compacta de Chris Okasaki —una sola función de balanceo, cuatro casos simétricos— y muestra por qué "rojo-negro" y "balanceado" significan lo mismo.

Un poco de historia

El árbol rojo-negro nació de una idea de Rudolf Bayer, quien en 1972 describió los "árboles B binarios simétricos": una manera de representar un árbol B (la estructura de bases de datos de un capítulo posterior) como un árbol binario. En 1978 Leo Guibas y Robert Sedgewick reformularon la idea de Bayer con el coloreo rojo/negro y las cuatro reglas que usamos hoy, y el nombre se quedó. La elección de los colores fue, según el propio relato posterior de Guibas y Sedgewick, en parte porque una impresora láser de dos colores que tenían podía imprimir bien el rojo y el negro. En 1999 Chris Okasaki publicó la inserción funcional que usa este capítulo, colapsando el análisis de casos —célebre por lo latoso— en una sola y elegante función balance: una pequeña obra maestra que volvió enseñables a los árboles rojo-negro. El verdadero triunfo de la estructura, eso sí, es su adopción: se convirtió en la implementación de mapa ordenado preferida en todo el mundo del software, el árbol balanceado que corre calladito debajo de cantidades enormes de código.

La intuición

Piensa en los colores como un presupuesto de balance. Las reglas —raíz negra, nunca dos rojos seguidos, y todo camino de la raíz a una hoja cruzando el mismo número de nodos negros— tienen una consecuencia combinada: como todas las alturas negras son iguales y los rojos no se pueden apilar, el camino más largo (que alterna rojo y negro) puede ser a lo más el doble del más corto (todo negro). El doble alcanza para mantener la altura en O(log n), y es más relajado que el "difieren en a lo más uno" del AVL, que es justo el punto: una regla más relajada se viola menos seguido, así que reparas menos seguido.

La inserción funciona agregando el nodo nuevo en rojo. ¿Por qué rojo? Porque un nodo rojo tiene la misma altura negra que no tener nodo alguno, así que insertar uno nunca puede romper la regla 4 (alturas negras iguales); solo puede romper la regla 3 (nunca dos rojos seguidos), si el padre del nuevo nodo rojo también es rojo. Arreglar esa violación rojo-rojo es el trabajo de la función balance, y aquí está la idea de Okasaki: en cada una de las cuatro formas en que se puede acomodar una violación rojo-rojo, la reparación es la misma — reescribir el clustercito como un abuelo rojo con dos hijos negros. Esa única reescritura empuja lo rojo un nivel hacia arriba, donde podría crear una nueva violación rojo-rojo con su padre, que el siguiente balance de arriba resuelve, y así hasta la raíz, que simplemente se fuerza a negra al final. Una sola regla, aplicada de regreso hacia arriba, balancea el árbol entero.

Complejidad: cómo escala

Las cuatro reglas acotan la altura en $2\log_2(n+1)$, así que toda operación es $O(\log n)$ garantizado —búsqueda, inserción, eliminación— para cualquier entrada, igualito que AVL. Lo que cambia es la constante en las actualizaciones: una inserción rojo-negro hace a lo más dos rotaciones (más algo de recoloreo), mientras que AVL puede rotar en cada nivel; empíricamente los árboles rojo-negro rotan notablemente menos. El trato se nota en la altura. Contra el BST desbalanceado con entrada ordenada, el árbol rojo-negro se mantiene plano donde el simple se va a cuadrático:

Y la altura se queda cómodamente por debajo de su cota, aunque es un toque más alta de lo que sería un AVL, que es el balance más relajado hecho visible:

Con 8000 inserciones ordenadas el árbol rojo-negro se construyó en 32 ms contra los 2179 ms del BST simple: 68× más rápido. Y con 100000 nodos su altura fue de 22, debajo de la cota de 33 y solo un poquito arriba de los 17 del AVL del capítulo pasado. Esa diferencia de cinco niveles es el precio de rebalancear menos seguido, y para la mayoría de las cargas de trabajo es un precio que vale la pena pagar.

En qué es bueno y en qué no

El árbol rojo-negro es el default correcto para un mapa o conjunto ordenado. Te da todo el poder de consultas ordenadas —iteración en orden, rangos, mínimo, máximo, sucesor— con O(log n) garantizado, y maneja inserciones y eliminaciones barato porque su regla de balance relajada se dispara pocas veces. Ese equilibrio entre garantías y bajo costo de actualización es la razón de que sea él, y no el AVL, la elección de la librería estándar en casi todos lados. Si echas mano de un TreeMap, un std::set o un diccionario ordenado en un lenguaje de sistemas, estás usando uno.

Donde no es ideal es en el mismo lugar donde ningún BST balanceado lo es: para pura membresía sin consultas ordenadas, el O(1) de una hash table le gana; y para cargas dominadas por lecturas, donde las búsquedas superan por mucho a las actualizaciones, el balance más estricto de un AVL (árbol más corto) puede sacarle ventaja. La eliminación también es genuinamente enredada —más que la inserción—, y esa es una de las razones por las que la formulación funcional de aquí se enfoca en la inserción. Pero como contenedor ordenado de propósito general, el árbol rojo-negro es el ganador pragmático, y su ubicuidad es la prueba.

Los datos, o las entradas

Ambas gráficas se alimentan de entrada ordenada, el peor caso para un BST simple y la prueba más clara de que el balanceo rojo-negro funciona. La animación inserta del 1 al 7 en orden y colorea cada nodo según su regla, para que puedas ver cómo los nodos rojos y negros se reacomodan para mantener el árbol corto.

Constrúyelo, una función a la vez

El corazón de todo es el balance de Okasaki: la única función que repara las cuatro configuraciones rojo-rojo dejándolas en la misma forma balanceada y recoloreada:

def _balance(color, value, left, right):
    """Okasaki's balance. Whenever a BLACK node has a red child that itself has a red
    child — a red-red violation, in any of four configurations — rewrite that little
    three-node cluster into a red parent with two black children. The same rebalanced
    shape results from all four cases; only which node ends up on top differs. This one
    rule, applied on the way back up, is the entire rebalancing logic."""
    if color == BLACK:
        if _red(left) and _red(left.left):          # left-left
            return Node(RED, left.value,
                        Node(BLACK, left.left.value, left.left.left, left.left.right),
                        Node(BLACK, value, left.right, right))
        if _red(left) and _red(left.right):         # left-right
            return Node(RED, left.right.value,
                        Node(BLACK, left.value, left.left, left.right.left),
                        Node(BLACK, value, left.right.right, right))
        if _red(right) and _red(right.left):        # right-left
            return Node(RED, right.left.value,
                        Node(BLACK, value, left, right.left.left),
                        Node(BLACK, right.value, right.left.right, right.right))
        if _red(right) and _red(right.right):       # right-right
            return Node(RED, right.value,
                        Node(BLACK, value, left, right.left),
                        Node(BLACK, right.right.value, right.right.left, right.right.right))
    return Node(color, value, left, right)

Y la inserción es casi trivial encima de eso: agrega el nodo en rojo, balancea de regreso hacia arriba, fuerza la raíz a negra:

def insert(self, value):
    """Insert the new node RED (adding a red node can't change any black-height,
    so rule 4 stays intact), fix any red-red violation on the way back up with
    `balance`, and finally force the root black. That's the whole insert — the
    recoloring keeps the height within 2·log₂(n+1)."""
    inserted = [False]

    def ins(node):
        if node is None:
            inserted[0] = True
            return Node(RED, value, None, None)
        if value < node.value:
            return _balance(node.color, node.value, ins(node.left), node.right)
        if value > node.value:
            return _balance(node.color, node.value, node.left, ins(node.right))
        return node

    self.root = ins(self.root)
    self.root.color = BLACK
    if inserted[0]:
        self._n += 1

Míralo funcionar

Aquí está un árbol rojo-negro construido a partir de la secuencia ordenada del 1 al 7, con cada nodo coloreado según las reglas: rojo o negro. Recórrelo paso a paso y observa cómo los colores hacen el balanceo: los nodos nuevos llegan en rojo y, cuando se formaría una violación rojo-rojo, el árbol recolorea y reestructura para empujar lo rojo hacia arriba y mantener igual la cuenta de negros en cada camino. Fíjate que nunca hay dos nodos rojos seguidos, que la raíz siempre es negra y que el árbol jamás se convierte en la cadena que un BST simple armaría con esta misma entrada. Los colores están haciendo el mismo trabajo que hacían los factores de balance de AVL, nada más que con una regla más relajada y barata:

El código completo

Ambas versiones en un solo lugar: cambia entre ellas. La pestaña desde cero es el árbol rojo-negro y el balance de Okasaki. La pestaña de librería es el BST simple desbalanceado —la línea base que degenera con entrada ordenada— porque Python no expone un árbol rojo-negro directamente (los mapas ordenados de C++ y Java son árboles rojo-negro en C; en Python usarías el paquete de terceros sortedcontainers).

"""The red-black tree — the balanced binary search tree that actually runs inside most
standard-library ordered maps. It guarantees O(log n) like the AVL tree, but enforces
balance with a looser rule based on node COLORS, so it rotates less on updates.

Every node is red or black, and four rules together keep the tree from getting more
than twice as tall as a perfectly balanced one:
  1. every node is red or black;
  2. the root is black;
  3. a red node's children are both black (no two reds in a row);
  4. every path from a node down to a leaf passes through the same number of black
     nodes (equal "black-height").

This chapter builds insertion using Chris Okasaki's beautifully compact functional
formulation: one `balance` function, four symmetric cases, and the red-red violation
bubbles up the tree until the root absorbs it.
"""

RED = "R"
BLACK = "B"


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

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


def _red(node):
    return node is not None and node.color == RED


# region: balance
def _balance(color, value, left, right):
    """Okasaki's balance. Whenever a BLACK node has a red child that itself has a red
    child — a red-red violation, in any of four configurations — rewrite that little
    three-node cluster into a red parent with two black children. The same rebalanced
    shape results from all four cases; only which node ends up on top differs. This one
    rule, applied on the way back up, is the entire rebalancing logic."""
    if color == BLACK:
        if _red(left) and _red(left.left):          # left-left
            return Node(RED, left.value,
                        Node(BLACK, left.left.value, left.left.left, left.left.right),
                        Node(BLACK, value, left.right, right))
        if _red(left) and _red(left.right):         # left-right
            return Node(RED, left.right.value,
                        Node(BLACK, left.value, left.left, left.right.left),
                        Node(BLACK, value, left.right.right, right))
        if _red(right) and _red(right.left):        # right-left
            return Node(RED, right.left.value,
                        Node(BLACK, value, left, right.left.left),
                        Node(BLACK, right.value, right.left.right, right.right))
        if _red(right) and _red(right.right):       # right-right
            return Node(RED, right.value,
                        Node(BLACK, value, left, right.left),
                        Node(BLACK, right.right.value, right.right.left, right.right.right))
    return Node(color, value, left, right)
# endregion


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

    # region: insert
    def insert(self, value):
        """Insert the new node RED (adding a red node can't change any black-height,
        so rule 4 stays intact), fix any red-red violation on the way back up with
        `balance`, and finally force the root black. That's the whole insert — the
        recoloring keeps the height within 2·log₂(n+1)."""
        inserted = [False]

        def ins(node):
            if node is None:
                inserted[0] = True
                return Node(RED, value, None, None)
            if value < node.value:
                return _balance(node.color, node.value, ins(node.left), node.right)
            if value > node.value:
                return _balance(node.color, node.value, node.left, ins(node.right))
            return node

        self.root = ins(self.root)
        self.root.color = BLACK
        if inserted[0]:
            self._n += 1
    # 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):
        def h(node):
            return 0 if node is None else 1 + max(h(node.left), h(node.right))
        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

"""Red-black trees are what real ordered maps use — but in Python they're behind the
C implementation, not exposed directly, so there's no stdlib red-black tree to call.
`dict`/`set` are hash tables (unordered); the third-party `sortedcontainers` is the
practical ordered structure. To show what the color rules buy, the baseline here is the
unbalanced BST from two chapters ago — the same insert without any balancing, which
degenerates on sorted input where the red-black tree stays O(log n).
"""


# 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 unbalanced BST — the same ordering, no color rules, no rebalancing. On
    sorted input it becomes a linked list; the red-black tree's recoloring is what
    prevents exactly that."""

    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 height(self):
        def h(node):
            return 0 if node is None else 1 + max(h(node.left), h(node.right))
        return h(self.root)
# endregion

Desde cero vs librería

Igual que en el capítulo de AVL, este duelo enfrenta balanceado contra desbalanceado en vez de Python contra C, y el balance gana por 68× con entrada ordenada a 8000 nodos, con la brecha abriéndose cuadráticamente. El número más interesante es la comparación con el capítulo anterior: con 100000 nodos ordenados, el árbol rojo-negro midió 22 niveles de alto contra los 17 del AVL. Ambos son O(log n), ambos son mundos mejores que los 100000 del BST simple, pero el rojo-negro es deliberadamente un poco más alto porque rebalancea con menos agresividad. Esa diferencia de cinco niveles es todo el trato AVL-versus-rojo-negro en una sola medición: AVL compra árboles más cortos y búsquedas más rápidas rotando más; rojo-negro compra actualizaciones más baratas tolerando un poco más de altura. La industria del software, necesitando un mapa ordenado de propósito general que aguante lecturas y escrituras por igual, eligió abrumadoramente rojo-negro, que es justamente por lo que es el árbol balanceado que con mayor probabilidad estás usando en este momento.

Dónde te lo vas a encontrar de verdad

Casi con toda seguridad estás corriendo árboles rojo-negro ahora mismo. std::map y std::set en C++, TreeMap y TreeSet en Java, y los contenedores asociativos ordenados de muchos lenguajes son árboles rojo-negro. El kernel de Linux los usa por todos lados: el completely fair scheduler ordena las tareas ejecutables en uno, y las áreas de memoria virtual se rastrean en otro. Cada vez que un software mantiene llaves ordenadas bajo inserciones y eliminaciones frecuentes —un índice de prioridades, un conjunto de intervalos, una tabla de símbolos que debe iterarse en orden— un árbol rojo-negro es el motor más probable. Es el árbol de búsqueda balanceado más desplegado que existe.

Para llevar

Un árbol rojo-negro balancea un BST con colores en los nodos y cuatro reglas que acotan su altura en $2\log_2(n+1)$, garantizando operaciones en $O(\log n)$ mientras rebalancea menos seguido que un AVL — el trato que lo convirtió en el mapa ordenado de la librería estándar. La inserción funcional de Okasaki reduce toda la historia del rebalanceo a una sola función balance sobre cuatro casos rojo-rojo simétricos, y resulta que la estructura es una codificación binaria de un árbol 2-3-4, lo que la amarra directo con los árboles B que vienen.

Esa es la familia de los BST balanceados: AVL para balance apretado y búsquedas rápidas, rojo-negro para actualizaciones baratas y ubicuidad, ambos descendientes del BST simple más una regla para mantenerlo corto. El siguiente capítulo se mueve de lado hacia un tipo de árbol completamente distinto. El heap binario renuncia al orden de árbol de búsqueda a cambio de una regla más débil, "el padre le gana al hijo", y a cambio hace una operación —agarrar siempre el máximo (o el mínimo)— lo más rápida posible. Es la cola de prioridad, y ya conociste su truco de arreglo-como-árbol allá en heapsort.