La concatenación de árboles rojo-negro
https://stackoverflow.com/questions/3176863
-
02-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
La biblioteca estándar OCaml tiene una aplicación Set maravilloso que utiliza un algoritmo de divide y vencerás muy eficiente para calcular la union de dos conjuntos. Creo que se necesita subárboles enteros (no sólo los elementos individuales) de un conjunto de ellos y se inserta en el otro conjunto, el reequilibrio cuando sea necesario.
Me pregunto si esto requiere la información de altura que se mantiene en el árbol AVL que los usos OCaml o si esto también es posible con árboles rojo-negro. Por ejemplo, ¿es posible concatenar un par de árboles rojo-negro más eficiente que simplemente interactuando sobre el segundo árbol añadiendo sus elementos al final del primer árbol?
Solución
No estoy seguro de la redacción de su pregunta si usted está interesado en la unión de conjuntos o concatenación o ambos, o si sólo está interesado en las estructuras de datos persistentes que son comunes en OCaml o también en estructuras efímeras.
Una aplicación de árboles rojo-negro con los dedos es descrito por Heather D. stand en un capítulo de su tesis . Con los dedos, un árbol rojo-negro de tamaño n puede ser dividido en dos árboles de tamaño p y q en amortizado O (lg (min (p, q))) de tiempo y dos árboles rojo-negro de tamaño P y Q se puede concatenado en la misma cota. Además, un elemento puede ser añadido o eliminado en cualquier extremo de un árbol de rb en tiempo O amortizado (1). Con estas operaciones, es posible lograr amortizado O (p lg (q / p)) Unión de tiempo establecido (por p Los límites anteriormente se amortizan en el sentido tradicional. Para un lenguaje funcional como OCaml, uno podría desear tener límites que se aplican cuando una estructura de datos se utiliza persistentemente. No creo que la descripción de Booth va a lograr todos esos límites cuando los árboles se utilizan persistentemente. Por ejemplo, la inserción en un dedo puede tomar omega (1) recolorings. Esto podría ser resuelto por medio de los recolorings perezosos discutidos en Driscoll et al. ' "estructuras de toma de datos persistentes" . Por otro lado, creo que el análisis de Booth podría mostrar que la concatenación es todavía O (lg (max (p, q))) incluso cuando se utiliza persistentemente. Estoy menos optimista acerca de la unión de conjuntos con destino. operaciones Set con límites de tiempo asintóticamente óptimos son posibles en un ambiente funcional. Aquellos descrito por Hinze y Paterson alcanzar los límites en un amortizado (pero persistente) sentido, el treaps descrito por Blandford y Blelloch alcanzar los límites en un sentido aleatorio , y los descrito por Kaplan y Tarjan alcanzarlos en el tiempo del peor caso. Este último también ofrecen O (lg lg (min (p, q))) de concatenación, aunque Hinze y Paterson son dudosas de dicha reivindicación. Estos árboles no son una respuesta directa a su pregunta, que es específico de árboles rojo-negro, pero esperemos que dan una idea de lo que es posible, y el documento de H & P incluye código, y ha sido verificado correcta utilizando Coq , que se puede extraer a código OCaml. Dos punteros más que podría estar interesado en: Brodal et al. se presentan los árboles de búsqueda con O (lg n) encontrar, insertar y eliminar y O (1) concat incluso en un entorno funcional. Además, Atallah et al. reclamo para describir un árbol rojo-negro que tiene O amortizado (1) concat (presumiblemente efímera solamente) , pero Buchsbaum y Goodrich afirmación de que hay varios defectos en que la estructura . 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 (rojo o negro) sólo es de 1 bit por rama. Mediante la adición de altura, que ha perdido esa ventaja y puede ser que también acaba de utilizar un árbol de altura equilibrada en su lugar. Hay otraventajas también. Por ejemplo, algunas estructuras de datos utilizadas en la geometría computacional se basan en los árboles binarios de búsqueda, pero tienen un alto costo de la rotación del árbol. árboles rojo-negro nivel puede ser regulado en como máximo 3 rotaciones por inserción y supresión , mientras que AVL árboles pueden tomar O (lg n) rotaciones para estas operaciones . Como Ralf Hinze notó , esquema de reequilibrio de Okasaki para los árboles rojo-negro (código disponible < a href = "http://www.eecs.usma.edu/webs/people/okasaki/pfds-sml.tar.gz" rel = "noreferrer"> ML , Haskell , Java y Ada ) no ofrece la misma cota, y puede terminar haciendo O (lg n) rotaciones de inserción. (Okasaki no presenta eliminación.) Además, los árboles de búsqueda de altura equilibrada (e incluso árboles AVL) se puede almacenar de manera que se utilice sólo un bit de información de saldo por nodo. Algunos árboles tienen sólo dos posibles posiciones de equilibrio en cada nodo, como los árboles de un solo lado en altura equilibrada, pero los árboles con hasta cuatro posibles posiciones de balance por nodo puede almacenar un bit de información equilibrio en cada niño, como explicados inicialmente por Brown y más tarde expandido sobre por 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. Se toma O (lg (max (| L |, | R |))) tiempo, lo cual es demasiado tiempo para obtener el tiempo asintóticamente óptima unión describo arriba. A modo de comparación, espero que la "unirse" a la ejecución de conjuntos AVL en stdlib de OCaml obtiene un rendimiento de O (h1-h2), donde H1 es la altura del árbol más alto, a pesar de que en realidad se une a dos árboles AVL dado un elemento que se coloca entre ellos, mientras que el algoritmo de abajo tiene que encontrar y eliminar ese elemento mortero de uno de sus argumentos. Se podría evitar que sólo el almacenamiento de elementos en las hojas, como en un árbol B +, pero que tiene una penalización de espacio de tener que llevar un montón de punteros a los elementos de los nodos que no son hojas para guiar la búsqueda. En cualquier caso, no tendría unirse a tiempo constante para los árboles de la misma altura como la AVL unirse código en el stdlib OCaml, ya que todavía tendría que calcular la altura de cada árbol negro, tal como se explica a continuación. Dados dos árboles no vacía de color rojo-negro L y R, se producirá 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. En primer lugar, retire el elemento más grande de L, c. A continuación, encontrar la altura de negro L y R. Por "altura de negro", es decir el número de nodos negros en cualquier trayectoria de la
raíz a una hoja. Por los invariantes árbol rojo-negro, esto es constante en todas las rutas de un árbol dado. Llamada L's negro altura y la altura p q negro de R, y asumir
w.l.o.g. p = q. A partir de la raíz de R, siga los niños izquierda hasta llegar a un nodo negro R' con la altura p. Hacer un nuevo árbol C rojo con elemento raíz c, izquierda y derecha L niño
niño R'. Desde L es un árbol rojo-negro en su propio, su raíz es de color negro, y los invariantes de color no se violan en o por debajo C. Además, la altura de negro de C
es p. Sin embargo, no podemos simplemente volver C empalme en R en lugar de R'. En primer lugar, si p =Q, R' es R, sin embargo, tiene una raíz C rojo. En este caso, basta con cambiar el color de la raíz de C negro. Esta es tu
nuevo árbol concatenada. En segundo lugar, si R' no es la raíz, puede tener un padre rojo. los padres rojos no se les permite tener niños de color rojo, por lo que hay que reequilibrar. Aquí sólo se aplica reequilibrio de Okasaki
esquema de todo el camino hasta la columna vertebral entre R'(que ha sido sustituido con C) y la raíz de la I. Hay dos casos posibles. Si C no tiene abuelos, los padres de color negro de C. El árbol es ahora válido. Si C tiene un abuelo, tiene que ser negro y negro de altura p + 1, ya que el padre del C es rojo. Reemplazar los abuelos de C con un nuevo árbol rojo, cuya raíz es la raíz de la matriz de C, el
hijo izquierdo de los cuales es C, recolored negro, y el hijo derecho de los cuales es un árbol negro que consta de un hermano de C, raíz de los abuelos de C, y el tío de C, en
ese orden. Esto no aumenta la altura del abuelo negro de C, pero cambia su color a rojo, lo que podría hacer que sea una raíz o un niño de color rojo de un rojo
padres, así que tenemos que equilibrar de nuevo, y así sucesivamente hasta el final hasta el árbol 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 revertir los punteros de la espina dorsal. Entonces no es necesario la altura del árbol negro grande, sólo es necesario contar nodos espina negro hasta que un árbol se queda sin columna vertebral. A continuación, utilice el original (no de Okasaki) esquema de reequilibrio para asegurarse de que sólo reequilibrio O (1) nodos. Por último, señalar el resto de la columna vertebral que no necesita reequilibrio de cambio de color perezoso si es necesario más adelante.
Otros consejos
Ya que parece estar hablando de concatenación + añadir en el extremo, parece que usted tiene 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 llama la operación de unión en los árboles y en este caso, es posible hacer la unión de los árboles en O (log n), echa un vistazo a: http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf
También puedes ver: http: // net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm , Problema 14.2.
puede hacer mejor que O (log ^ 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 está concatenando. Después de calcular la altura en O (log (n)), utilice la información del balance en cada nodo cuando va por el árbol para encontrar el punto de concatenación derecho!
Es posible ganar algo cuando se le combina con el árbol bajo solapamiento, pero, en general, que tendrá que reorgainze nodos. Con el equilibrio que tiene peor situación, ya que, probablemente, reglas para la rotación después de tocar un solo nodo.
