Melhor BST auto-equilíbrio para inserção rápida de um grande número de nós

votos
8

Eu tenho sido capaz de encontrar detalhes sobre várias auto-equilíbrio BSTs através de várias fontes, mas eu não encontrei qualquer boas descrições detalhando qual é o melhor para usar em situações diferentes (ou se ele realmente não importa).

Eu quero um BSTque é ideal para o armazenamento de mais de dez milhões de nós. A ordem de inserção dos nós é basicamente aleatória, e eu nunca precisará excluir nós, assim que o tempo de inserção é a única coisa que precisa ser otimizado.

Eu pretendo usá-lo para armazenar estados de jogo visitadas anteriormente em um jogo de quebra-cabeça, para que eu possa verificar rapidamente se uma configuração anterior já foi encontrado.

Publicado 05/08/2008 em 16:40
fonte usuário
Em outras línguas...                            


4 respostas

votos
3

Por que usar um BSTem tudo? De sua descrição de um dicionário vai funcionar tão bem, se não melhor.

A única razão para usar um BSTseria se você queria listar o conteúdo do recipiente na ordem da chave. Ela certamente não soar como você quer fazer isso, caso em que ir para a tabela de hash. O(1)inserção e pesquisa, não se preocupa com a eliminação, o que poderia ser melhor?

Respondeu 29/08/2008 em 01:10
fonte usuário

votos
3

Vermelho-preto é melhor do que AVL para aplicações de inserção-pesado. Se você prever relativamente uniforme look-up, em seguida, Red-negro é o caminho a percorrer. Se você prevê um look-up relativamente desequilibrado onde os elementos mais recentemente visitadas são mais propensos a ser visto novamente, você quer usar árvores splay .

Respondeu 05/08/2008 em 16:59
fonte usuário

votos
0

Os dois auto-equilíbrio BSTs Eu estou mais familiarizado são rubro-negro e AVL, por isso não posso dizer com certeza se quaisquer outras soluções são melhores, mas se bem me lembro, vermelho-preto tem inserção mais rápida e recuperação mais lenta em comparação com AVL.

Portanto, se a inserção é uma prioridade mais elevada do que a recuperação, vermelha-preta pode ser uma solução melhor.

Respondeu 05/08/2008 em 16:50
fonte usuário

votos
-2

[Tabelas de dispersão têm] O (1) de inserção e pesquisa

Acho que isso está errado.

Primeiro de tudo, se você limitar a keyspace ser finito, você pode armazenar os elementos em uma matriz e fazer um O (1) varredura linear. Ou você poderia shufflesort a matriz e, em seguida, fazer uma varredura linear em O (1) tempo de espera. Quando o material é finito, o material é facilmente O (1).

Então, digamos que a sua tabela hash irá armazenar qualquer cadeia de bits arbitrária; isso não importa muito, contanto que há um conjunto infinito de chaves, cada uma das quais são finitos. Então você tem que ler todos os bits de qualquer entrada de consulta e inserção, mais eu inserir y0 em um hash vazio e consulta on y1, onde y0 e y1 diferem em uma posição de bit único que você não olhar.

Mas vamos dizer que os comprimentos de chave não são um parâmetro. Se a sua inserção e procurar tomar O (1), em particular hashing leva O (1) tempo, o que significa que você só olhar para uma quantidade finita de saída da função hash (a partir do qual não é provável que seja apenas uma saída finita, concedido ).

Isto significa que com um número finito de baldes, deve haver um conjunto infinito de seqüências de que todos têm o mesmo valor hash. Suponhamos que inserir um lote, ou seja, ω (1), daqueles, e iniciar a consulta. Isto significa que a sua tabela hash tem que cair para trás em algum outro O (1) mecanismo de inserção / pesquisa para responder às minhas perguntas. Qual deles, e por que não usar isso diretamente?

Respondeu 01/02/2009 em 13:49
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more