En informática , un árbol de fusión es un tipo de estructura de datos de árbol que implementa una matriz asociativa en enteros de w bits en un universo finito, donde cada uno de los enteros de entrada tiene un tamaño inferior a 2 w y no es negativo. Cuando opera en una colección de n pares clave-valor , utiliza el espacio O ( n ) y realiza búsquedas en el tiempo O (log w n ) , lo cual es asintóticamente más rápido que un árbol de búsqueda binario autoequilibrado tradicional , y también mejor que el Árbol de van Emde Boas para valores grandes de w . Logra esta velocidad mediante el uso de ciertas operaciones de tiempo constante que se pueden realizar en una palabra de máquina . Los árboles de fusión fueron inventados en 1990 por Michael Fredman y Dan Willard . [1]
Se han logrado varios avances desde el artículo original de Fredman y Willard de 1990. En 1999 [2] se mostró cómo implementar árboles de fusión bajo un modelo de computación en el que todas las operaciones subyacentes del algoritmo pertenecen a AC 0 , un modelo de complejidad de circuito que permite la suma y operaciones booleanas bit a bit pero no permite la Operaciones de multiplicación utilizadas en el algoritmo de árbol de fusión original. En 1996 [3] se propuso una versión dinámica de árboles de fusión que utilizan tablas hash que coincidían con el tiempo de ejecución O (log w n ) de la estructura original según las expectativas. En 2007 [4] se propuso otra versión dinámica que utiliza un árbol exponencial que produce tiempos de ejecución en el peor de los casos de O (log w n + log log n ) por operación. Finalmente, se demostró que los árboles de fusión dinámica pueden realizar cada operación en tiempo O (log w n ) de forma determinista. [5]
Esta estructura de datos implementa operaciones de búsqueda de agregar clave, eliminar clave, buscar clave y predecesor (siguiente valor más pequeño) y sucesor (siguiente valor más grande) para una clave determinada. El resultado parcial del localizador de bits más significativo en tiempo constante también ha ayudado a seguir investigando. Los árboles de fusión utilizan el paralelismo a nivel de palabras para ser eficientes, realizando cálculos en varios números enteros pequeños, almacenados en una sola palabra de máquina, simultáneamente para reducir el número de operaciones totales.
Un árbol de fusión es esencialmente un árbol B con un factor de ramificación de w 1/5 (también es posible cualquier exponente pequeño ya que no tendrá un gran impacto en la altura del árbol), lo que le da una altura de O (log w norte ) . Para lograr los tiempos de ejecución deseados para actualizaciones y consultas, el árbol de fusión debe poder buscar un nodo que contenga hasta w 1/5 claves en tiempo constante. Esto se hace comprimiendo ("dibujando") las claves para que todas puedan caber en una palabra de máquina, lo que a su vez permite realizar comparaciones en paralelo. Entonces, una serie de cálculos que involucran bocetos, comparación paralela y localizador del índice de bits más significativo, ayudan a llegar a la solución requerida.
El boceto es el método mediante el cual cada clave de w bits en un nodo que contiene k claves se comprime en solo k − 1 bits. Cada clave x puede considerarse como una ruta en el árbol binario completo de altura w que comienza en la raíz y termina en la hoja correspondiente a x . Esta ruta se puede procesar buscando recursivamente en el hijo izquierdo de i si el i-ésimo bit es 0 y en el hijo derecho si es 1, generalmente, hasta que se escaneen todos los bits. Para distinguir dos caminos, basta con observar su punto de bifurcación (el primer bit donde dos claves difieren). Como hay un máximo de k claves, no habrá más de k-1 puntos de ramificación, lo que significa que no se requieren más de k-1 bits para identificar una clave. Y por tanto, ningún boceto tendrá más de k-1 bits.
Una propiedad importante de la función de boceto es que conserva el orden de las claves. Es decir, sketch( x ) < sketch( y ) para dos claves cualesquiera x < y . Entonces, para todo el rango de claves, sketch(x 0 )<sketch(x 1 )<...<sketch(x k-1 ) porque si se sigue la ruta de árbol binario, los nodos se ordenarán de tal manera que x 0 <x 1 <...<x k-1 .
Si las ubicaciones de los bits del boceto son b 1 < b 2 < ··· < b r , entonces el boceto de la clave x w -1 ··· x 1 x 0 es el entero de r bits .
Con sólo operaciones de palabras estándar, como las del lenguaje de programación C , es difícil calcular directamente el boceto perfecto de una clave en tiempo constante. En cambio, los bits del boceto se pueden empaquetar en un rango de tamaño como máximo r 4 , usando AND bit a bit y multiplicación, llamado boceto aproximado, que tiene todos los bits importantes pero también algunos bits inútiles adicionales distribuidos en un patrón predecible. La operación AND bit a bit sirve como una máscara para eliminar todos estos bits que no son de boceto de la clave, mientras que la multiplicación desplaza los bits de boceto a un rango pequeño. Al igual que el boceto "perfecto", el boceto aproximado también conserva el orden de las claves y significa que sketch(x 0 )<sketch(x 1 )<...<sketch(x k-1 ).
Se necesita algún procesamiento previo para determinar la constante de multiplicación correcta. Cada bit de boceto en la ubicación b i se desplazará a b i + m i mediante una multiplicación por m = 2 m i . Para que el boceto aproximado funcione, se deben cumplir las tres propiedades siguientes:
Un argumento inductivo muestra cómo se puede construir m i . Sea metro 1 = w - segundo 1 . Supongamos que 1 < t ≤ r y que m 1 , m 2 ... m t-1 ya han sido elegidos. Luego elija el entero más pequeño m t tal que se cumplan ambas propiedades (1) y (2). La propiedad (1) requiere que m t ≠ b i − b j + m l para todo 1 ≤ i , j ≤ r y 1 ≤ l ≤ t -1. Por lo tanto, hay menos de tr 2 ≤ r 3 valores que m t debe evitar. Dado que m t se elige como mínimo, ( b t + m t ) ≤ ( b t -1 + m t -1 ) + r 3 . Esto implica la Propiedad (3).
Por tanto, el boceto aproximado se calcula de la siguiente manera:
El propósito de la compresión lograda mediante el boceto es permitir que todas las claves se almacenen en una palabra de w bits. Sea el boceto de nodo de un nodo la cadena de bits
sketch( x 1 )1 sketch( x 2 ) ...1 sketch( xk )Aquí, todas las palabras esbozadas se agrupan en una cadena anteponiendo un bit determinado a cada una de ellas. Podemos suponer que la función de boceto usa exactamente b ≤ r 4 bits. Luego, cada bloque usa 1 + b ≤ w 4/5 bits, y como k ≤ w 1/5 , el número total de bits en el boceto del nodo es como máximo w .
Una breve nota aparte: para una cadena de bits s y un entero no negativo m , denotemos por s m la concatenación de s consigo mismo m veces. Si t también es una cadena de bits, st denota la concatenación de t con s .
El boceto del nodo permite buscar las claves para cualquier número entero de b bits y . Sea z = (0 y ) k , que se puede calcular en tiempo constante (multiplique y por la constante (0 b 1) k ), para que sea tan largo como el boceto del nodo de modo que se pueda comparar cada palabra en el boceto del nodo. con el entero de consulta y en una sola operación, lo que demuestra el paralelismo a nivel de palabra. Si y tuviera 5 bits de longitud, se multiplicaría por 000001....000001 para obtener sketch(y) k . La diferencia entre sketch(xi ) y 0y da como resultado que el bit principal de cada bloque sea 1, si y sólo si sketch(y) sketch(xi ) . Por tanto, podemos calcular el índice más pequeño i tal que ( x i ) ≥ y de la siguiente manera:sketch
Para una consulta arbitraria q , la comparación paralela calcula el índice i tal que
sketch( x yo -1 ) ≤ sketch( q ) ≤ sketch( x yo )Desafortunadamente, esto da el predecesor o sucesor exacto de q , porque la ubicación del boceto de q entre los bocetos de todos los valores puede no ser la misma que la ubicación de q en todos los valores reales. Lo que es cierto es que, entre todas las claves, x i -1 o x i tiene el prefijo común más largo con q . Esto se debe a que cualquier clave y con un prefijo común más largo con q también tendría más bits de boceto en común con q y , por lo tanto, sketch( y ) estaría más cerca de sketch( q ) que cualquier sketch( x j ).
La longitud del prefijo común más largo entre dos enteros de w bits a y b se puede calcular en tiempo constante encontrando el bit más significativo del XOR bit a bit entre a y b . Esto luego se puede usar para enmascarar todos los prefijos comunes excepto el más largo.
Tenga en cuenta que p identifica exactamente dónde se ramifica q del conjunto de claves. Si el siguiente bit de q es 0, entonces el sucesor de q está contenido en el subárbol p 1, y si el siguiente bit de q es 1, entonces el predecesor de q está contenido en el subárbol p 0. Esto sugiere el siguiente algoritmo para determinar la ubicación exacta de q :
sketch( x i -1 ) ≤ sketch( q ) ≤ sketch( x i ).sketch( e ). Este es el predecesor real de q .sketch( e ). Este es el sucesor real de q .Willard dio una aplicación de árboles de fusión a tablas hash , quien describe una estructura de datos para hash en la que una tabla hash de nivel externo con encadenamiento hash se combina con un árbol de fusión que representa cada cadena hash. En el encadenamiento hash, en una tabla hash con un factor de carga constante, el tamaño promedio de una cadena es constante, pero además, con una alta probabilidad, todas las cadenas tienen un tamaño O (log n / log log n ) , donde n es el número de elementos hash . Este tamaño de cadena es lo suficientemente pequeño como para que un árbol de fusión pueda manejar búsquedas y actualizaciones dentro de ella en un tiempo constante por operación. Por lo tanto, el tiempo para todas las operaciones en la estructura de datos es constante con una alta probabilidad. Más precisamente, con esta estructura de datos, para cada probabilidad cuasipolinomial inversa p ( n ) = exp((log n ) O (1) ) , existe una constante C tal que la probabilidad de que exista una operación que exceda el tiempo C es como máximo p ( n ) . [6]
El modelo computacional para el algoritmo Fusion Tree es una RAM de Word con un conjunto de instrucciones específico, que incluye instrucciones aritméticas (suma, resta y multiplicación (todas realizadas en módulo 2 w ) y operaciones booleanas: bit a bit AND, NOT, etc. Una instrucción de multiplicación de doble precisión también está incluido. Se ha demostrado [7] que la eliminación de esta última instrucción hace imposible ordenar más rápido que O ( n log n ) , a menos que se permita utilizar un espacio de memoria de casi 2 w palabras (en contraste con el espacio lineal utilizado por Fusion Trees). ), o incluir otras instrucciones en su lugar [2] .