Los árboles RRB (Relaxed Radix Balanced Trees) son una extensión del tipo de dato vector inmutable que resuelve una de las grandes limitaciones de las estructuras usadas en lenguajes funcionales como Clojure y Scala: la dificultad para concatenar, dividir e insertar vectores sin perder eficiencia. Los autores, Phil Bagwell y Tiark Rompf, de la EPFL, explican que los vectores inmutables clásicos —basados en árboles anchos con un número fijo de hijos por nodo, normalmente 32— ofrecen indexación, actualización e iteración en tiempo prácticamente constante, pero penalizan la concatenación con un coste lineal, lo que dificulta aprovechar el procesamiento en paralelo.
La propuesta amplía esa estructura de 32 ramificaciones para soportar concatenación, inserción en un índice y división (split) en tiempo O(log N), sin sacrificar el rendimiento de las operaciones originales. La idea clave es relajar las restricciones de equilibrio del árbol para permitir unir y partir vectores de forma eficiente, conservando las propiedades que hacen a esta estructura amigable con la caché del procesador.
El artículo repasa trabajos previos sobre estructuras inmutables —Ropes, finger trees 2-3 y B-Trees— y analiza sus compromisos: los Ropes degradan su rendimiento tras concatenaciones y divisiones repetidas, y los finger trees son hasta cinco veces más lentos en indexación que los vectores de 32 ramas. Los RRB-Trees superan ambos inconvenientes.
Entre los casos de uso citados destacan la paralelización de operaciones comunes como filter o map, donde un vector puede dividirse en particiones procesadas en paralelo y luego recombinarse sin copia lineal. También son útiles en implementaciones especializadas de cadenas de caracteres, como las empleadas en generación de páginas web mediante plantillas. Aunque el trabajo se orientó inicialmente a Scala, la estructura es aplicable a Clojure, C, C++ y otros entornos.