8 - Rotaciones y recoloreo en Red-Black Tree

En los árboles Red-Black, las rotaciones izquierda/derecha y el recoloreo corrigen violaciones al insertar o eliminar sin perder altura O(log n). Las reglas dependen del color del padre, del tío y de la forma (línea o zig-zag) que adopta el nodo nuevo o el nodo problemático.

8.1 Rotación izquierda

Gira un subárbol para acercar al hijo derecho hacia la raíz local y bajar al nodo original a la izquierda. Se usa cuando hay sesgo a la derecha o en el caso tío negro con forma en L.

  • pivot = nodo->derecho; el hijo derecho sube.
  • nodo->derecho = pivot->izquierdo; mueve el subárbol central.
  • pivot->izquierdo = nodo; enlaza al antiguo padre debajo del pivote.
  • Actualiza padres si se guardan punteros; retorna el nuevo subárbol.
RbNode *rotarIzquierda(RbNode *nodo, RbNode **raiz) {
  RbNode *pivot = nodo->derecho;
  nodo->derecho = pivot->izquierdo;
  if (pivot->izquierdo) pivot->izquierdo->padre = nodo;

  pivot->padre = nodo->padre;
  if (!nodo->padre) {
    *raiz = pivot;
  } else if (nodo == nodo->padre->izquierdo) {
    nodo->padre->izquierdo = pivot;
  } else {
    nodo->padre->derecho = pivot;
  }

  pivot->izquierdo = nodo;
  nodo->padre = pivot;
  return pivot;
}

8.2 Rotación derecha

Simétrica a la izquierda: acerca al hijo izquierdo y baja al nodo original hacia la derecha. Se aplica ante sesgo a la izquierda o en casos tío negro con forma en J invertida.

  • pivot = nodo->izquierdo; el hijo izquierdo sube.
  • nodo->izquierdo = pivot->derecho; conserva el subárbol medio.
  • pivot->derecho = nodo; reubica al nodo original.
  • Ajusta punteros a padres y devuelve el nuevo subárbol.
RbNode *rotarDerecha(RbNode *nodo, RbNode **raiz) {
  RbNode *pivot = nodo->izquierdo;
  nodo->izquierdo = pivot->derecho;
  if (pivot->derecho) pivot->derecho->padre = nodo;

  pivot->padre = nodo->padre;
  if (!nodo->padre) {
    *raiz = pivot;
  } else if (nodo == nodo->padre->derecho) {
    nodo->padre->derecho = pivot;
  } else {
    nodo->padre->izquierdo = pivot;
  }

  pivot->derecho = nodo;
  nodo->padre = pivot;
  return pivot;
}

8.3 Reglas con el tío rojo

Si el padre es rojo y el tío también es rojo, hay dos rojos consecutivos. La solución es solo recolorear:

  • Padre pasa a negro.
  • Tío pasa a negro.
  • Abuelo pasa a rojo (salvo que sea la raíz, que se deja negra).
  • Subir el puntero al abuelo y reevaluar mientras haya dos rojos consecutivos.

Se mantiene la cantidad de nodos negros por camino y se empuja la posible violación hacia arriba sin rotar.

8.4 Reglas con el tío negro + rotaciones

Si el padre es rojo y el tío es negro (o NIL), se requieren rotaciones para evitar dos rojos consecutivos. Se analizan dos formas:

  • Forma en zig-zag (LR o RL): primero rotar al padre para convertirla en línea y luego rotar al abuelo.
  • Forma en línea (LL o RR): rotar directamente al abuelo en sentido contrario al sesgo.

Tras la rotación final, el nuevo padre de la subestructura se colorea negro y el abuelo original se colorea rojo. Esto elimina los rojos consecutivos y preserva la altura negra.

Retornar