Subrango de un árbol rojo y negro

14

Mientras intentaba corregir un error en una biblioteca, busqué documentos para encontrar subranges en árboles rojos y negros sin éxito. Estoy considerando una solución con cremalleras y algo similar a la operación de adición habitual utilizada en algoritmos de eliminación para estructuras de datos inmutables, pero todavía me pregunto si hay un mejor enfoque que no pude encontrar, o incluso algún límite de complejidad mínima en tal operación?

Para ser claros, estoy hablando de un algoritmo que, dado un árbol rojo y negro y dos límites, producirá un nuevo árbol rojo y negro con todos los elementos del primer árbol que pertenecen a esos límites.

Por supuesto, un límite superior para la complejidad sería la complejidad de atravesar un árbol y construir el otro agregando elementos.

Daniel C. Sobral
fuente
3
@Radu: hay un error en la función de edición de comentarios. Si usa látex en un comentario y edita el comentario, verá un comportamiento extraño, como duplicación, etc.
Aryabhata
@Radu Agregué un par de párrafos para explicar mejor mi pregunta.
Daniel C. Sobral
¿Los árboles son inmutables?
Tsuyoshi Ito
Además, ¿te refieres al límite superior en lugar del límite inferior en el último párrafo?
Tsuyoshi Ito
2
Parece que la operación de división en árboles rojo-negros se puede implementar en el peor de los casos O (log n), donde n es el número de elementos en un árbol. Esta afirmación se puede encontrar en la introducción del documento "Listas ordenadas catenables de tiempo constante en el peor de los casos puramente funcional" por Gerth Stølting Brodal, Christos Makris y Kostas Tsichlas, ESA 2006: cs.au.dk/~gerth/pub/esa06trees.html . Como mencioné en mi comentario anterior, esto permite una implementación de tiempo de O (log n) en el peor de los casos de la operación de subrango.
Tsuyoshi Ito

Respuestas:

10

Esta respuesta combina algunos de mis comentarios a la pregunta y los expande.

La operación de subrango en árboles rojo-negros se puede realizar en el peor de los casos O (log n), donde n es el número de elementos en el árbol original. Dado que el árbol resultante compartirá algunos nodos con el árbol original, este enfoque es adecuado solo si los árboles son inmutables (o los árboles son mutables, pero el árbol original ya no es necesario).

Primero observe que la operación de subrango puede implementarse mediante dos operaciones divididas. Aquí la operación de división toma un árbol rojo-negro T y una tecla x y produce dos árboles L y R de modo que L consista en todos los elementos de T menores que x y R los elementos de T mayores que x. Por lo tanto, nuestro objetivo ahora es implementar la operación de división en árboles rojo-negros en el peor de los casos O (log n).

¿Cómo realizamos la operación de división en árboles rojo-negros en tiempo O (log n)? Bueno, resultó que había un método bien conocido. (No lo sabía, pero no soy un experto en estructuras de datos). Considere la operación de unión , que toma dos árboles L y R de tal manera que cada valor en L es menor que cada valor en R y produce un árbol que consiste en todos los valores en L y R. La operación de unión se puede implementar en el peor de los casos O (| r L −r R | +1), donde r L y r Rson los rangos de L y R, respectivamente (es decir, el número de nodos negros en el camino desde la raíz hasta cada hoja). La operación de división se puede implementar utilizando la operación de unión O (log n) veces, y el tiempo total en el peor de los casos sigue siendo O (log n) considerando una suma telescópica.

Las secciones 4.1 y 4.2 de un libro [Tar83] de Tarjan describen cómo implementar las operaciones de unión y división en árboles rojo-negros en el peor de los casos O (log n). Estas implementaciones destruyen árboles originales, pero es fácil convertirlos en implementaciones funcionales inmutables copiando nodos en lugar de modificarlos.

Como nota al margen, los módulos Set y Map de Objective Caml proporcionan la operación dividida, así como otras operaciones estándar en árboles de búsqueda binarios balanceados (inmutables). Aunque no usan árboles rojo-negros (usan árboles de búsqueda binarios balanceados con la restricción de que la altura izquierda y la altura derecha difieren en un máximo de 2), mirar sus implementaciones también podría ser útil. Aquí está la implementación del módulo Set .

Referencias

[Tar83] Robert Endre Tarjan. Estructuras de datos y algoritmos de red . Volumen 44 de la serie de conferencias regionales CBMS-NSF en matemáticas aplicadas , SIAM, 1983.

Tsuyoshi Ito
fuente
@Radu GRIGore: Sí, a menos que me falte algo.
Tsuyoshi Ito
@Radu GRIGore: O tal vez no, ahora no estoy seguro. Esta implementación de la operación dividida asigna O (log n) nuevos nodos para el árbol de salida, pero creo que toda la operación probablemente se puede implementar de forma recursiva, requiriendo solo espacio de trabajo O (1). Si esto es correcto, la respuesta a su pregunta dependerá de lo que quiera decir con "espacio extra".
Tsuyoshi Ito
@Radu GRIGore: En ese caso, creo que el espacio extra es O (1), aunque no lo he verificado con cuidado.
Tsuyoshi Ito
@Radu GRIGore: No puedo ver la razón por la que a uno le importa la cantidad de espacio de trabajo sin preocuparme por la cantidad de espacio necesario para almacenar el resultado en sí. En la teoría de la complejidad, el problema generalmente especifica cuál es el resultado y, por lo tanto, el espacio necesario para almacenar el resultado no depende de algoritmos. Sin embargo, en el problema actual, hay muchas formas de implementar la operación requerida y algunas implementaciones necesitan más espacio para almacenar el resultado que otras. Si ignora la diferencia de esta cantidad de espacio, no veo por qué le importa cuánto espacio de trabajo necesitamos.
Tsuyoshi Ito
El problema para los árboles inmutables es diferente al de los árboles mutables. Entiendo la diferencia, así que no tenía nada que preguntar al respecto. Ahora, acercando uno de los dos problemas, hay dos aspectos a discutir: memoria y tiempo. No dijiste cuánta memoria usas y no me pareció obvio cuál es la respuesta, así que pregunté. No veo cómo esto te hizo pensar que ignoro la diferencia entre los dos problemas.
Radu GRIGore
8

La solución es no usar árboles rojo-negros. En árboles de visualización y árboles AVL, el código para dividir y unir es muy simple. Le remito a las siguientes URL con código java para los árboles de visualización y los árboles AVL que admiten esto. Vaya a la siguiente URL y consulte Set.java (árboles avl) y SplayTree.java (árboles splay).

ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/

--- Danny Sleator

Danny Sleator
fuente
55
¡Bienvenido al sitio, Danny!
Suresh Venkat
2
¿Cómo ayudará esto a modificar la implementación de Scala Red Black para admitir la subranging en menos de O(n)? No he preguntado qué tipo de árboles tienen implementaciones de subrango simples porque eso no es un problema que tengo. Esta respuesta, aunque bien intencionada, está fuera de tema e inútil para el problema en cuestión.
Daniel C. Sobral
6

(Esto está destinado a ser un comentario, pero soy demasiado nuevo para dejar un comentario).

Simplemente quiero señalar que también puede estar interesado en la operación de "escisión", que devuelve el subrango como un nuevo árbol y el árbol de entrada sin el subrango como otro. Sin embargo, debe tener control sobre la representación subyacente del árbol, ya que el método conocido se basa en enlaces de nivel. La escisión se ejecuta en el tiempo logarítmico al tamaño del árbol más pequeño , aunque en el sentido amortizado ("amortizado" es iirc, porque ya no tengo acceso al papel) Ver:

K. Hoffman, K. Mehlhorn, P. Rosenstiehl y RE Tarjan, Clasificación de secuencias de Jordan en tiempo lineal utilizando árboles de búsqueda vinculados por nivel, Información y control, 68 (1986), 170–184

PD: La cita anterior proviene de la redacción del informe de Seidel. Treaps también apoyan la escisión.

Maverick Woo
fuente
Este método supone que uno ya tiene punteros (o "dedos") a los dos límites.
jbapple
3

nm[a,b]

  1. O(lgn)aa
  2. O(m)
  3. O(m)

O(m+lgn)O(n+mlgm)

o(m)Ω(lgm)klgm

No resolví los detalles, por lo que no estoy seguro de cómo la contabilidad adicional afecta el tiempo de ejecución.

O(1)Ω(lgm)

Radu GRIGore
fuente
Pensando en esto, creo que podría obtener un recuento aproximado O(logn), con lo que podría evitar la matriz temporal.
Daniel C. Sobral
Puede obtener el recuento en O (lg n) almacenando tamaños de subárbol en sus raíces.
Radu GRIGore
... pero almacenar tamaños en los nodos va en contra del requisito de no usar espacio auxiliar, por lo que mi observación no aborda su preocupación por la memoria.
Radu GRIGore
1
Los árboles binarios se pueden reequilibrar perfectamente utilizando solo espacio adicional CONSTANTE (además del árbol en sí): eecs.umich.edu/~qstout/abs/CACM86.html
Jeffε
O(m+lgn)O(1)