algorithm - separador - Concatenando árboles rojo-negros.

excel concatenar celdas con separador (4)

La biblioteca estándar de OCaml tiene una maravillosa implementación de Set que utiliza un algoritmo muy eficiente de dividir y conquistar para calcular la union de dos conjuntos. Creo que toma subárboles enteros (no solo elementos individuales) de un conjunto y los inserta en el otro conjunto, reequilibrando cuando sea necesario.

Me pregunto si esto requiere la información de altura que se guarda en el árbol AVL que usa OCaml o si esto también es posible con árboles rojo-negros. Por ejemplo, ¿es posible concatenar un par de árboles rojo-negro más eficientemente que simplemente iterar sobre el segundo árbol agregando sus elementos al final del primer árbol?

No estoy seguro de la redacción de su pregunta si está interesado en establecer una unión o concatenación, o si solo está interesado en estructuras de datos persistentes como son comunes en OCaml o también en estructuras efímeras.

Heather D. Booth describe una implementación de árboles rojo-negros con dedos en un capítulo de su tesis . Con los dedos, un árbol rojo-negro de tamaño n se puede dividir en dos árboles de tamaño p y q en el tiempo amortizado O (lg (min (p, q))) y dos árboles rojo-negros de tamaño p y q pueden ser Concatenado en el mismo límite. Además, un elemento se puede agregar o eliminar al final de un árbol rb en O (1) amortizado. Con estas operaciones, es posible lograr una unión de conjunto de tiempo O (p lg (q / p) amortizada) (para p <q), que es teóricamente óptima para la información. Quizás la idea clave para obtener estos límites es la inversión de los punteros del niño en las espinas dorsales 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 utiliza de forma persistente. 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 coloraciones ω (1). Esto podría resolverse a través de los cambios de color perezosos discutidos en "Hacer estructuras de datos persistentes" de Driscoll et al .

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 de forma persistente. Soy menos optimista sobre el conjunto unido a la unión.

Las operaciones de configuración con límites de tiempo asintóticamente óptimos son posibles en una configuración funcional. Los descritos por Hinze y Paterson alcanzan los límites en un sentido amortizado (pero persistente), los tratamientos descritos por Blandford y Blelloch alcanzan los límites en un sentido aleatorio , y los descritos por Kaplan y Tarjan los logran en el peor de los casos. Los últimos también ofrecen O (lg lg (min (p, q)) concatenación, aunque Hinze y Paterson dudan de esa afirmación. Estos árboles no son una respuesta directa a su pregunta, que es específica de los árboles rojo-negro, pero se espera que den una idea de lo que es posible, y el documento de H&P incluye un código, y se verificó correctamente utilizando Coq , que puede extraer a Código OCaml.

Otros dos puntos que podrían interesarle: Brodal et al. presentó los árboles de búsqueda con O (lg n) buscar, insertar y eliminar y O (1) concat incluso en una configuración funcional . Adicionalmente, Atallah et al. afirma que describe un árbol rojo-negro que ha amortizado O (1) concat (probablemente solo de manera efímera) , pero Buchsbaum y Goodrich afirman que hay varias fallas en esa estructura .

Una nota final sobre la utilidad de los árboles rojo-negro: en uno de los comentarios sobre una de las respuestas a esta pregunta, usted dice:

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 la geometría computacional se basan en árboles de búsqueda binarios pero tienen un alto costo de rotación de árboles. Los árboles rojo-negro se pueden reequilibrar a lo sumo en 3 rotaciones por inserción y eliminación , mientras que los árboles AVL pueden tomar rotaciones Ω (lg n) para estas operaciones . Como Ralf Hinze notó , el esquema de rebalanceo de Okasaki para árboles rojo-negros (código disponible en ML , Haskell , Java y Ada ) no ofrece el mismo límite y puede terminar haciendo rotaciones de Ω (lg n) en la inserción. (Okasaki no presenta eliminación).

Además, los árboles de búsqueda de altura equilibrada (e incluso los árboles AVL) se pueden almacenar para utilizar solo un bit de información de balance por nodo. Algunos árboles solo tienen dos posiciones de equilibrio posibles en cada nodo, como los árboles de altura equilibrada de una cara, pero los árboles con hasta cuatro posiciones de equilibrio posibles por nodo pueden almacenar un bit de información de equilibrio en cada niño, como lo explicó Brown en una versión posterior. ampliado por Haeupler et al.

Editar:

En respuesta a su consulta específica al final de su pregunta, aquí hay una descripción de un algoritmo para concatenar dos árboles rojo-negro. Lleva O (lg (max (| L |, | R |))) tiempo, que es demasiado largo para obtener el tiempo de unión asintóticamente óptimo que describí anteriormente. A modo de comparación, espero que la implementación de "unión" para los conjuntos de AVL en stdlib de OCaml obtenga un rendimiento de O (h1-h2), donde h1 es la altura del árbol más alto, aunque en realidad se une a dos árboles de AVL dado un elemento que encaja entre ellos , mientras que el algoritmo a continuación tiene que encontrar y eliminar ese elemento de mortero de uno de sus argumentos. Se podría evitar solo 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 elementos en los nodos que no son hojas para guiar la búsqueda. En cualquier caso, no sería un tiempo constante de unión para árboles de la misma altura que el código de unión AVL en la tabla de contenido de OCaml, ya que aún tendría que calcular la altura de negro de cada árbol, como se explica a continuación.

Dados dos árboles rojo-negro no vacíos L y R, produciremos un nuevo árbol rojo-negro que es la concatenación de L y R. Esto tomará un tiempo proporcional a O (lg (max (| L |, | R | ))), donde | L | Denota el número de nodos en L.

Primero, quite el elemento más grande de L, c. Luego, encuentre la altura negra de L y R. Por "altura negra", me refiero al número de nodos negros en cualquier camino desde la raíz a una hoja. Por los invariantes del árbol rojo-negro, esto es constante en todos los caminos de cualquier árbol dado. Llame a la altura negra de L p y la altura negra de R q, y suponga wlog p ≤ q.

Desde la raíz de R, siga a los niños de 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 hijo izquierdo L y el hijo derecho R ''. Como L es un árbol rojo-negro en sí mismo, su raíz es negra y los invariantes de color no se violan en o por debajo de C. Además, la altura negra de C es p.

Sin embargo, no podemos simplemente empalmar C de nuevo en R en lugar de R ''. Primero, si p = q, R ''es R, sin embargo, C tiene una raíz roja. En este caso, simplemente vuelva a colorear la raíz de C negro. Este es tu nuevo árbol concatenado.

Segundo, si R ''no es la raíz, puede tener un padre rojo. A los padres rojos no se les permite tener hijos rojos, por lo que debemos reequilibrar. Aquí solo aplicamos el esquema de rebalanceo de Okasaki hasta el final de la columna vertebral entre R ''(ahora reemplazado con C) y la raíz de R.

Hay dos casos posibles. Si C no tiene abuelo, el color de 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 es rojo. Reemplace al abuelo de C con un nuevo árbol rojo, cuya raíz es la raíz del padre de C, cuyo hijo izquierdo es C, negro recolored y el hijo derecho de un árbol negro que consiste en el hermano de C, la raíz de abuelo de C , y el 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 una raíz o un hijo rojo de un padre rojo, por lo que tenemos que volver a equilibrar, y así sucesivamente hasta el final árbol

Encontrar la altura negra de ambos árboles: O (lg | L |) + O (lg | R |)
Rastreando R hasta el punto correcto: O (lg | R | - lg | L |)
Rotaciones hasta 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 este O (lg (min (| L |, | R |))), primero invierta los punteros de la columna vertebral. Entonces no necesita la altura negra del árbol más grande, solo necesita contar los nodos de la columna vertebral negra hasta que un árbol se quede sin la columna vertebral. Luego, use el esquema de rebalanceo original (no de Okasaki) para asegurarse de que solo reequilibre los nodos O (1). Finalmente, marque el resto de la columna vertebral que no necesita reequilibrar para volver a colorear perezoso si es necesario más tarde.

Puede ganar algo cuando combine un árbol con una superposición baja, pero en general tendrá que volver a ordenar los nodos. Con el balanceo tiene una situación peor, ya que probablemente haya reglas para rotar después de tocar solo un nodo.

Puede hacerlo mejor que O (registro ^ 2 (n)) al concatenar y no aumentar el árbol con información de altura en cada nodo. Puede concatenar en 2 * [log (n1) + log (n2)] donde n1 y n2 representan el número de nodos en los árboles que está concatenando. Después de calcular la altura en O (log (n)), use la información de Balance en cada nodo al bajar el árbol para encontrar el punto de concatenación correcto.

Ya que parece que estás hablando de que Concatenate + se agrega al final, parece que tienes el siguiente problema:

Given two red-black trees T1 and T2, such that keys of T1 <= keys of T2, find union of the two.

Esto se denomina la operación de unión en los árboles y, en este caso, es posible realizar la unión de los árboles en tiempo O (log n), consulte: http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf

También revise: http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm , Problema 14.2.