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.
def rotar_izquierda(nodo, raiz):
  pivot = nodo.derecho
  nodo.derecho = pivot.izquierdo
  if pivot.izquierdo:
    pivot.izquierdo.padre = nodo

  pivot.padre = nodo.padre
  if not nodo.padre:
    raiz[0] = pivot
  elif 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.
def rotar_derecha(nodo, raiz):
  pivot = nodo.izquierdo
  nodo.izquierdo = pivot.derecho
  if pivot.derecho:
    pivot.derecho.padre = nodo

  pivot.padre = nodo.padre
  if not nodo.padre:
    raiz[0] = pivot
  elif 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