Estrutura de dicionário classificada que suporta fusões eficientes?

Muitas estruturas de árvore balanceadas (árvores vermelhas / pretas, árvores espalhadas etc.) e algumas outras estruturas de dicionário classificadas (skiplists) oferecem suporte a uma operação de junção que realiza dois dicionários em que todas as chaves na primeira estrutura são menores que todas as chaves no segundo, depois combina os dois dicionários em um único dicionário classificado no tempo , onde n é o número total de chaves. No entanto, isso só funciona se não houver sobreposição nos intervalos de chaves armazenados nessas árvores.$O(\log n)$$n$

Da mesma forma, muitas filas de prioridade (pilhas binomiais, pilhas de Fibonacci, etc.) suportam mesclagens -time. Essas mesclagens funcionam independentemente de quais chaves estão armazenadas, mas, como as estruturas de dados são filas prioritárias, não podemos fazer pesquisas de elementos aleatórios na estrutura resultante.$O(\log n)$

Existe uma estrutura de dicionário classificado que suporta mesclagens de dicionários arbitrários no tempo ao mesmo tempo, suporta operações normais do dicionário classificado (inserções, exclusões, pesquisas, consultas de sucessores / predecessores, etc.) no tempo O ( log n ) ou uma prova inferior de que tais estruturas não podem existir?$O(\log n)$$O(\log n)$

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

Agora, suponha que você queira oferecer suporte a inserções, mesclagens destrutivas e pesquisas. Para inserções e pesquisas, basta usar as operações existentes da árvore de pesquisa. Para uma mesclagem, sempre mescle a árvore menor na maior e use uma passagem interna da árvore menor para obter sua ordem classificada em tempo linear. Em seguida, insira os elementos da árvore menor, um de cada vez, na árvore maior nessa ordem de classificação.

$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)$o tempo por operação deve ser o número total de itens já inseridos ou excluídos, em vez do número atualmente presente. Se esses dois números se afastarem demais, você poderá fazer uma atualização que reajuste todas as contagens aos números reais, redefinindo a estrutura de dados para um estado sem itens excluídos com folga; o tempo amortizado para esta atualização pode ser cobrado pelas operações de exclusão que você precisou executar para separar os números. Ou, possivelmente, você pode fazer com que a amortização de mesclagem funcione diretamente com exclusões não preguiçosas, mas ainda não resolvi os detalhes dessa parte.