¿Cómo funcionan los Árboles Binarios Rojo-Negro?

Los árboles binarios rojo-negro son estructuras de datos elegantes y eficientes, implementadas en un sinfín de lugares como bases de datos, sistemas operativos y lenguajes de programación.

Un árbol binario rojo-negro es capaz de mantenerse (casi) perfectamente balanceado sin importar el orden en que se inserten o eliminen los elementos, cosa que no ocurre con los árboles binarios de búsqueda tradicionales. Por ejemplo, si en un árbol binario de búsqueda tradicional insertamos los números 1, 2, 3 y 4, precisamente en este orden, los nodos terminarán formando una lista enlazada, lo que resultará en un rendimiento deficiente para las operaciones de búsqueda, inserción y eliminación (O(n) para encontrar el 4, por ejemplo). Mientras que, en un árbol rojo-negro, el mismo conjunto de números se mantendría relativamente balanceado (nunca mayor a O(log n)).

  BST tradicional         Árbol rojo-negro
  (1, 2, 3, 4 en orden)   (mismos elementos)

  1                           2
   \                         / \
    2                       1   3
     \                           \
      3                           4
       \
        4

Los detalles sobre el algoritmo de auto-balanceo de estas estructuras aparecen escritos en numerosos artículos, apuntes y libros. Pero lo que hacía falta, era una manera de ver el algoritmo en acción.

Por eso escribí rbtrees, un React Component que permite visualizar de forma interactiva los procesos de insercion, búsqueda y eliminación de nodos en un árbol binario rojo-negro.

Al ser un React Component, es fácil de integrar en prácticamente cualquier lado, como por ejemplo, justo aquí debajo:

El Stack

• React 18, TypeScript y Vite
• SVG puro: sin canvas, sin librerías de visualización
• Animaciones con interpolación frame a frame via requestAnimationFrame

La Arquitectura

• RBT/ — implementa el árbol y sus operaciones sin saber nada de la UI
• TreeVisualizer/ — se encarga de renderizar y animar
• La comunicación entre ambas ocurre a través de una función de log que el árbol llama cada vez que su estado cambia, generando una secuencia de snapshots que el visualizador reproduce paso a paso

Los Retos

El mayor reto fue sincronizar las animaciones con los pasos del algoritmo. Cada operación —inserción, búsqueda, eliminación— genera múltiples eventos internos (comparaciones, rotaciones, recoloraciones) y cada uno debe traducirse en una transición visual coherente. Un caso especialmente delicado fue la eliminación con sucesor: el nodo eliminado y el nodo flotante deben desvanecerse al mismo tiempo, lo que exigió controlar con precisión el momento exacto en que se registra cada snapshot.

El Algoritmo de Distribución de los Nodos en un Grid

Posicionar los nodos de un árbol en pantalla parece sencillo, pero no lo es. El reto es que cada subárbol ocupa un espacio que depende de sus hijos, y los subárboles izquierdo y derecho deben encajar sin solaparse.

La solución fue modelar cada subárbol como un Grid: una estructura que describe, fila por fila, cuántas celdas ocupa a la izquierda y a la derecha de su raíz. Al combinar dos Grids (uno por cada hijo), se puede calcular la posición exacta del nodo padre de forma que ambos subárboles queden alineados y sin colisiones. Las posiciones de todos los nodos son relativas a la raíz, lo que mantiene el árbol centrado en el viewport independientemente de su forma.