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 C

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

typedef enum Color { ROJO, NEGRO } Color;

typedef struct RbNode {
  int clave;
  Color color;
  struct RbNode *izquierdo;
  struct RbNode *derecho;
  struct RbNode *padre; /* opcional pero facilita recoloreos */
} RbNode;

static int esRojo(RbNode *n) { return n && n->color == ROJO; }
static int esNegro(RbNode *n) { return !n || n->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.