En informática , los árboles binarios con equilibrio de peso ( WBT ) son un tipo de árboles de búsqueda binarios con equilibrio automático 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]
Al igual que otros árboles de autoequilibrio, los WBT almacenan información contable relacionada con el equilibrio en sus nodos y realizan rotaciones para restablecer el equilibrio cuando se ve perturbado por operaciones de inserción o eliminación. Específicamente, cada nodo almacena el tamaño del subárbol enraizado 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 almacenan la altura de los subárboles) y los árboles rojo-negro (que almacenan un bit de "color" ficticio), la información de contabilidad 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 de estadísticas de orden , es decir, obtener el n -ésimo elemento más grande en un conjunto o determinar el índice de un elemento en orden pedido. [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 e implementaciones de Haskell . [6] [4]
Descripción
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 (típicamente representado 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 ( talla [n] = talla [n. izquierda] + talla [n. derecha] + 1 ). Según el tamaño, se define el peso como peso [n] = talla [n] + 1 . [a]
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 algún factor α entre sí, utilizando las mismas operaciones de reequilibrio que se utilizan 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 peso [n. izquierda] ≥ α · peso [n] y peso [n. derecha] ≥ α · peso [n] . [7]
Aquí, α es un parámetro numérico que se determinará al implementar árboles con balance de peso. Los valores más altos de α producen árboles "más equilibrados", pero no todos los valores de α son apropiados; Nievergelt y Reingold demostraron que
es una condición necesaria para que funcione el algoritmo de equilibrio. El trabajo posterior mostró un límite inferior de 2 ⁄ 11 para α , aunque puede hacerse arbitrariamente pequeño si se utiliza un algoritmo de reequilibrio personalizado (y más complicado). [7]
Aplicar el equilibrio correctamente garantiza que un árbol de n elementos tendrá altura [7]
El número de operaciones de balance requeridas en una secuencia de n inserciones y eliminaciones es lineal en n , es decir, el balance requiere una cantidad constante de gastos generales en un sentido amortizado . [8]
Si bien mantener el árbol con el costo de búsqueda mínimo requiere cuatro tipos de rotaciones dobles (LL, LR, RL, RR como en el á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 pase único de arriba hacia abajo. [9]
Establecer operaciones y operaciones masivas
Se han definido varias operaciones de conjuntos en árboles de peso equilibrado: unión , intersección y diferencia de conjuntos . Luego, se pueden implementar operaciones masivas rápidas en inserciones o eliminaciones basadas en estas funciones establecidas. Estas operaciones de conjunto 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]
- Unir : La función Unir está en dos árboles de peso equilibrado t 1 y t 2 y una tecla k y devolverá un árbol que contiene todos los elementos en t 1 , t 2 y k . Requiere que k sea mayor que todas las claves en t 1 y menor que todas las claves en t 2 . Si los dos árboles tienen el peso equilibrado, 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 tiene más peso 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 ponderación. Esto se puede solucionar con una rotación simple o doble asumiendo
- Dividir : Para dividir un árbol con equilibrio de peso en dos árboles más pequeños, los más pequeños que la clave x y los 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 de la izquierda, 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 las propiedades especiales de un árbol de peso equilibrado y, por lo tanto, es genérico para otros esquemas de equilibrio como los árboles AVL .
El algoritmo de unión es el siguiente:
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 .
El algoritmo de división es el siguiente:
función split (T, k) if (T = nil) return (nil, false, nil) (L, (m, c), 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))
La unión de dos árboles de equilibrado de peso- T 1 y T 2 que representa conjuntos A y B , es un árbol de peso equilibrado t que representa A ∪ B . La siguiente función recursiva calcula esta unión:
función union (t 1 , t 2 ): if t 1 = nil: return t 2 if t 2 = nil: return t 1 t < , t > ← split t 2 on t 1 .root return join (union (left (t 1 ), t < ), t 1 .root, union (right (t 1 ), t > ))
Aquí, se supone que Split devuelve dos árboles: uno que sostiene las teclas menos su tecla de entrada, otro que sostiene las teclas mayores. (El algoritmo no es destructivo , pero también existe una versión destructiva in situ).
El algoritmo de intersección o diferencia es similar, pero requiere la rutina auxiliar Join2 que es la misma que Join pero sin la tecla del medio. Según las nuevas funciones de unión, intersección o diferencia, se puede insertar o eliminar una o varias teclas del árbol de ponderación. Dado que Split y Union llaman a Join pero no se ocupan directamente de los criterios de equilibrio de los árboles con equilibrio de peso, esta implementación se suele denominar algoritmos basados en uniones .
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. . [10] Cuando, la implementación basada en uniones tiene el mismo gráfico acíclico dirigido computacionalmente (DAG) que la inserción y 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.
Notas
Referencias
- ^ Tsakalidis, AK (1984). "Mantener el orden en una lista enlazada generalizada". Acta Informatica . 21 : 101-112. doi : 10.1007 / BF00289142 .
- ^ Nievergelt, J .; Reingold, EM (1973). "Árboles de búsqueda binaria de equilibrio acotado". Revista SIAM de Computación . 2 : 33–43. doi : 10.1137 / 0202005 .
- ^ Este artículo incorpora material de dominio público del documento NIST : Black, Paul E. "Árbol BB (α)" . Diccionario de algoritmos y estructuras de datos .
- ^ a b c Hirai, Y .; Yamamoto, K. (2011). "Equilibrio de árboles con equilibrio de peso" (PDF) . Revista de programación funcional . 21 (3): 287. doi : 10.1017 / S0956796811000104 .
- ^ Roura, Salvador (2001). Un nuevo método para equilibrar árboles de búsqueda binarios . ICALP . Apuntes de conferencias en informática. 2076 . págs. 469–480. doi : 10.1007 / 3-540-48224-5_39 . ISBN 978-3-540-42287-7.
- ^ a b Adams, Stephen (1993). "Perlas funcionales: conjuntos eficientes, un acto de equilibrio". Revista de programación funcional . 3 (4): 553–561. doi : 10.1017 / S0956796800000885 .
- ^ a b c Latón, Peter (2008). Estructuras de datos avanzadas . Prensa de la Universidad de Cambridge. págs. 61 –71.
- ^ Blum, Norbert; Mehlhorn, Kurt (1980). "Sobre el número medio de operaciones de reequilibrio en árboles ponderados" (PDF) . Informática Teórica . 11 (3): 303–320. doi : 10.1016 / 0304-3975 (80) 90018-3 .
- ^ Cho, Seonghun; Sahni, Sartaj (2000). "Un nuevo árbol de búsqueda binaria con equilibrio de peso" . Revista Internacional de Fundamentos de la Ciencia de la Computación . 11 (3): 485–513. doi : 10.1142 / S0129054100000296 .
- ^ 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.
- ^ Adams, Stephen (1992), Implementar conjuntos de manera eficiente en un lenguaje funcional , CiteSeerX 10.1.1.501.8427.