Árbol de peso equilibrado

En informática , los árboles binarios de equilibrio de peso ( WBT ) son un tipo de árboles binarios de búsqueda autoequilibrados que se pueden utilizar para implementar conjuntos dinámicos , diccionarios (mapas) y secuencias. ^[1] Estos árboles fueron introducidos por Nievergelt y Reingold en la década de 1970 como árboles de equilibrio acotado o árboles BB[α] . ^{[2] [3]} Su nombre más común se debe a Knuth . ^[4]

Un ejemplo bien conocido es la codificación Huffman de un corpus .

Al igual que otros árboles autoequilibrados, los WBT almacenan información contable relativa al equilibrio en sus nodos y realizan rotaciones para restablecer el equilibrio cuando éste se ve alterado por operaciones de inserción o eliminación. En concreto, cada nodo almacena el tamaño del subárbol con raíz en el nodo, y los tamaños de los subárboles izquierdo y derecho se mantienen dentro de algún factor entre sí. A diferencia de la información de equilibrio en los árboles AVL (que utilizan información sobre la altura de los subárboles) y los árboles rojo-negros (que almacenan un bit de "color" ficticio), la información contable en un WBT es una propiedad realmente útil para las aplicaciones: el número de elementos en un árbol es igual al tamaño de su raíz, y la información de tamaño es exactamente la información necesaria para implementar las operaciones de un árbol estadístico de orden , es decir, obtener el n -ésimo elemento más grande de un conjunto o determinar el índice de un elemento en orden ordenado. ^[5]

Los árboles con equilibrio de peso son populares en la comunidad de programación funcional y se utilizan para implementar conjuntos y mapas en MIT Scheme , SLIB , SML-NJ e implementaciones de Haskell . ^{[6] [4]}

Un árbol de peso equilibrado es un árbol de búsqueda binario que almacena los tamaños de los subárboles en los nodos. Es decir, un nodo tiene campos

• clave , de cualquier tipo ordenado
• valor (opcional, solo para asignaciones)
• izquierda , derecha , puntero al nodo
• tamaño , de tipo entero.

Por definición, el tamaño de una hoja (normalmente representada por un puntero nulo ) es cero. El tamaño de un nodo interno es la suma de los tamaños de sus dos hijos, más uno: ( size[n] = size[n.left] + size[n.right] + 1 ). En función del tamaño, se define el peso como weight[n] = size[n] + 1 . ^[a] El peso tiene la ventaja de que el peso de un nodo es simplemente la suma de los pesos de sus hijos izquierdo y derecho.

Las operaciones que modifican el árbol deben asegurarse de que el peso de los subárboles izquierdo y derecho de cada nodo permanezca dentro de un factor α entre sí, utilizando las mismas operaciones de reequilibrio utilizadas en los árboles AVL : rotaciones y rotaciones dobles. Formalmente, el equilibrio de nodos se define de la siguiente manera:

Un nodo está equilibrado en peso α si weight[n.left] ≥ α·weight[n] y weight[n.right] ≥ α·weight[n] . ^[7]

Aquí, α es un parámetro numérico que se debe determinar al implementar árboles con equilibrio de peso. Valores mayores de α producen árboles "más equilibrados", pero no todos los valores de α son apropiados; Nievergelt y Reingold demostraron que

${\displaystyle \alpha <1-{\frac {\sqrt {2}}{2}}\aproximadamente 0,29289}$

es una condición necesaria para que funcione el algoritmo de equilibrio. Trabajos posteriores mostraron un límite inferior de 2 ⁄ 11 para α , aunque se puede hacer arbitrariamente pequeño si se utiliza un algoritmo de reequilibrio personalizado (y más complicado). ^[7]

La aplicación correcta del equilibrio garantiza que un árbol de n elementos tendrá altura ^[7]

${\displaystyle h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)}$

Si se le da a α su valor máximo permitido, la altura en el peor de los casos de un árbol con equilibrio de peso es la misma que la de un árbol rojo-negro en . $Estilo de visualización 2 log _{2}n$

El número de operaciones de balanceo requeridas en una secuencia de n inserciones y eliminaciones es lineal en n , es decir, el balanceo requiere una cantidad constante de sobrecarga en un sentido amortizado . ^[8]

Si bien mantener un árbol con el costo de búsqueda mínimo requiere cuatro tipos de rotaciones dobles (LL, LR, RL, RR como en un árbol AVL) en operaciones de inserción/eliminación, si solo deseamos un rendimiento logarítmico, LR y RL son las únicas rotaciones requeridas en una sola pasada de arriba hacia abajo. ^[9]

Se han definido varias operaciones de conjuntos en árboles con equilibrio de peso: unión , intersección y diferencia de conjuntos . Luego, se pueden implementar operaciones rápidas en bloque sobre inserciones o eliminaciones basadas en estas funciones de conjuntos. Estas operaciones de conjuntos se basan en dos operaciones auxiliares, Split y Join . Con las nuevas operaciones, la implementación de árboles con equilibrio de peso puede ser más eficiente y altamente paralelizable. ^{[10] [11]}

• Join : La función Join se basa en dos árboles con peso equilibrado t ₁ y t ₂ y una clave k y devolverá un árbol que contiene todos los elementos en t ₁ , t ₂ así como k . Requiere que k sea mayor que todas las claves en t ₁ y menor que todas las claves en t ₂ . Si los dos árboles tienen el peso equilibrado, Join simplemente crea un nuevo nodo con el subárbol izquierdo t ₁ , la raíz k y el subárbol derecho t ₂ . Supongamos que t ₁ tiene un peso mayor que t ₂ (el otro caso es simétrico). Join sigue la columna derecha de t ₁ hasta un nodo c que está equilibrado con t ₂ . En este punto, se crea un nuevo nodo con el hijo izquierdo c , la raíz k y el hijo derecho t ₂ para reemplazar a c. El nuevo nodo puede invalidar el invariante con peso equilibrado. Esto se puede solucionar con una rotación simple o doble asumiendo${\displaystyle \alpha <1-{\frac {1}{\sqrt {2}}}}$
• Split : para dividir un árbol con equilibrio de peso en dos árboles más pequeños, aquellos más pequeños que la clave x y aquellos más grandes que la clave x , primero dibuje 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 simé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. Este algoritmo en realidad no tiene nada que ver con ninguna propiedad especial de un árbol con equilibrio de peso y, por lo tanto, es genérico para otros esquemas de equilibrio como los árboles AVL .${\displaystyle O(\log n)}$

El algoritmo de unión es el siguiente:

función joinRightWB(T L , k, T R )
    (l, k', c) = exponer(T L )
     si balance(|T L |, |T R |) devuelve Nodo(T L , k, T R )
     de lo contrario  
        T' = joinRightWB(c, k, T R )
        (l', k', r') = exponer(T')
        si (balance(|l|,|T'|)) retorna Nodo(l, k', T')
         de lo contrario si (balance(|l|,|l'|) y balance(|l|+|l'|,|r'|))
              retorna rotateLeft(Nodo(l, k', T'))
         de lo contrario retorna rotateLeft(Nodo(l, k', rotateRight(T'))
 función joinLeftWB(T L , k, T R )
    /* simétrico para unirse a RightWB */
función join(T L , k, T R )
     si (heavy(T L , T R )) devuelve joinRightWB(T L , k, T R )
     si (heavy(T R , T L )) devuelve joinLeftWB(T L , k, T R )
    Nodo(T L , k, T R )

Aquí balance significa dos pesos y están equilibrados. exposed(v)=(l, k, r) significa extraer el hijo izquierdo de un nodo del árbol , la clave del nodo y el hijo derecho . Node(l, k, r) significa crear un nodo de hijo izquierdo , clave e hijo derecho . ${\estilo de visualización (x,y)}$${\estilo de visualización x}$${\estilo de visualización y}$${\estilo de visualización v}$${\estilo de visualización l}$${\estilo de visualización k}$${\estilo de visualización r}$${\estilo de visualización l}$${\estilo de visualización k}$${\estilo de visualización r}$

El algoritmo de división es el siguiente:

función split(T, k)
     si (T = nulo) devuelve (nulo, falso, nulo)
    (L, (m, c), R) = exponer(T)
    si (k = m) devuelve (L, verdadero, R)
     si (k < m)
       (L', b, R') = dividir(L, k)
       devuelve (L', b, unir(R', m, R))
     si (k > m)
       (L', b, R') = dividir(R, k)
       devolver (unir(L, m, L'), b, R))

La unión de dos árboles con ponderación equilibrada t ₁ y t ₂ que representan los conjuntos A y B , es un árbol con ponderación equilibrada 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 
    si t 2 = nulo:
         devuelve t 1 
    t < , t > ← dividir t 2 en t 1 .root
     devuelve unión(unión(izquierda(t 1 ), t < ), t 1 .root, unión(derecha(t 1 ), t > ))

Aquí, se supone que Split devuelve dos árboles: uno que contiene las claves menores que su clave de entrada, y el otro que contiene las claves mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva en el lugar).

El algoritmo para intersección o diferencia es similar, pero requiere la rutina auxiliar Join2 que es la misma que Join pero sin la clave intermedia. Según las nuevas funciones para unión, intersección o diferencia, se puede insertar o eliminar una o varias claves en el árbol con equilibrio de peso. Dado que Split y Union llaman a Join pero no tratan directamente los criterios de equilibrio de los árboles con equilibrio de peso, una implementación de este tipo suele denominarse algoritmos basados ​​en join .

La complejidad de cada unión, intersección y diferencia 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 unión, intersección o diferencia son independientes entre sí, se pueden ejecutar en paralelo con una profundidad paralela . ^[10] Cuando , la implementación basada en unión tiene el mismo gráfico acíclico dirigido (DAG) computacional que la inserción y 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({n \sobre m}+1\right)\right)}$${\estilo de visualización m}$${\displaystyle n(\geq m)}$ ${\displaystyle O(\log m\log n)}$${\estilo de visualización m=1}$