¿Estructura de diccionario ordenada que admite fusiones eficientes?

Muchas estructuras de árbol equilibradas (árboles rojos / negros, árboles de separación, etc.) y algunas otras estructuras de diccionario ordenadas (listas de omisión) admiten una operación de unión que incluye dos diccionarios donde todas las claves de la primera estructura son menores que todas las claves del segundo, luego combina los dos diccionarios en un solo diccionario ordenado en el tiempo , donde n es el número total de claves. Sin embargo, esto solo funciona si no hay superposición en los rangos de claves almacenadas en esos árboles.$O(\log n)$$n$

Del mismo modo, muchas colas prioritarias (montones binomiales, montones de Fibonacci, etc.) admiten fusiones de tiempo . Estas fusiones funcionan independientemente de las claves almacenadas, pero dado que las estructuras de datos son colas de prioridad, no podemos buscar elementos aleatorios en la estructura resultante.$O(\log n)$

¿Existe una estructura de diccionario ordenada que admita fusiones de diccionarios arbitrarios en el tiempo al tiempo que admite operaciones de diccionario ordenadas normales (inserciones, eliminaciones, búsquedas, consultas de sucesor / predecesor, etc.) en el tiempo O ( log n ) , o ¿Una prueba de límite inferior de que tales estructuras no pueden existir?$O(\log n)$$O(\log n)$

$d$$O(\log d)$$k$$O(k\log(n/k))$

Ahora, suponga que desea admitir inserciones, fusiones destructivas y búsquedas. Para las inserciones y búsquedas, solo use las operaciones de árbol de búsqueda existentes. Para una fusión, siempre combine el árbol más pequeño en el más grande, y use un recorrido transversal del árbol más pequeño para obtener su orden ordenado en tiempo lineal. Luego, inserte los elementos del árbol más pequeño uno a la vez en el árbol más grande en este orden ordenado.

$x$$n_1, n_2,\dots$$x$$O(\log n_1)$$O(\log(n_2/n_1))$$\dots$$O(\log n)$$x$$O(\log n)$$O(1)$

$n$$O(\log n)$el tiempo por operación debe ser el número total de elementos que se insertaron o eliminaron en lugar del número actualmente presente. Si estos dos números alguna vez se separan demasiado, puede realizar una actualización que reajuste todos los recuentos a sus números reales, restableciendo la estructura de datos a un estado sin elementos borrados de forma diferida; el tiempo amortizado para esta actualización se puede cargar contra las operaciones de eliminación que tuvo que realizar para obtener los números tan separados. O posiblemente puede hacer que la amortización de fusión funcione directamente con eliminaciones no perezosas, pero no he resuelto los detalles de esa parte.