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

8

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(logn)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(logn)

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(logn)O(logn)

templatetypedef
fonte
2
Que outras operações o dicionário classificado deve ter e com que rapidez elas são? Sem requisitos na classificação de inserção e pesquisa, as listas duplamente vinculadas funcionam bem, mas as operações de não mesclagem levam tempo linear, no comprimento da lista, que pode ser superlinear no número de chaves distintas.
Jbapple #
O(logn)
Eu sugiro que você editar a sua pergunta para incluir esta informação na pergunta ...
DW
O(logn)n

Respostas:

8

dO(logd)kO(klog(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.

xn1,n2,xO(logn1)O(log(n2/n1))O(logn)xO(logn)O(1)

nO(logn)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.

David Eppstein
fonte
1
logUU
Não, basta registrar o número máximo de itens em uma árvore ao mesmo tempo.
David Eppstein