Qual é a estrutura de dados ideal para uma árvore de mapas.

Estou procurando uma estrutura de dados, que é basicamente uma árvore de mapas, onde o mapa em cada nó contém alguns novos elementos, bem como os elementos no mapa do nó pai. Por mapa aqui, quero dizer um mapa de programação com chaves e valores, como mapa no STL ou dict em python.

Por exemplo, pode haver um nó raiz:

root = {'car':1, 'boat':2}

e 2 filhos, cada um adicionando um elemento ao mapa pai

child1 = {'car':1, 'boat':2, 'jet':35}
child2 = {'car':1, 'boat':2, 'scooter':-5}

Eu gostaria que esse espaço fosse o mais eficiente possível, ou seja, não quero armazenar uma cópia completa do mapa resultante em cada nó, mas, idealmente, a pesquisa ainda seria O (log N), sendo N o número total de elementos no nó, não na árvore inteira.

Eu estava pensando que talvez haja uma função de hash inteligente que eu possa usar para isso, mas não consegui criar nada.

A abordagem ingênua seria armazenar as entradas recém-adicionadas em um mapa em cada nó e, em seguida, subir a árvore se nada for encontrado. Não gosto disso porque depende da profundidade da árvore.

ds.data-structures tree hash-function phreeza
fonte

então cada nó representa um mapa que refina o mapa armazenado no pai?

precisa

além disso, você quer dizer mapa no sentido matemático ou cartográfico?

precisa

Quero dizer um mapa no sentido matemático / CS. Como mapa no STL, por exemplo.

Phreza

@ Suresh: Parece que não é um refinamento. Se eu acertei a pergunta, um nó filho adiciona novos elementos ao mapa do nó pai.

Jukka Suomela

e para responder à primeira pergunta, cada nó refina o mapa no sentido em que mais pares de chave / valor são adicionados.

Phreza

Respostas:

Você não disse o que são consultas, mas presumo que query () use um nó e uma chave e deseje o valor associado (ou null se esse valor não existir). Nesse caso, acho que, em geral, você não pode fazer melhor do que armazenar um mapa separado em cada nó. Considere, por exemplo, uma árvore lagarta em que cada nó do caminho tem um nó conectado a ele que é bifurcado (um total de 2n nós). Enraizá-lo em uma extremidade do caminho. Agora, suponha que o tamanho do universo para chaves seja m. Para cada nó bifurcado v e cada uma das m chaves possíveis, essa chave pode existir ou não existir em v, e ambas estariam em conformidade com a restrição de subárvore. Portanto, existem possibilidades para saber se cada chave existe em cada nó da bifurcação, portanto, você precisa de mn bits de espaço apenas para armazenar as informações necessárias. $2^{mn}$

Jelani Nelson
fonte

Mas este exemplo não mostra que você deve armazenar informações redundantes (ou seja, que você também deve duplicar as entradas do nó raiz em cada filho)!

Jukka Suomela

Estou confuso. Em uma árvore de profundidade com nós, fica claro que você não pode armazenar ligações em espaço. Seu exemplo está mostrando algo mais?

1

$1$

n

$n$

m

$m$

o (m)

$o(m)$

Radu GRIGore

Primeiro de tudo, acho que o que você quer dizer com "mapa" é um "dicionário" no idioma do TCS. Segundo, não entendo a frase "idealmente, a pesquisa ainda seria ", pois em um dicionário a pesquisa leva tempo O (1) com várias tabelas de hash. Terceiro, você não declarou se o problema é estático ou dinâmico; Estou assumindo estática. $O(\log N)$

A complexidade ideal para esse problema é pesquisa predecessora), por exemplo, usando van Emde Boas. Isso é ideal se o tamanho da palavra for ; consulte http://people.csail.mit.edu/mip/papers/pred/pred.pdf para obter os limites ideais do predecessor. $\Theta($ $O(\lg\lg N)$ $\Theta(\lg n)$

A maneira correta de atacar o problema é criar uma tabela de hash global e lidar com a hierarquia separadamente para cada chave na tabela. Para uma chave , conhecemos os nós onde ela aparece. Considere uma travessia em ordem da árvore. Os nós em que aparece definem os intervalos nesta ordem. Para determinar se está na tabela de hash de algum nó , é necessário perguntar se apunhala algum segmento conforme definido acima. Isso é feito facilmente pela pesquisa de antecessores, onde construímos uma tabela de antecessores para todos os pontos finais de intervalo. $x$ $x$ $x$ $v$ $v$

Para um limite inferior, observe que mesmo uma pergunta esfaqueada é tão difícil quanto o predecessor (consulte as reduções da pesquisa de predecessores coloridos). Como as referências em papel acima mostram o comportamento ideal de soma direta para a pesquisa predecessora, isso significa que o algoritmo descrito acima é ideal para qualquer relação entre o número de nós e o número total de chaves.

Mihai
fonte