Algoritmos de árboles basados ​​en uniones

En informática , los algoritmos de árboles basados ​​en uniones son una clase de algoritmos para árboles de búsqueda binarios autoequilibrados . Este marco tiene como objetivo diseñar algoritmos altamente paralelizados para varios árboles de búsqueda binarios equilibrados. El marco algorítmico se basa en una única operación join . ^[1] En este marco, la operación join captura todos los criterios de equilibrio de diferentes esquemas de equilibrio, y todas las demás funciones join 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-negros , árboles equilibrados por peso y treaps .

La operación de unión toma como entrada dos árboles binarios balanceados y del mismo esquema de balanceo, y una clave , y genera como salida un nuevo árbol binario balanceado cuyo recorrido en orden es el recorrido en orden de , luego 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 ordenamiento total en claves, debe satisfacer la condición de que todas las claves en sean menores que y todas las claves en sean mayores que . ${\displaystyle (L,k,R)}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle k}$ ${\displaystyle t}$ ${\displaystyle L}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle L}$ ${\displaystyle k}$ ${\displaystyle R}$ ${\displaystyle k}$

Historia

La operación de unión fue definida por primera vez por Tarjan ^[2] en árboles rojo-negros , que se ejecuta en tiempo logarítmico de peor caso. Más tarde, Sleator y Tarjan ^[3] describieron un algoritmo de unión para árboles splay que se ejecuta en tiempo logarítmico amortizado. Más tarde, Adams ^[4] extendió la unión a árboles con equilibrio de peso y lo utilizó para funciones rápidas de conjunto a conjunto, incluyendo unión , intersección y diferencia de conjuntos . En 1998, Blelloch y Reid-Miller extendieron la unión en treaps , y demostraron que el límite de las funciones de conjunto es para dos árboles de tamaño y , que es óptimo en el modelo de comparación. También plantearon el paralelismo en el algoritmo de Adams utilizando un esquema de divide y vencerás . En 2016, Blelloch et al. propusieron formalmente los algoritmos basados ​​en unión y formalizaron el algoritmo de unión para cuatro esquemas de equilibrio diferentes: árboles AVL , árboles rojo-negros , árboles con equilibrio de peso y treaps . En el mismo trabajo demostraron que los algoritmos de Adams sobre unión, intersección y diferencia son óptimos en los cuatro esquemas de equilibrio. ${\displaystyle O(m\log(1+{\tfrac {n}{m}}))}$ ${\displaystyle m}$ ${\displaystyle n(\geq m)}$

Unir algoritmos

La función join considera el reequilibrio del á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 subárbol izquierdo t ₁ , raíz k y subárbol derecho t ₂ . Supongamos que t ₁ es más pesado (este "más pesado" depende del esquema de equilibrio) que t ₂ (el otro caso es simétrico). Join sigue la columna vertebral derecha de t ₁ hasta un nodo c que está equilibrado con t ₂ . En este punto, se crea un nuevo nodo con hijo izquierdo c , raíz k y hijo derecho t ₂ para reemplazar a c. El nuevo nodo puede invalidar el invariante de equilibrio. Esto se puede solucionar con rotaciones. ${\displaystyle (t_{1},k,t_{2})}$

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 devuelve Nodo(l, k', T') de lo contrario  devuelve rotateLeft(Nodo(l, k', rotateRight(T'))) de lo contrario T' := joinRightAVL(c, k, T R ) T : = Nodo(l, k', T') si h(T') ≤ h(l) + 1 devuelve T de lo contrario  devuelve rotateLeft(T)función joinLeftAVL(T L , k, T R ) /* simétrico para joinRightAVL */función join(T L , k, T R ) si h(T L ) > h(T R ) + 1 devuelve joinRightAVL(T L , k, T R ) de lo contrario si h(T L ) > h(T L ) + 1 devuelve joinLeftAVL(T L , k, T R ) de lo contrario  devuelve Node(T L , k, T R )

Dónde:

• ${\displaystyle h(v)}$es la altura del nodo . ${\displaystyle v}$
• ${\displaystyle {\text{expose}}(v)}$extrae el hijo izquierdo , la clave y el hijo derecho del nodo en una tupla . ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,k,r)}$
• ${\displaystyle {\text{Node}}(l,k,r)}$crea un nodo con hijo izquierdo , clave y hijo derecho . ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$

El algoritmo de unión para árboles rojo-negros :

función joinRightRB(T L , k, T R ) si T L .color = negro y ĥ(T L ) = ĥ(T R ) devuelve Nodo(T L , ⟨k, rojo⟩, T R ) de lo contrario (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 devuelve rotateLeft(T') de lo contrario  devuelve T'función joinLeftRB(T L , k, T R ) /* simétrico para unirse a RightRB */función join(T L , k, T R ) si ĥ(T L ) > ĥ(T R ) T' := joinRightRB(T L , k, T R ) si (T'.color = rojo) y (T'.right.color = rojo) T'.color := negro devuelve T' de lo contrario si ĥ(T R ) > ĥ(T L ) /* simétrico */ de lo contrario, si T L .color = negro y T R = negro, devuelve Nodo(T L , ⟨k, rojo⟩, T R ) de lo contrario,  devuelve Nodo(T L , ⟨k, negro⟩, T R )

Dónde:

• ⁠ ⁠ ${\displaystyle {\hat {h}}(v)}$ es la altura negra del nodo . ${\displaystyle v}$
• ${\displaystyle {\text{expose}}(v)}$extrae el hijo izquierdo , la clave , el color y el hijo derecho del nodo en una tupla . ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,\langle k,c\rangle ,r)}$
• ⁠ ⁠ ${\displaystyle {\text{Node}}(l,\langle k,c\rangle ,r)}$ crea un nodo con hijo izquierdo , clave , color y hijo derecho . ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle c}$ ${\displaystyle r}$

El algoritmo de unión para árboles con equilibrio de peso :

función joinRightWB(T L , k, T R ) (l, k', c) := exponer(T L ) si w(T L ) = α w(T R ) devolver Nodo(T L , k, T R ) de lo contrario T' := unirDerechaWB(c, k, T R ) (l 1 , k 1 , r 1 ) := exponer(T') si w(l) = α w(T') devuelve Nodo(l, k', T') de lo contrario si w(l) = α w(l 1 ) y w(l)+w(l 1 ) = α w(r 1 ) devuelve rotarIzquierda(Nodo(l, k', T')) de lo contrario  devuelve rotarIzquierda(Nodo(l, k', rotarDerecha(T'))función joinLeftWB(T L , k, T R ) /* simétrico para unirse a RightWB */función join(T L , k, T R ) si w(T L ) > α w(T R ) retorna joinRightWB(T L , k, T R ) de lo contrario si w(T R ) > α w(T L ) retorna joinLeftWB(T L , k, T R ) de lo contrario  retorna Node(T L , k, T R )

Dónde:

• ${\displaystyle w(v)}$es el peso del nodo . ${\displaystyle v}$
• ${\displaystyle w_{1}=_{\alpha }w_{2}}$significa pesos y están equilibrados en peso α. ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$
• ${\displaystyle w_{1}>_{\alpha }w_{2}}$significa que el peso es más pesado que el peso con respecto al equilibrio de peso α. ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$
• ${\displaystyle {\text{expose}}(v)}$extrae el hijo izquierdo , la clave y el hijo derecho del nodo en una tupla . ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,k,r)}$
• ${\displaystyle {\text{Node}}(l,k,r)}$crea un nodo con hijo izquierdo , clave e hijo derecho . ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$

Algoritmos basados ​​en uniones

A continuación, extrae el hijo izquierdo , la clave y el hijo derecho del nodo en una tupla . crea un nodo con hijo izquierdo , clave y hijo derecho . " " significa que dos declaraciones y pueden ejecutarse en paralelo. ${\displaystyle {\text{expose}}(v)}$ ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,k,r)}$ ${\displaystyle {\text{Node}}(l,k,r)}$ ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle s_{1}||s_{2}}$ ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$

Dividir

Para dividir un árbol en dos árboles, aquellos más pequeños que la clave x y aquellos 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 izquierdo, 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. ${\displaystyle O(\log n)}$

El algoritmo de división es el siguiente:

función split(T, k) si (T = nulo) devuelve (nulo, falso, nulo) de lo contrario (L, m, R) := exponer(T) si k < m (L', b, R') := dividir(L, k) devuelve (L', b, join(R', m, R)) de lo contrario si k > m (L', b, R') := dividir(R, k) devuelve (join(L, m, L'), b, R')) de lo contrario  devuelve (L, true, R)

Unirse2

Esta función se define de forma similar a join pero sin la clave intermedia. Primero, divide la última clave del árbol izquierdo y luego une la parte restante del árbol izquierdo con el árbol derecho con . El algoritmo es el siguiente: ${\displaystyle k}$ ${\displaystyle k}$

función splitLast(T) (L, k, R) := exponer(T) si R = nulo devuelve (L, k) de lo contrario (T', k') := dividirÚltimo(R) devolver (unir(L, k, T'), k')función join2(L, R) si L = nulo devuelve R de lo contrario (L', k) := dividirÚltimo(L) devolver unirse(L', k, R)

El costo es para un árbol de tamaño . ${\displaystyle O(\log n)}$ ${\displaystyle n}$

Insertar y eliminar

Los algoritmos de inserción y eliminación, cuando se hace uso de join , pueden ser independientes de los esquemas de balanceo. Para una inserción, el algoritmo compara la clave que se va a insertar con la clave en la raíz, la inserta en el subárbol izquierdo/derecho si la clave es menor/mayor que la clave en la raíz y une los dos subárboles nuevamente con la raíz. Una eliminación compara la clave que se va a eliminar con la clave en la raíz. Si son iguales, devuelve join2 en los dos subárboles. De lo contrario, elimina la clave del subárbol correspondiente y une los dos subárboles nuevamente con la raíz. Los algoritmos son los siguientes:

función insertar(T, k) si T = nulo devuelve Nodo(nil, k, nulo) de lo contrario (L, k', R) := exponer(T) si k < k' retorna join(insert(L,k), k', R) de lo contrario si k > k' retorna join(L, k', insert(R, k)) de lo contrario  retorna Tfunción eliminar(T, k) si T = nulo devuelve nulo en caso contrario (L, k', R) := exponer(T) si k < k' retorna join(eliminar(L, k), k', R) de lo contrario si k > k' retorna join(L, k', eliminar(R, k)) de lo contrario  retorna join2(L, R)

Tanto la inserción como la eliminación requieren tiempo si . ${\displaystyle O(\log n)}$ ${\displaystyle |T|=n}$

Funciones conjunto-conjunto

Se han definido varias operaciones de conjuntos en árboles con ponderación equilibrada: unión , intersección y diferencia de conjuntos . La unión de dos árboles con ponderación equilibrada t ₁ y t ₂ que representan los conjuntos A y B es un árbol t que representa A ∪ B. La siguiente función recursiva calcula esta unión:

función unión(t 1 , t 2 ) si t 1 = nulo devuelve t 2  de lo contrario si t 2 = nulo devuelve t 1  de lo contrario (l 1 , k 1 , r 1 ) := exponer(t 1 ) (t < , b, t > ) := dividir(t 2 , k 1 ) l' := unión(l 1 , t < ) || r' := unión(r 1 , t > ) devolver unión(l', k 1 , r')

De manera similar, los algoritmos de intersección y diferencia de conjuntos son los siguientes:

función intersección(t 1 , t 2 ) si t 1 = nulo o t 2 = nulo devuelve nulo de lo contrario (l 1 , k 1 , r 1 ) := exponer(t 1 ) (t < , b, t > ) = dividir(t 2 , k 1 ) l' := intersección(l 1 , t < ) || r' := intersección(r 1 , t > ) si b devuelve join(l', k 1 , r') de lo contrario  devuelve join2(l', r')función diferencia(t 1 , t 2 ) si t 1 = nulo devuelve nulo de lo contrario si t 2 = nulo devuelve t 1  de lo contrario (l 1 , k 1 , r 1 ) := exponer(t 1 ) (t < , b, t > ) := dividir(t 2 , k 1 ) l' = diferencia(l 1 , t < ) || r' = diferencia(r 1 , t > ) si b devuelve join2(l', r') de lo contrario  devuelve join(l', k 1 , r')

La complejidad de cada una de las uniones, intersecciones y diferencias es para dos árboles con pesos equilibrados de tamaños y . Esta complejidad es óptima en términos de la cantidad de comparaciones. Más importante aún, dado que las llamadas recursivas a uniones, intersecciones o diferencias 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 se usa la raíz del árbol más grande para dividir el árbol más pequeño. ${\displaystyle O\left(m\log \left({\tfrac {n}{m}}+1\right)\right)}$ ${\displaystyle m}$ ${\displaystyle n(\geq m)}$ ${\displaystyle O(\log m\log n)}$ ${\displaystyle m=1}$

Construir

El algoritmo para construir un árbol puede utilizar el algoritmo de unión y utilizar el esquema de dividir y vencer:

función construir(A[], n) si n = 0 devuelve nil de lo contrario si n = 1 devuelve Nodo(nil, A[0], nil) de lo contrario l' := construir(A, n/2) || r' := (A+n/2, nn/2) Unión de retorno (L, R)

Este algoritmo requiere trabajo y tiene profundidad. Un algoritmo más eficiente utiliza un algoritmo de ordenamiento paralelo. ${\displaystyle O(n\log n)}$ ${\displaystyle O(\log ^{3}n)}$

función buildSorted(A[], n) si n = 0 devuelve nil de lo contrario si n = 1 devuelve Node(nil, A[0], nil) de lo contrario l' := construir(A, n/2) || r' := (A+n/2+1, nn/2-1) devolver unión(l', A[n/2], r')función construir(A[], n) A' := ordenar(A, n) devuelve buildSorted(A, n)

Este algoritmo cuesta trabajo y tiene profundidad, asumiendo que el algoritmo de clasificación tiene trabajo y profundidad. ${\displaystyle O(n\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(\log n)}$

Filtrar

Esta función selecciona todas las entradas de un árbol que satisfacen un predicado y devuelve un árbol que contiene todas las entradas seleccionadas. Filtra de forma recursiva los dos subárboles y los une con la raíz si esta satisface ; de lo contrario, une2 los dos subárboles. ${\displaystyle p}$ ${\displaystyle p}$

función filter(T, p) si T = nulo devuelve nulo en caso contrario (l, k, r) := exponer(T) l' := filtro(l, p) || r' := filtro(r, p) si p(k) devuelve join(l', k, r') de lo contrario  devuelve join2(l', R)

Este algoritmo cuesta trabajo y profundidad en un árbol de tamaño , asumiendo que tiene un costo constante. ${\displaystyle O(n)}$ ${\displaystyle O(\log ^{2}n)}$ ${\displaystyle n}$ ${\displaystyle p}$

Utilizado en bibliotecas

Los algoritmos basados ​​en uniones se aplican para soportar interfaces para conjuntos , mapas y mapas aumentados ^[5] en bibliotecas como Hackage , SML/NJ y PAM . ^[5]

Notas

Referencias

1. Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Simposio sobre algoritmos y arquitecturas paralelas, Actas del 28.º Simposio de la ACM sobre 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
2. Tarjan, Robert Endre (1983), "Estructuras de datos y algoritmos de red", Estructuras de datos y algoritmos de red , Siam, págs. 45-56
3. Sleator, Daniel Dominic; Tarjan, Robert Endre (1985), "Árboles de búsqueda binarios autoajustables", Journal of the ACM , Siam
4. Adams, Stephen (1992), "Implementación eficiente de conjuntos en un lenguaje funcional", Implementación eficiente de conjuntos en un lenguaje funcional , Citeseer, CiteSeerX 10.1.1.501.8427 .
5. Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018), "PAM: mapas aumentados paralelos", Actas del 23.º Simposio SIGPLAN de la ACM sobre principios y prácticas de programación paralela , ACM, págs. 290-304

Enlaces externos

• PAM, la biblioteca de mapas aumentada paralela
• Hackage, contenedores en Hackage