Algoritmos de árbol basados ​​en uniones

En ciencias de la computación , los algoritmos de árbol basados ​​en unión 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 binaria equilibrados. El marco algorítmico se basa en una única operación de unión . ^{[ 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 unión se pueden aplicar a al menos cuatro esquemas de equilibrio: árboles AVL , árboles rojo-negro , árboles equilibrados por peso y treaps .

La unión${\displaystyle (L,k,R)}$La operación toma como entrada dos árboles binarios equilibrados.${\displaystyle L}$y${\displaystyle R}$del mismo esquema de equilibrio y una clave${\displaystyle k}$y genera un nuevo árbol binario equilibrado.${\displaystyle t}$cuyo recorrido en orden es el recorrido en orden de${\displaystyle L}$, entonces${\displaystyle k}$luego el recorrido en orden de${\displaystyle R}$. 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${\displaystyle L}$son más pequeños que${\displaystyle k}$y todas las llaves en${\displaystyle R}$son mayores que${\displaystyle k}$.

La operación de unión fue definida por primera vez por Tarjan ^{[ 2 ]} en árboles rojo-negro , que se ejecuta en tiempo logarítmico en el peor de los casos. Posteriormente, 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 operación de unión a árboles con peso equilibrado y la utilizó para funciones rápidas de conjuntos, incluyendo unión , intersección y diferencia de conjuntos . En 1998, Blelloch y Reid-Miller extendieron la operación de unión a treaps y demostraron que la cota de las funciones de conjuntos es${\displaystyle O(m\log(1+{\tfrac {n}{m}}))}$para dos árboles de tamaño${\displaystyle m}$y${\displaystyle n(\geq m)}$, que es óptimo en el modelo de comparación. También mencionaron el paralelismo en el algoritmo de Adams mediante un esquema de divide y vencerás . En 2016, Blelloch et al. propusieron formalmente los algoritmos basados ​​en la unión y formalizaron el algoritmo de unión para cuatro esquemas de balance diferentes: árboles AVL , árboles rojo-negro , árboles con balance de peso y treaps . En el mismo trabajo demostraron que los algoritmos de Adams sobre unión, intersección y diferencia son óptimos en términos de trabajo en los cuatro esquemas de balance.

La función unir${\displaystyle (t_{1},k,t_{2})}$Considera 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 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 e hijo derecho t ₂ para reemplazar a c. El nuevo nodo puede invalidar el invariante de equilibrio. Esto se puede corregir con rotaciones.

A continuación se muestran los algoritmos de unión en diferentes esquemas de balanceo.

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 devolver Nodo(l, k', T') si no devolver rotarIzquierda(Nodo(l, k', rotarDerecha(T'))) si no T' := unirDerechaAVL(c, k, T R ) T : = Nodo(l, k', T') si h(T') ≤ h(l) + 1 devolver T sino devolver rotateLeft(T) función joinLeftAVL(T L , k, T R ) /* simétrico a joinRightAVL */ función join(T L , k, T R ) si h(T L ) > h(T R ) + 1 devolver joinRightAVL(T L , k, T R ) sino si h(T R ) > h(T L ) + 1 devolver joinLeftAVL(T L , k, T R ) sino devolver Node(T L , k, T R )

Dónde:

• ${\displaystyle h(v)}$es la altura del nodo${\displaystyle v}$.
• ${\displaystyle {\text{exponer}}(v)}$extrae al niño izquierdo${\displaystyle l}$, llave${\displaystyle k}$y el niño derecho${\displaystyle r}$del nodo${\displaystyle v}$en una tupla${\displaystyle (l,k,r)}$.
• ${\displaystyle {\text{Nodo}}(l,k,r)}$crea un nodo con hijo izquierdo${\displaystyle l}$, llave${\displaystyle k}$y el niño derecho${\displaystyle r}$.

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

función joinRightRB(T L , k, T R ) si T L .color = negro y ĥ(T L ) = ĥ(T R ) devolver Nodo(T L , ⟨k, rojo⟩, T R ) de lo contrario (L', ⟨k', c'⟩, R') := exponer(T L ) T' := Nodo(L', ⟨k', c'⟩, unirDerechaRB(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 unirLeftRB(T L , k, T R ) /* simétrico a joinRightRB */ función unir(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 devolver T' si no, si ĥ(T R ) > ĥ(T L ) /* simétrico */ else if T L .color = black and T R = black return Node(T L , ⟨k, red⟩, T R ) else return Node(T L , ⟨k, black⟩, T R )

Dónde:

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

El algoritmo de unión para árboles con ponderación equilibrada :

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 ) := expose(T') si w(l) = α w(T') devolver Nodo(l, k', T') si no, si w(l) = α w(l 1 ) y w(l)+w(l 1 ) = α w(r 1 ) devolver rotateLeft(Nodo(l, k', T')) si no, devolver rotateLeft(Nodo(l, k', rotateRight(T')) función unirIzquierdaWB(T L , k, T R ) /* simétrico a joinRightWB */ función join(T L , k, T R ) si w(T L ) > α w(T R ) devolver joinRightWB(T L , k, T R ) sino si w(T R ) > α w(T L ) devolver joinLeftWB(T L , k, T R ) sino devolver 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${\displaystyle w_{1}}$y${\displaystyle w_{2}}$están equilibrados en peso α.
• ${\displaystyle w_{1}>_{\alpha }w_{2}}$significa peso${\displaystyle w_{1}}$es más pesado que peso${\displaystyle w_{2}}$con respecto al equilibrio de peso α.
• ${\displaystyle {\text{exponer}}(v)}$extrae al niño izquierdo${\displaystyle l}$, llave${\displaystyle k}$y el niño derecho${\displaystyle r}$del nodo${\displaystyle v}$en una tupla${\displaystyle (l,k,r)}$.
• ${\displaystyle {\text{Nodo}}(l,k,r)}$crea un nodo con hijo izquierdo${\displaystyle l}$, llave${\displaystyle k}$y el niño derecho${\displaystyle r}$.

A continuación,${\displaystyle {\text{exponer}}(v)}$extrae al niño izquierdo${\displaystyle l}$, llave${\displaystyle k}$y el niño derecho${\displaystyle r}$del nodo${\displaystyle v}$en una tupla${\displaystyle (l,k,r)}$.${\displaystyle {\text{Nodo}}(l,k,r)}$crea un nodo con hijo izquierdo${\displaystyle l}$, llave${\displaystyle k}$y el niño derecho${\displaystyle r}$. "${\displaystyle s_{1}||s_{2}}$" significa que dos afirmaciones${\displaystyle s_{1}}$y${\displaystyle s_{2}}$pueden ejecutarse en paralelo.

función split(T, k) si (T = nil) devolver (nil, falso, nil) de lo contrario (L, m, R) := exponer(T) si k < m (L', b, R') := split(L, k) devolver (L', b, unir(R', m, R)) de lo contrario si k > m (L', b, R') := split(R, k) Devuelve (join(L, m, L'), b, R')) de lo contrario, devuelve (L, verdadero, R)

función splitLast(T) (L, k, R) := exponer(T) si R = nil devolver (L, k) de lo contrario (T', k') := splitLast(R) devolver (unir(L, k, T'), k') función join2(L, R) si L = nil devolver R sino (L', k) := splitLast(L) devolver unir(L', k, R)

función insertar(T, k) si T = nil devolver Nodo(nil, k, nil) de lo contrario (L, k', R) := exponer(T) Si k < k', devuelve join(insertar(L,k), k', R) ; de lo contrario, si k > k', devuelve join(L, k', insertar(R, k)) ; de lo contrario , devuelve T. función delete(T, k) si T = nil devolver nil sino (L, k', R) := exponer(T) Si k < k', devuelve join(delete(L, k), k', R) ; de lo contrario, si k > k', devuelve join(L, k', delete(R, k)); de lo contrario, devuelve join2(L, R).

función unión(t 1 , t 2 ) si t 1 = nil devolver t 2 sino si t 2 = nil devolver t 1 sino (l 1 , k 1 , r 1 ) := exponer(t 1 ) (t < , b, t > ) := split(t 2 , k 1 ) l' := unión(l 1 , t < ) || r' := unión(r 1 , t > ) return unión(l', k 1 , r')

función intersección(t 1 , t 2 ) si t 1 = nil o t 2 = nil devolver nil sino (l 1 , k 1 , r 1 ) := exponer(t 1 ) (t < , b, t > ) = split(t 2 , k 1 ) l' := intersección(l 1 , t < ) || r' := intersección(r 1 , t > ) si b devuelve unir(l', k 1 , r') sino devuelve unir2(l', r') función diferencia(t 1 , t 2 ) si t 1 = nil devolver nil sino si t 2 = nil devolver t 1 sino (l 1 , k 1 , r 1 ) := exponer(t 1 ) (t < , b, t > ) := split(t 2 , k 1 ) l' = diferencia(l 1 , t < ) || r' = diferencia(r 1 , t > ) si b devuelve join2(l', r') sino devuelve join(l', k 1 , r')

función construir(A[], n) si n = 0 devolver nil sino si n = 1 devolver Nodo(nil, A[0], nil) sino l' := construir(A, n/2) || r' := (A+n/2, nn/2) devolver unión(L, R)

función buildSorted(A[], n) si n = 0 devuelve nil sino si n = 1 devuelve Node(nil, A[0], nil) sino l' := construir(A, n/2) || r' := (A+n/2+1, nn/2-1) devolver unir(l', A[n/2], r') función construir(A[], n) A' := sort(A, n) devolver buildSorted(A, n)

función filter(T, p) si T = nil devolver nil sino (l, k, r) := exponer(T) l' := filter(l, p) || r' := filter(r, p) si p(k) devuelve join(l', k, r') de lo contrario devuelve join2(l', R)

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 ]}

• PAM , la biblioteca de mapas aumentados paralelos
• Hackage , contenedores en Hackage