No estoy seguro por la redacción de su pregunta si está interesado en establecer unión o concatenación o ambos, o si solo está interesado en estructuras de datos persistentes como son comunes en OCaml o también en estructuras efímeras.
Una implementación de red-black trees with fingers is described by Heather D. Booth in a chapter from her thesis. Con los dedos, un árbol rojo-negro de tamaño n se puede dividir en dos árboles de tamaño p y q en tiempo O (lg (min (p, q))) amortiguado y dos árboles rojo-negro de tamaño pyq pueden ser concatenado en el mismo límite. Además, un elemento se puede agregar o eliminar en cualquier extremo de un árbol rb en tiempo O (1) amortizado. Con estas operaciones, es posible lograr una unión de tiempo de amortización O (p lg (q/p)) (para p < q), que es teóricamente la información óptima. Tal vez la idea clave para obtener estos límites es la inversión de los indicadores secundarios en las líneas de columna izquierda y derecha.
Los límites anteriores se amortizan en el sentido tradicional. Para un lenguaje funcional como OCaml, uno podría desear tener límites que se apliquen cuando una estructura de datos se usa persistentemente. No creo que la descripción de Booth logre todos esos límites cuando los árboles se usan de manera persistente. Por ejemplo, la inserción en un dedo puede tomar ω (1) recolocaciones. Esto podría resolverse a través del lazy recolorings discussed in Driscoll et al.'s "Making Data Structures Persistent".
Por otro lado, creo que el análisis de Booth podría mostrar que la concatenación sigue siendo O (lg (max (p, q))) incluso cuando se usa persistentemente. Soy menos optimista sobre el conjunto de unión obligado.
Las operaciones de ajuste con límites de tiempo asintóticamente óptimos son posibles en una configuración funcional. Esos described by Hinze & Paterson alcanzan los límites en un sentido amortizado (pero persistente), el treaps described by Blandford & Blelloch achieve the bounds in a randomized sense, y esos described by Kaplan & Tarjan los alcanzan en el peor de los casos. Estos últimos también ofrecen O (lg lg (min (p, q))) concatenación, aunque Hinze & Paterson son dudosos de esa afirmación. Estos árboles no son una respuesta directa a su pregunta, que es específica de los árboles rojo-negro, pero con suerte dan un sabor de lo que es posible, y el documento H & P incluye código y has been verified correct using Coq, que puede extraer al código OCaml.
Dos punteros más que pueden interesarle: Brodal et al. presented search trees with O(lg n) find, insert, and delete and O(1) concat even in a functional setting. Además, Atallah et al. claim to describe a red-black tree that has amortized O(1) concat (presumably ephemerally only), pero Buchsbaum and Goodrich claim that there are several flaws in that structure.
Una nota final sobre la utilidad de los árboles rojo-negro: en uno de los comentarios en una de las respuestas a esta pregunta, es decir:
La única ventaja de un árbol rojo-negro es que la información auxiliar (roja o negra) es solo de 1 bit por rama. Al agregar altura, ha perdido esa ventaja y podría usar un árbol de altura equilibrada.
También hay otras ventajas. Por ejemplo, algunas estructuras de datos utilizadas en geometría computacional se basan en árboles de búsqueda binarios pero tienen un alto costo de rotación de árboles. Red-black trees can be rebalanced in at most 3 rotations per insert and delete, mientras que AVL trees can take Ω(lg n) rotations for these operations. As Ralf Hinze noticed, Okasaki's rebalancing scheme for red-black trees (código disponible en ML, Haskell, Java, and Ada) no ofrece el mismo límite, y puede terminar haciendo Ω (lg n) rotaciones en la inserción. (Okasaki no presenta eliminación.)
Además, los árboles de búsqueda con equilibrio de altura (e incluso los árboles AVL) se pueden almacenar para utilizar solo un bit de información de equilibrio por nodo. Algunos árboles tienen solo dos posibles posiciones de equilibrio en cada nodo, como árboles balanceados en una sola cara, pero los árboles con hasta cuatro posibles posiciones de equilibrio por nodo pueden almacenar un bit de información de saldo en cada niño, como initially explained by Brown y más tarde expanded upon by Haeupler et al.
Editar:
en respuesta a su consulta específica al final de su pregunta, he aquí una descripción de un algoritmo para la concatenación de dos árboles rojo-negro. Toma el tiempo O (lg (max (| L |, | R |))), que es demasiado largo para obtener el tiempo de unión asintóticamente óptimo que describo arriba. A modo de comparación, espero que the "join" implementation for AVL sets in OCaml's stdlib obtenga un rendimiento O (h1-h2), donde h1 es la altura del árbol más alto, aunque se une a dos árboles AVL dado un elemento que se ajusta entre ellos, mientras que el algoritmo siguiente debe buscar y eliminar ese elemento de mortero de uno de sus argumentos. Podrías evitar eso almacenando elementos en las hojas, como en un árbol B +, pero eso tiene una penalización de espacio de tener que mantener un montón de punteros a los elementos en los nodos hoja para guiar la búsqueda. En cualquier caso, no se uniría el tiempo constante para árboles de la misma altura, como el código de unión AVL en OCaml stdlib, ya que aún tendría que calcular la altura negra de cada árbol, como se explica a continuación.
Dados dos árboles rojos y negros no vacíos L y R, produciremos un nuevo árbol rojo-negro que es la concatenación de L y R. Esto tomará tiempo proporcional a O (lg (max (| L |, | R |))), donde | L | denota el número de nodos en L.
Primero, elimine el elemento más grande de L, c. Luego, encuentre la altura negra de L y R. Por "altura negra", me refiero a la cantidad de nodos negros en cualquier ruta desde la raíz hasta una hoja. Por los invariantes del árbol rojo-negro, esto es constante en todos los caminos de cualquier árbol dado. Llame a la altura de negro p de L y la altura de negro de R q, y asuma w.l.o.g. p ≤ q.
Desde la raíz de R, siga hacia la izquierda hasta llegar a un nodo negro R 'con altura p. Cree un nuevo árbol rojo C con el elemento raíz c, el niño izquierdo L y el derecho niño R '. Como L es un árbol rojo-negro en sí mismo, su raíz es negra, y las invariantes de color no se violan ao por debajo de C. Además, la altura de negro de C es p.
Sin embargo, no podemos simplemente empalmar C en R en lugar de R '. Primero, si p = q, R 'es R, pero C tiene una raíz roja. En este caso, simplemente vuelva a colorear la raíz de C negro. Este es su nuevo árbol concatenado .
En segundo lugar, si R 'no es la raíz, puede tener un elemento primario rojo. A los padres rojos no se les permite tener hijos rojos, por lo que debemos reequilibrarlos. Aquí solo aplicamos el esquema de reequilibrio de Okasaki hasta el final del lomo entre R '(ahora reemplazado con C) y la raíz de R.
Hay dos casos posibles. Si C no tiene un abuelo, el padre del color C es negro. El árbol ahora es válido.
Si C tiene un abuelo, debe ser negro y de altura negra p + 1, ya que el padre de C está en rojo. Reemplace a los abuelos de C con un nuevo árbol rojo, cuya raíz es la raíz del padre de C, el niño de la izquierda, C, recolored negro, y el niño derecho del cual es un árbol negro que consiste en el hermano de C, los abuelos de C root, y tío de C, en ese orden. Esto no aumenta la altura negra del abuelo de C, pero cambia su color a rojo, lo que podría convertirlo en un hijo raíz o rojo de un padre rojo , por lo que tenemos que reequilibrar de nuevo, y así sucesivamente hasta el final el árbol
- Encontrar la altura del negro de los dos árboles: O (lg | L |) + O (lg | R |)
- rastreo por R en el lugar correcto: O (lg | R | - LG | L |)
- Rotaciones todo el camino de vuelta a la raíz: O (lg | R | - LG | L |)
Ninguno de estos es mayor que O (lg | R | + lg | L |) = O (lg (max (| L |, | R |)))
Para hacer esto O (lg (min (| L |, | R |))), primero invierta los punteros del lomo. Entonces no necesitas la altura negra del árbol más grande, solo necesitas contar los nodos negros de la columna vertebral hasta que un árbol se quede sin columna vertebral. Luego, use el esquema de reequilibrio original (no el de Okasaki) para asegurarse de que solo reequilibre los O (1) nodos. Finalmente, marque el resto de la columna vertebral que no necesita un reequilibrio para un rediseño lento si es necesario más adelante.
Alguien votó para cerrar mi pregunta como "fuera del tema". ¿Desde cuándo los árboles RB están fuera de tema en Stack Overflow? –