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

Question

Consegui encontrar detalhes sobre vários métodos de autoequilíbrio BSTs através de várias fontes, mas não encontrei nenhuma boa descrição detalhando qual é melhor usar em diferentes situações (ou se realmente não importa).

eu quero um BST isso é ideal para armazenar mais de dez milhões de nós.A ordem de inserção dos nós é basicamente aleatória, e nunca precisarei deletar nós, então o tempo de inserção é a única coisa que precisaria ser otimizada.

Pretendo usá-lo para armazenar estados de jogos visitados anteriormente em um jogo de quebra-cabeça, para poder verificar rapidamente se uma configuração anterior já foi encontrada.

Answer 1

Vermelho preto é melhor que AVL para aplicativos com muita inserção.Se você prevê uma aparência relativamente uniforme, então o Rubro-Negro é o caminho a seguir.Se você prevê uma pesquisa relativamente desequilibrada, onde os elementos visualizados mais recentemente têm maior probabilidade de serem visualizados novamente, você deseja usar espalhar árvores.

Answer 2

Por que usar um BST de forma alguma?Pela sua descrição, um dicionário funcionará tão bem, se não melhor.

A única razão para usar um BST seria se você quisesse listar o conteúdo do contêiner em ordem de chave.Certamente não parece que você queira fazer isso; nesse caso, vá para a tabela hash. O(1) inserção e pesquisa, não se preocupe com exclusão, o que poderia ser melhor?

Answer 3

Os dois auto-equilíbrio BSTque estou mais familiarizado são rubro-negros e AVL, então não posso dizer com certeza se alguma outra solução é melhor, mas pelo que me lembro, o vermelho-preto tem inserção mais rápida e recuperação mais lenta em comparação com AVL.

Portanto, se a inserção tiver uma prioridade mais alta do que a recuperação, o vermelho-preto pode ser uma solução melhor.

Answer 4

[tabelas hash têm] inserção e pesquisa O (1)

Acho que isso está errado.

Primeiro de tudo, se você limitar o keyspace para ser finito, poderá armazenar os elementos em uma matriz e fazer uma varredura linear O(1).Ou você pode ordenar aleatoriamente a matriz e, em seguida, fazer uma varredura linear no tempo esperado O(1).Quando o material é finito, o material é facilmente O(1).

Então, digamos que sua tabela hash armazene qualquer sequência de bits arbitrária;isso não importa muito, desde que haja um conjunto infinito de chaves, cada uma delas finita.Então você tem que ler todos os bits de qualquer consulta e entrada de inserção, caso contrário eu insiro y0 em um hash vazio e consulto em y1, onde y0 e y1 diferem em uma única posição de bit que você não olha.

Mas digamos que os comprimentos das chaves não sejam um parâmetro.Se sua inserção e pesquisa levarem O(1), em particular o hashing leva tempo O(1), o que significa que você olha apenas para uma quantidade finita de saída da função hash (da qual é provável que ser apenas uma produção finita, concedida).

Isso significa que com um número finito de buckets, deve haver um conjunto infinito de strings, todas com o mesmo valor de hash.Suponha que eu insira muito, ou seja,ω(1), desses, e comece a consultar.Isso significa que sua tabela hash precisa recorrer a algum outro mecanismo de inserção/pesquisa O(1) para responder às minhas perguntas.Qual e por que não usá-lo diretamente?