Red-Black Tree es un BST auto-balanceado con 5 propiedades que garantizan altura ≤ 2 log₂(n+1). Es más relajado que AVL (balance aproximado) pero con menos rotations en inserción/eliminación, haciéndolo más rápido en práctica para workloads con muchas modificaciones.

Usado en C++ std::map, Java TreeMap, Linux kernel (CFS scheduler), y databases.

5 Propiedades

1. Cada nodo es rojo o negro.
2. La raíz es negra.
3. Todas las hojas (NIL) son negras.
4. Si un nodo es rojo, ambos hijos son negros (no dos rojos consecutivos).
5. Para cada nodo, todo camino a sus hojas descendientes tiene la misma cantidad de nodos negros (black-height).

Insert Fix-Up

1. Inserta nodo como en BST estándar, color = rojo (preserva black-height).
2. Si padre es negro: no hay problema.
3. Si padre es rojo: tripleta roja (padre, nodo, tío).
   • Tío rojo: recolorea padre y tío a negro, abuelo a rojo, continúa desde abuelo.
   • Tío negro: rotación + recoloring según casos (triangle o line).
4. Raíz siempre negra al final.

Ejemplo: Tío Rojo

      G (negro)
     / \\
    P (rojo)   U (rojo)
   / \\
  N (nuevo, rojo)  ...

Recolorea: P→negro, U→negro, G→rojo. Ahora el problema sube al abuelo.

Delete Fix-Up

Eliminar en RBT es más complejo que AVL porque la estructura es más flexible. Requiere hasta O(log n) rotations y recoloring.

Comparación

Aplicaciones

• C++ std::map/set — RBT es el default
• Java TreeMap — RBT implementation
• Linux kernel — CFS scheduler usa RBT
• Databases — índices en memoria
• JVM — garbage collection (card table)
• Enseñanza — introduce balance relajado y fix-up cases

Trayectoria de Práctica

1. Investiga insert fix-up: traza los casos con tío rojo, triangle, y line.
2. Investiga delete fix-up: ¿por qué es más complejo?
3. Verifica que todas las rutas a hojas tienen el mismo black-height.
4. Compara altura con AVL: para n=1000, ¿cuántos niveles de diferencia?
5. Investiga LLRB (Left-Leaning Red-Black): ¿cómo simplifica cases?