En informática , los algoritmos de árbol basados en uniones son una clase de algoritmos para árboles de búsqueda binaria autoequilibrados . Este marco tiene como objetivo diseñar algoritmos altamente paralelizados para varios árboles de búsqueda binarios balanceados. El marco algorítmico se basa en una única operación conjunta . [1] Bajo este marco, la operación de unión captura todos los criterios de equilibrio de diferentes esquemas de equilibrio, y todas las demás funciones de unión tienen una implementación genérica en diferentes esquemas de equilibrio. Los algoritmos basados en uniones se pueden aplicar a al menos cuatro esquemas de equilibrio: árboles AVL , árboles rojo-negro, árboles y treaps de peso equilibrado .
La unión la operación toma como entrada dos árboles binarios balanceados y del mismo esquema de equilibrio, y una clave , y genera un nuevo árbol binario balanceado cuyo recorrido en orden es el recorrido en orden de, luego entonces el recorrido en orden de . En particular, si los árboles son árboles de búsqueda , lo que significa que el orden de los árboles mantiene un orden total en las claves, debe satisfacer la condición de que todas las claves en son más pequeños que y todas las llaves en son mayores que .
Historia
La operación de unión fue definida por primera vez por Tarjan [2] en árboles rojo-negro , que se ejecuta en el peor de los casos logarítmicos. Más tarde, Sleator y Tarjan [3] describieron un algoritmo de unión para árboles de splay que se ejecuta en tiempo logarítmico amortizado. Más tarde, Adams [4] extendió la unión a árboles con balance de peso y la usó para funciones de conjunto-conjunto rápidas que incluyen unión , intersección y diferencia de conjunto . En 1998, Blelloch y Reid-Miller ampliaron la combinación en treaps y demostraron que el límite de las funciones de conjunto era para dos árboles de tamaño y , que es óptimo en el modelo de comparación. También mencionaron el paralelismo en el algoritmo de Adams mediante el uso de un esquema de divide y vencerás . En 2016, Blelloch et al. propuso formalmente los algoritmos basados en unión y formalizó el algoritmo de unión para cuatro esquemas de equilibrio diferentes: árboles AVL , árboles rojo-negro , árboles de peso equilibrado y treaps . En el mismo trabajo, demostraron que los algoritmos de Adams sobre unión, intersección y diferencia son óptimos para el trabajo en los cuatro esquemas de equilibrio.
Unir algoritmos
La función unirseconsidera reequilibrar el árbol y, por lo tanto, depende del esquema de equilibrio de entrada. Si los dos árboles están equilibrados, join simplemente crea un nuevo nodo con el subárbol izquierdo t 1 , la raíz k y el subárbol derecho t 2 . Suponga que t 1 es más pesado (este "más pesado" depende del esquema de equilibrio) que t 2 (el otro caso es simétrico). La unión sigue la espina dorsal derecha de t 1 hasta un nodo c que está equilibrado con t 2 . En este punto, se crea un nuevo nodo con el hijo izquierdo c , la raíz k y el hijo derecho t 2 para reemplazar c. El nuevo nodo puede invalidar el invariante de equilibrio. Esto se puede arreglar con rotaciones.
A continuación se muestran los algoritmos de unión en diferentes esquemas de equilibrio.
El algoritmo de unión para árboles AVL :
función joinRightAVL (T L , k, T R ) (l, k ', c) = exponer (T L ) si (h (c) <= h (T R ) + 1) T '= Nodo (c, k, T R ) si (h (T ') <= h (l) + 1) entonces devuelve Node (l, k', T ') else return rotateLeft (Node (l, k ', rotateRight (T'))) else T '= joinRightAVL (c, k, T R ) T = Nodo (l, k ', T') si (h (T ') <= h (l) + 1) devuelve T else return rotateLeft (T ) función joinLeftAVL (T L , k, T R ) / * simétrico para joinRightAVL * /función join (T L , k, T R ) if (h (T L )> h (T R ) + 1) return joinRightAVL (T L , k, T R ) if (h (T R )> h (T L ) + 1) return joinLeftAVL (T L , k, T R ) return Node (T L , k, T R )
Aquí de un nodo la altura de . exponer (v) = (l, k, r) significa extraer un nodo de árbolhijo dejado , la clave del nodo y el niño adecuado . Node (l, k, r) significa crear un nodo de hijo izquierdo, clave , y el niño correcto .
El algoritmo de unión para árboles rojo-negro :
función joinRightRB (T L , k, T R ) si r (T L ) = ⌊r (T L ) / 2⌋ × 2: return Node (T L , ⟨k, red⟩, T R ) else (L ', ⟨K ', c'⟩, R') = exponer (T L ) T '= Nodo (L', ⟨k ', c'⟩, joinRightRB (R', k, T R ) si (c '= negro) y (T'.right.color = T'.right.right.color = rojo): T'.right.right.color = negro return rotateLeft (T ') else return T' function joinLeftRB (T L , k, T R ) / * simétrico para joinRightRB * /función join (T L , k, T R ) si ⌊r (T L ) / 2⌋> ⌊r (T R ) / 2⌋ × 2: T '= joinRightRB (T L , k, T R ) si (T'.color = red) y (T'.right.color = red): T'.color = negro volver T ' de lo contrario, si ⌊r (T L ) / 2⌋> ⌊r (T L ) / 2⌋ × 2 / * simétrico * / si no (T L .color = negro) y (T R = negro) Nodo (T L , ⟨k, red⟩, T R ) más Nodo (T L , ⟨k, black⟩, T R )
Aquí de un nodo significa el doble de la altura negra de un nodo negro y el doble de la altura negra de un nodo rojo. exponer (v) = (l, ⟨k, c⟩, r) significa extraer un nodo de árbolhijo dejado , la clave del nodo , el color del nodo y el niño adecuado . Node (l, ⟨k, c⟩, r) significa crear un nodo de hijo izquierdo, clave , color y niño correcto .
El algoritmo de unión para árboles con peso equilibrado :
función joinRightWB (T L , k, T R ) (l, k ', c) = exponer (T L ) if balance (| T L |, | T L |) return Node (T L , k, T R ) else T' = joinRightWB (c, k, T R ) (l 1 , k 1 , r 1 ) = exponer (T ') if (balance (l, T')) return Node (l, k ', T') else if (balance (| l |, | l 1 | ) y balance (| l | + | l 1 |, | r 1 |)) return rotateLeft (Node (l, k ', T')) else return rotateLeft (Node (l, k ', rotateRight (T')) función joinLeftWB (T L , k, T R ) / * simétrico para joinRightWB * /función join (T L , k, T R ) if (heavy (T L , T R )) return joinRightWB (T L , k, T R ) if (heavy (T R , T L )) return joinLeftWB (T L , k, T R ) Nodo (T L , k, T R )
Aquí equilibrio significa dos pesos y están equilibrados. exponer (v) = (l, k, r) significa extraer un nodo de árbolhijo dejado , la clave del nodo y el niño adecuado . Node (l, k, r) significa crear un nodo de hijo izquierdo, clave y niño correcto .
Algoritmos basados en uniones
A continuación, exponer (v) = (l, k, r) significa extraer un nodo de árbol hijo dejado , la clave del nodo y el niño adecuado . Node (l, k, r) significa crear un nodo de hijo izquierdo, clave y niño correcto . derecho() E izquierda() extrae el hijo derecho y el hijo izquierdo de un nodo de árbol, respectivamente. extraer la clave de un nodo . Muchos de los algoritmos basados en combinaciones son paralelos. ""significa que dos declaraciones y puede funcionar en paralelo.
Separar
Para dividir un árbol en dos árboles, los más pequeños que la clave x y los más grandes que la clave x , primero dibujamos una ruta desde la raíz insertando x en el árbol. Después de esta inserción, todos los valores menores que x se encontrarán a la izquierda de la ruta, y todos los valores mayores que x se encontrarán a la derecha. Al aplicar Join , todos los subárboles del lado izquierdo se fusionan de abajo hacia arriba usando claves en la ruta como nodos intermedios de abajo hacia arriba para formar el árbol de la izquierda, y la parte derecha es asimétrica. Para algunas aplicaciones, Split también devuelve un valor booleano que indica si x aparece en el árbol. El costo de Split es, orden de la altura del árbol.
El algoritmo de división es el siguiente:
función split (T, k) if (T = nil) return (nil, false, nil) (L, m, R) = exponer (T) si (k = m) devuelve (L, verdadero, R) si (k) (L ', b, R') = dividir (L, k) return (L ', b, join (R', m, R)) si (k> m) (L ', b, R') = dividir (R, k) volver (unirse (L, m, L '), b, R'))
Join2
Esta función se define de forma similar a join pero sin la tecla del medio. Primero divide la última clave del árbol de la izquierda, y luego une la parte restante del árbol de la izquierda con el árbol de la derecha con . El algoritmo es como sigue:
función splitLast (T) (L, k, R) = exponer (T) si (R = nulo) devuelve (L, k) (T ', k') = splitLast (R) return (join (L, k, T '), k') función join2 (L, R) if (L = nil) return R (L ', k) = splitLast (L) volver unirse (L ', k, R)
El precio es para un árbol de tamaño .
Insertar y eliminar
Los algoritmos de inserción y eliminación, al hacer uso de la combinación, pueden ser independientes de los esquemas de equilibrio. Para una inserción, el algoritmo compara la clave que se insertará con la clave en la raíz, la inserta en el subárbol izquierdo / derecho si la clave es más pequeña / mayor que la clave en la raíz y une los dos subárboles con la raíz. . Una eliminación compara la clave que se eliminará con la clave en la raíz. Si son iguales, devuelve join2 en los dos subárboles. De lo contrario, elimine la clave del subárbol correspondiente y vuelva a unir los dos subárboles con la raíz. Los algoritmos son los siguientes:
función insertar (T, k) si (T = nil) return Node (nil, k, nil) (L, k ', R) = exponer (T) if (kreturn join (insert (L, k), k', R) if (k> k ') return join (L, k', insert (R, k)) return T función eliminar (T , k) si (T = nil) devuelve nil (L, k ', R) = exponer (T) if (k return join (eliminar (L, k), k', R) if (k> k ') return join (L, k', delete (R, k)) return join2 (L, R )
Tanto la inserción como la eliminación requieren tiempo si .
Funciones set-set
Se han definido varias operaciones de conjuntos en árboles de peso equilibrado: unión , intersección y diferencia de conjuntos . La unión de dos árboles de equilibrado de peso- T 1 y T 2 que representa conjuntos A y B , es un árbol t que representa A ∪ B . La siguiente función recursiva calcula esta unión:
unión de funciones (t 1 , t 2 ): si t 1 = nil: devuelve t 2 si t 2 = nil: devuelve t 1 (t < , b, t > ) = divide t 2 en t 1 .root nl = unión (izquierda (t 1 ), t < ) || nr = union (right (t 1 ), t > ) return join (nl, t 1 .root, nr)
De manera similar, los algoritmos de intersección y diferencia de conjuntos son los siguientes:
intersección de funciones (t 1 , t 2 ): si (t 1 = nil o t 2 = nil) devuelve nil (t < , b, t > ) = dividir t 2 en t 1 .root nl = intersección (izquierda (t 1 ), t < ) || nr = intersección (right (t 1 ), t > ) if (b) return join (nl, t 1 .root, nr) else return join2 (nl, nr) función diferencia (t 1 , t 2 ): if (t 1 = nil) devuelve nil si (t 2 = nil) devuelve t 1 (t < , b, t > ) = divide t 2 en t 1 .root nl = diferencia (izquierda (t 1 ), t < ) || nr = diferencia (derecha (t 1 ), t > ) return join2 (nl, nr)
La complejidad de cada unión, intersección y diferencia es para dos árboles de tamaño equilibrado en peso y . Esta complejidad es óptima en términos del número de comparaciones. Más importante aún, dado que las llamadas recursivas a unión, intersección o diferencia son independientes entre sí, se pueden ejecutar en paralelo con una profundidad paralela. . [1] Cuando, la implementación basada en uniones aplica el mismo cálculo que en una inserción o eliminación de un solo elemento si la raíz del árbol más grande se usa para dividir el árbol más pequeño.
Construir
El algoritmo para construir un árbol puede hacer uso del algoritmo de unión y usar el esquema de divide y vencerás:
función build (A [], n): if (n = 0) return nil if (n = 1) return Node (nil, A [0], nil) L = construcción (A, n / 2) || R = (A + n / 2, nn / 2) unión de retorno (L, R)
Este algoritmo cuesta trabaja y tiene profundidad. Un algoritmo más eficiente utiliza un algoritmo de clasificación en paralelo.
función buildSorted (A [], n): if (n = 0) return nil if (n = 1) return Node (nil, A [0], nil) L = construcción (A, n / 2) || R = (A + n / 2 + 1, nn / 2-1) return join (L, A [n / 2], R) función build (A [], n): A '= ordenar (A, n) devolver buildSorted (A, n)
Este algoritmo cuesta trabaja y tiene profundidad asumiendo que el algoritmo de clasificación tiene trabaja y profundidad.
Filtrar
Esta función selecciona todas las entradas en un árbol que satisfacen un indicador y devuelve un árbol que contiene todas las entradas seleccionadas. Filtra recursivamente los dos subárboles y los une con la raíz si la raíz satisface, de lo contrario une2 los dos subárboles.
función filtro (T, f): si (T = nil) devuelve nil L = filtro (izquierda (T), f) || R = (derecha (T), f) if (f (k (T)) return join (L, k (T), R) de lo contrario regresa join2 (L, R)
Este algoritmo cuesta trabajo y profundidad en un árbol de tamaño , asumiendo tiene costo constante.
Utilizado en bibliotecas
Los algoritmos basados en uniones se aplican para admitir interfaces para conjuntos , mapas y mapas aumentados [5] en bibliotecas como Hackage , SML / NJ y PAM . [5]
Notas
Referencias
- ^ a b Blelloch, Guy E .; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Simposio sobre arquitecturas y algoritmos paralelos, Proc. de 28a ACM Symp. Algoritmos y arquitecturas paralelas (SPAA 2016) , ACM, págs. 253–264, arXiv : 1602.02120 , doi : 10.1145 / 2935764.2935768 , ISBN 978-1-4503-4210-0
- ^ Tarjan, Robert Endre (1983), "Estructuras de datos y algoritmos de red", Estructuras de datos y algoritmos de red , Siam, págs. 45–56
- ^ Sleator, Daniel Dominic; Tarjan, Robert Endre (1985), "Árboles de búsqueda binarios autoajustables", Journal of the ACM , Siam
- ^ Adams, Stephen (1992), "Implementar conjuntos de manera eficiente en un lenguaje funcional", Implementar conjuntos de manera eficiente en un lenguaje funcional , Citeseer, CiteSeerX 10.1.1.501.8427.
- ^ a b Blelloch, Guy E .; Ferizovic, Daniel; Sun, Yihan (2018), "PAM: mapas aumentados paralelos", Actas del 23º Simposio ACM SIGPLAN sobre Principios y Práctica de la Programación Paralela , ACM, págs. 290–304
enlaces externos
- PAM , la biblioteca de mapas aumentada paralela
- Hackage , contenedores en Hackage