9 - Inserción en Red-Black Tree

Insertar en un Red-Black Tree comienza como un BST normal y luego aplica recoloreo y rotaciones para evitar dos rojos consecutivos y conservar la misma cantidad de nodos negros en cada camino.

vizualizador de arbol Red-Black

9.1 Inserción como BST

El primer paso es idéntico a un árbol de búsqueda binaria:

  • Recorrer por izquierda si la clave es menor, derecha si es mayor.
  • Si la clave ya existe, se puede devolver el nodo y no insertar duplicados.
  • Al llegar a una hoja NIL, se crea el nuevo nodo enlazándolo donde corresponda.

9.2 Colorear nodo inicial

El nodo recién creado se pinta rojo; esto evita incrementar la altura negra. Excepción: si es la raíz, se recolorea a negro al final para cumplir la regla.

  • Los punteros izquierdo y derecho apuntan al nodo NIL negro compartido.
  • Se guarda el puntero al padre si la estructura lo maneja.

9.3 Casos de recoloreo

Si el padre es rojo y el tío también es rojo, hay una violación de dos rojos consecutivos. La corrección es solo de colores:

  • Padre → negro.
  • Tío → negro.
  • Abuelo → rojo (salvo que sea la raíz; en ese caso queda negro).
  • Subir el puntero al abuelo y seguir verificando hacia arriba.

Este caso no requiere rotaciones y mantiene la altura negra en todos los caminos.

9.4 Casos de rotación

Si el padre es rojo y el tío es negro (o NIL), las rotaciones eliminan los rojos consecutivos. Se analizan dos formas:

  • Zig-zag (LR o RL): rotar primero al padre para convertir la forma en línea y luego rotar al abuelo.
  • Línea (LL o RR): rotar directamente al abuelo en sentido opuesto al sesgo.

Tras la rotación final, el nuevo padre de la subestructura se colorea negro y el abuelo original se colorea rojo para evitar rojos consecutivos y conservar la altura negra.

void arreglarInsercion(RbNode **raiz, RbNode *n) {
  while (n->padre != NIL && n->padre->color == ROJO) {
    RbNode *p = n->padre;
    RbNode *g = p->padre;
    int padreEsIzq = (p == g->izquierdo);
    RbNode *tio = padreEsIzq ? g->derecho : g->izquierdo;

    if (tio->color == ROJO) {
      /* Caso tío rojo: solo recolorear */
      p->color = NEGRO;
      tio->color = NEGRO;
      g->color = ROJO;
      n = g;
      continue;
    }

    /* Tío negro: rotaciones */
    if (padreEsIzq && n == p->derecho) {
      rotarIzquierda(raiz, p);
      n = p;
      p = n->padre;
    } else if (!padreEsIzq && n == p->izquierdo) {
      rotarDerecha(raiz, p);
      n = p;
      p = n->padre;
    }

    /* Forma en línea */
    p->color = NEGRO;
    g->color = ROJO;
    if (padreEsIzq) rotarDerecha(raiz, g);
    else rotarIzquierda(raiz, g);
  }
  (*raiz)->color = NEGRO;
}

RbNode *insertarRbt(RbNode *raiz, int clave) {
  /* 1) Inserción tipo BST */
  RbNode *padre = NIL;
  RbNode *cur = raiz;
  while (cur != NIL) {
    padre = cur;
    if (clave < cur->clave) cur = cur->izquierdo;
    else if (clave > cur->clave) cur = cur->derecho;
    else return raiz; /* duplicado */
  }

  RbNode *nuevo = crearNodoRbt(clave, padre);
  if (padre == NIL) {
    raiz = nuevo;
  } else if (clave < padre->clave) {
    padre->izquierdo = nuevo;
  } else {
    padre->derecho = nuevo;
  }

  /* 2) Arreglar colores/rotaciones */
  arreglarInsercion(&raiz, nuevo);
  return raiz;
}

9.5 Código completo para probar en CLion

Ejemplo autocontenible con nodo NIL compartido, inserción y correcciones. Puedes crear un proyecto vacío en CLion, pegar este archivo main.c y ejecutarlo.

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

typedef enum Color { ROJO, NEGRO } Color;

typedef struct RbNode {
  int clave;
  Color color;
  struct RbNode *izquierdo;
  struct RbNode *derecho;
  struct RbNode *padre;
} RbNode;

RbNode *NIL;

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

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

void rotarDerecha(RbNode **raiz, RbNode *y) {
  RbNode *x = y->izquierdo;
  y->izquierdo = x->derecho;
  if (x->derecho != NIL) x->derecho->padre = y;
  x->padre = y->padre;
  if (y->padre == NIL) *raiz = x;
  else if (y == y->padre->izquierdo) y->padre->izquierdo = x;
  else y->padre->derecho = x;
  x->derecho = 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 padreEsIzq = (p == g->izquierdo);
    RbNode *tio = padreEsIzq ? g->derecho : g->izquierdo;

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

    if (padreEsIzq && n == p->derecho) {
      rotarIzquierda(raiz, p);
      n = p;
      p = n->padre;
    } else if (!padreEsIzq && n == p->izquierdo) {
      rotarDerecha(raiz, p);
      n = p;
      p = n->padre;
    }

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

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

  RbNode *nuevo = crearNodo(clave, padre);
  if (!padre) {
    raiz = nuevo;
  }
  else if (clave < padre->clave) padre->izquierdo = nuevo;
  else padre->derecho = nuevo;

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

void imprimirEnOrden(RbNode *n) {
  if (n == NIL) return;
  imprimirEnOrden(n->izquierdo);
  printf("%d(%c) ", n->clave, n->color == ROJO ? 'R' : 'N');
  imprimirEnOrden(n->derecho);
}

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

  RbNode *raiz = NIL;
  int datos[] = {10, 20, 30, 15, 25, 5, 1, 50};
  int cantidad = (int)(sizeof(datos) / sizeof(datos[0]));
  for (int i = 0; i < cantidad; ++i) {
    raiz = insertar(raiz, datos[i]);
  }

  imprimirEnOrden(raiz);
  printf("\n");
  return 0;
}
Secuencia de eliminación y rebalanceo en un árbol AVL
Retornar