7 - Árboles Red-Black (Rojo-Negro)

Los Red-Black Tree (RB) conservan altura O(log n) permitiendo recoloreos y rotaciones en inserciones y eliminaciones. El balance es más laxo que en AVL, pero a cambio cada operación requiere a lo sumo un puñado de cambios locales.

7.1 Definición y propiedades

• Cada nodo es rojo o negro.
• La raíz siempre es negra.
• Las hojas nulas (NIL) se consideran negras.
• Un nodo rojo no puede tener hijos rojos (no hay dos rojos consecutivos).
• Todo camino desde un nodo hasta una hoja NIL contiene el mismo número de nodos negros (black-height).

7.2 Hojas nulas (NIL)

En los árboles Red-Black, las hojas nulas (NIL) son nodos especiales ficticios que no contienen datos y sirven para simplificar la lógica.

¿Qué son exactamente las hojas NIL?

• Punteros nulos representados como nodos reales compartidos.
• No almacenan valores; marcan el final de cada rama.
• Se consideran siempre negras.
• En lugar de left = null o right = null, muchos códigos usan un nodo NIL global para todas las hojas vacías.

¿Por qué existen?

• Uniformidad: rotar, insertar, borrar o verificar propiedades es más simple si siempre hay un nodo hijo (aunque sea NIL) y se evitan chequeos constantes de null.
• Altura negra: la regla exige que todo camino hasta una hoja NIL tenga la misma cantidad de nodos negros; definirlas como negras permite comparar fácilmente la black-height.
• Menos casos especiales: todos los nodos mantienen dos hijos (reales o NIL), lo que limpia el código.

        (10, negro)
        /         \
   (5, rojo)      (15, negro)
   /      \        /        \
 NIL     NIL     NIL        NIL

Resumen corto: las hojas NIL representan la ausencia de hijo, siempre son negras y simplifican tanto las propiedades como las implementaciones.

7.3 Colores y reglas fundamentales

El algoritmo usa recoloreo y rotaciones para restaurar las reglas tras insertar o eliminar. Si se viola la regla de rojos consecutivos, se recolorea al padre/tío o se rota el subárbol afectado. La igualdad de nodos negros por camino se mantiene ajustando colores y rotaciones hasta que la raíz quede negra.

7.4 Estructura del nodo en Python

Una estructura típica guarda el color y, opcionalmente, una referencia al padre para simplificar los casos de rebalanceo.

ROJO = "ROJO"
NEGRO = "NEGRO"

class RbNode:
  def __init__(self, clave, color=ROJO, padre=None):
    self.clave = clave
    self.color = color
    self.izquierdo = None
    self.derecho = None
    self.padre = padre  # opcional pero facilita recoloreos

def es_rojo(nodo):
  return nodo is not None and nodo.color == ROJO

def es_negro(nodo):
  return nodo is None or nodo.color == NEGRO

7.5 Por qué son casi balanceados

La restricción de black-height garantiza que el camino más largo es a lo sumo el doble del más corto. Formalmente, la altura de un RB es ≤ 2 × log₂(n + 1). Esto basta para que buscar, insertar y eliminar sigan siendo O(log n) sin exigir el balance estricto de AVL.