Árboles Balanceados en C - Eliminación en Red-Black Tree

Eliminar en un Red-Black Tree comienza como un borrado de BST y luego corrige la posible pérdida de un nodo negro. El objetivo es preservar la altura negra uniforme y evitar rojos consecutivos.

10.1 Eliminación como BST

Se sigue el procedimiento estándar de un árbol de búsqueda:

Si el nodo tiene 0 o 1 hijo real, se reemplaza directamente por su hijo (o por NIL).
Si tiene 2 hijos, se busca el sucesor in-order (mínimo del subárbol derecho), se copian sus datos y luego se elimina el sucesor, reduciendo el problema a un caso de 0/1 hijo.
El puntero que sustituye al nodo eliminado se llama hijo y hereda la posible deuda de color.

10.2 Caso del doble negro

Si el nodo eliminado era negro y el hijo que lo reemplaza también es negro (o NIL negro), aparece un doble negro que reduce en 1 la altura negra de los caminos por ese lado.

Se propaga hacia arriba hasta que se restaure la altura negra o se alcance la raíz.
El hermano del nodo doble negro y sus hijos determinan el caso de recoloreo/rotación.

10.3 Recoloreo

El recoloreo resuelve los casos en que el hermano es negro y tiene al menos un hijo rojo o cuando el hermano es rojo:

Hermano rojo: se recolorea hermano a negro y padre a rojo, seguida de rotación hacia el doble negro para convertirlo en un caso de hermano negro.
Hermano negro sin hijos rojos: se pinta el hermano de rojo y se mueve el doble negro hacia el padre (subiendo la deuda).
Hermano negro con hijo rojo lejano: se recolorea para que el hermano pase a color del padre, el padre a negro y el hijo rojo lejano a negro.

10.4 Rotaciones correctivas

Las rotaciones reubican al hermano y al padre para redistribuir la altura negra:

Si el hermano es rojo, una rotación acerca al hermano a la raíz local para exponer un hermano negro.
En casos con hijo rojo cercano, se realiza primero una rotación sobre el hermano para convertirlo en hijo rojo lejano, luego se rota sobre el padre y se recolorean los tres nodos.
Tras la rotación final, el doble negro se elimina: su nodo queda negro o se resuelve al llegar a la raíz.

void arreglarEliminacion(RbNode **raiz, RbNode *x) {
  while (x != *raiz && x->color == NEGRO) {
    int xEsIzq = (x == x->padre->izquierdo);
    RbNode *h = xEsIzq ? x->padre->derecho : x->padre->izquierdo;

    if (h->color == ROJO) {
      h->color = NEGRO;
      x->padre->color = ROJO;
      if (xEsIzq) rotarIzquierda(raiz, x->padre);
      else rotarDerecha(raiz, x->padre);
      h = xEsIzq ? x->padre->derecho : x->padre->izquierdo;
    }

    if (h->izquierdo->color == NEGRO && h->derecho->color == NEGRO) {
      h->color = ROJO;
      x = x->padre;
    } else {
      if (xEsIzq && h->derecho->color == NEGRO) {
        h->izquierdo->color = NEGRO;
        h->color = ROJO;
        rotarDerecha(raiz, h);
        h = x->padre->derecho;
      } else if (!xEsIzq && h->izquierdo->color == NEGRO) {
        h->derecho->color = NEGRO;
        h->color = ROJO;
        rotarIzquierda(raiz, h);
        h = x->padre->izquierdo;
      }
      h->color = x->padre->color;
      x->padre->color = NEGRO;
      if (xEsIzq) {
        h->derecho->color = NEGRO;
        rotarIzquierda(raiz, x->padre);
      } else {
        h->izquierdo->color = NEGRO;
        rotarDerecha(raiz, x->padre);
      }
      x = *raiz;
    }
  }
  x->color = NEGRO;
}

10.5 Código completo para probar en CLion

Ejemplo autocontenible con nodo NIL compartido, inserción y eliminación con correcciones. Copia en main.c y ejecútalo.

#include <stdio.h>
#include <stdlib.h>

typedef enum Color { ROJO, NEGRO } Color;

typedef struct RbNode {
  int clave;
  Color color;
  struct RbNode *izq;
  struct RbNode *der;
  struct RbNode *padre;
} RbNode;

RbNode *NIL;

RbNode *crearNodo(int clave, RbNode *padre) {
  RbNode *n = malloc(sizeof(RbNode));
  n->clave = clave;
  n->color = ROJO;
  n->izq = n->der = NIL;
  n->padre = padre ? padre : NIL;
  return n;
}

void rotarIzquierda(RbNode **raiz, RbNode *x) {
  RbNode *y = x->der;
  x->der = y->izq;
  if (y->izq != NIL) y->izq->padre = x;
  y->padre = x->padre;
  if (x->padre == NIL) *raiz = y;
  else if (x == x->padre->izq) x->padre->izq = y;
  else x->padre->der = y;
  y->izq = x;
  x->padre = y;
}

void rotarDerecha(RbNode **raiz, RbNode *y) {
  RbNode *x = y->izq;
  y->izq = x->der;
  if (x->der != NIL) x->der->padre = y;
  x->padre = y->padre;
  if (y->padre == NIL) *raiz = x;
  else if (y == y->padre->izq) y->padre->izq = x;
  else y->padre->der = x;
  x->der = y;
  y->padre = x;
}

void arreglarInsercion(RbNode **raiz, RbNode *n) {
  while (n->padre != NIL && n->padre->color == ROJO) {
    RbNode *p = n->padre;
    RbNode *g = p->padre;
    int pEsIzq = (p == g->izq);
    RbNode *opuesto = pEsIzq ? g->der : g->izq;

    if (opuesto->color == ROJO) {
      p->color = NEGRO;
      opuesto->color = NEGRO;
      g->color = ROJO;
      n = g;
      continue;
    }

    if (pEsIzq && n == p->der) {
      rotarIzquierda(raiz, p);
      n = p;
      p = n->padre;
    } else if (!pEsIzq && n == p->izq) {
      rotarDerecha(raiz, p);
      n = p;
      p = n->padre;
    }

    p->color = NEGRO;
    g->color = ROJO;
    if (pEsIzq) rotarDerecha(raiz, g);
    else rotarIzquierda(raiz, g);
  }
  (*raiz)->color = NEGRO;
}

RbNode *insertar(RbNode *raiz, int clave) {
  RbNode *padre = NIL;
  RbNode *cur = raiz;
  while (cur != NIL) {
    padre = cur;
    if (clave < cur->clave) cur = cur->izq;
    else if (clave > cur->clave) cur = cur->der;
    else return raiz;
  }

  RbNode *nuevo = crearNodo(clave, padre);
  if (padre == NIL) raiz = nuevo;
  else if (clave < padre->clave) padre->izq = nuevo;
  else padre->der = nuevo;

  arreglarInsercion(&raiz, nuevo);
  return raiz;
}

RbNode *minimo(RbNode *n) {
  while (n->izq != NIL) n = n->izq;
  return n;
}

void trasplantar(RbNode **raiz, RbNode *u, RbNode *v) {
  if (u->padre == NIL) *raiz = v;
  else if (u == u->padre->izq) u->padre->izq = v;
  else u->padre->der = v;
  v->padre = u->padre;
}

void arreglarEliminacion(RbNode **raiz, RbNode *x) {
  while (x != *raiz && x->color == NEGRO) {
    int xEsIzq = (x == x->padre->izq);
    RbNode *h = xEsIzq ? x->padre->der : x->padre->izq;

    if (h->color == ROJO) {
      h->color = NEGRO;
      x->padre->color = ROJO;
      if (xEsIzq) rotarIzquierda(raiz, x->padre);
      else rotarDerecha(raiz, x->padre);
      h = xEsIzq ? x->padre->der : x->padre->izq;
    }

    if (h->izq->color == NEGRO && h->der->color == NEGRO) {
      h->color = ROJO;
      x = x->padre;
    } else {
      if (xEsIzq && h->der->color == NEGRO) {
        h->izq->color = NEGRO;
        h->color = ROJO;
        rotarDerecha(raiz, h);
        h = x->padre->der;
      } else if (!xEsIzq && h->izq->color == NEGRO) {
        h->der->color = NEGRO;
        h->color = ROJO;
        rotarIzquierda(raiz, h);
        h = x->padre->izq;
      }
      h->color = x->padre->color;
      x->padre->color = NEGRO;
      if (xEsIzq) {
        h->der->color = NEGRO;
        rotarIzquierda(raiz, x->padre);
      } else {
        h->izq->color = NEGRO;
        rotarDerecha(raiz, x->padre);
      }
      x = *raiz;
    }
  }
  x->color = NEGRO;
}

RbNode *buscar(RbNode *n, int clave) {
  while (n != NIL && clave != n->clave) {
    n = (clave < n->clave) ? n->izq : n->der;
  }
  return n;
}

RbNode *eliminar(RbNode *raiz, int clave) {
  RbNode *z = buscar(raiz, clave);
  if (z == NIL) return raiz;

  RbNode *y = z;
  Color yColor = y->color;
  RbNode *x;

  if (z->izq == NIL) {
    x = z->der;
    trasplantar(&raiz, z, z->der);
  } else if (z->der == NIL) {
    x = z->izq;
    trasplantar(&raiz, z, z->izq);
  } else {
    y = minimo(z->der);
    yColor = y->color;
    x = y->der;
    if (y->padre == z) {
      x->padre = y;
    } else {
      trasplantar(&raiz, y, y->der);
      y->der = z->der;
      y->der->padre = y;
    }
    trasplantar(&raiz, z, y);
    y->izq = z->izq;
    y->izq->padre = y;
    y->color = z->color;
  }

  if (yColor == NEGRO) {
    arreglarEliminacion(&raiz, x);
  }

  free(z);
  return raiz;
}

void imprimir(RbNode *n, int nivel) {
  if (n == NIL) return;
  imprimir(n->der, nivel + 1);
  for (int i = 0; i < nivel; ++i) printf("   ");
  printf("%d(%c)\n", n->clave, n->color == ROJO ? 'R' : 'N');
  imprimir(n->izq, nivel + 1);
}

int main(void) {
  RbNode nilNode = {0, NEGRO, NULL, NULL, NULL};
  NIL = &nilNode;

  RbNode *raiz = NIL;
  int datos[] = {20, 15, 25, 10, 18, 22, 30, 5, 12, 17, 19};
  int n = (int)(sizeof(datos) / sizeof(datos[0]));
  for (int i = 0; i < n; ++i) {
    raiz = insertar(raiz, datos[i]);
  }

  printf("Inicial:\n");
  imprimir(raiz, 0);

  int borrar[] = {10, 22, 20};
  int m = (int)(sizeof(borrar) / sizeof(borrar[0]));
  for (int i = 0; i < m; ++i) {
    raiz = eliminar(raiz, borrar[i]);
    printf("\nTras eliminar %d:\n", borrar[i]);
    imprimir(raiz, 0);
  }

  return 0;
}

Retornar

10 - Eliminación en Red-Black Tree

10.1 Eliminación como BST

10.2 Caso del doble negro

10.3 Recoloreo

10.4 Rotaciones correctivas

10.5 Código completo para probar en CLion