Vantagens da estrutura de dados Trie
Tries é uma árvore que armazena strings. O número máximo de filhos de um nó é igual ao tamanho do alfabeto. Trie oferece suporte a operações de pesquisa, inserção e exclusão em tempo O (L), onde L é o comprimento da chave.
Hashing : - No hashing, convertemos a chave em um valor pequeno e o valor é usado para indexar dados. O hash suporta operações de pesquisa, inserção e exclusão em tempo O (L) em média.
BST de auto-equilíbrio: A complexidade de tempo das operações de pesquisa, inserção e exclusão em uma árvore de pesquisa binária de auto-equilíbrio (BST) (como Red-Black Tree , AVL Tree , Splay Tree , etc) é O (L * Log n) onde n é o número total de palavras e L é o comprimento da palavra. A vantagem dos BSTs com autobalanceamento é que eles mantêm a ordem, o que torna mais rápidas as operações de mínimo, máximo, mais próximo (piso ou teto) e k-ésimo maior. Consulte Vantagens do BST sobre a tabela de hash para obter detalhes.
Por que Trie? : -
- Com Trie, podemos inserir e encontrar strings no tempo O (L), onde L representa o comprimento de uma única palavra. Obviamente, isso é mais rápido do que o BST. Isso também é mais rápido do que o hash devido à maneira como é implementado. Não precisamos calcular nenhuma função hash. Nenhum tratamento de colisão é necessário (como fazemos no endereçamento aberto e encadeamento separado )
- Outra vantagem do Trie é que podemos imprimir facilmente todas as palavras em ordem alfabética, o que não é possível com o hash.
- Podemos fazer pesquisa de prefixo (ou autocompletar) de maneira eficiente com o Trie .
Problemas com Trie: -
A principal desvantagem das tentativas é que precisam de muita memória para armazenar as strings. Para cada nó, temos muitos ponteiros de nó (igual ao número de caracteres do alfabeto), se o espaço estiver em causa, então a Árvore de Pesquisa Ternária pode ser preferida para implementações de dicionário. Na árvore de pesquisa ternária, a complexidade de tempo da operação de pesquisa é O (h), onde h é a altura da árvore. Árvores de pesquisa ternárias também suportam outras operações suportadas pelo Trie, como pesquisa de prefixo, impressão em ordem alfabética e pesquisa de vizinho mais próximo.
A conclusão final em relação à estrutura de dados das tentativas é que eles são mais rápidos, mas requerem muita memória para armazenar as strings.
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva