MATERIAL
1 Motivação
2 Introdução
3 Implementação
4 Comparações
5 Variações e otimizações
6 Aplicações no mundo real
7 Guia para resolução de problemas
7.1 Dicas
7.1.1 Quando usar uma Trie?
Passo 1: Analisar problema
A primeira pergunta que você deve se fazer é:
"Que tipos de dados envolve o problema e qual a sua unidade mais básica? "
Se a resposta para essa pergunta envolver uma sequência construida através de um alfabeto(conjunto FINITO de símbolos), preste bem atenção no finito, essa é uma das premissas chaves, veremos no passo 3 que o tamanho desse conjunto impactará diretamente no consumo de memória. Nesse caso, é um bom sinal de que o problema pode ser resolvido com Trie.
Pois em sua essência, Trie é uma estrutura otimizada para armazenar e consultar sequências. As sequências mais comuns são as strings, nesse caso, o alfabeto são os caractêres. No entanto, o conceito é bem mais amplo, pode ser uma sequência de digitos, como números de telefones, ou até uma sequência de bits.
Passo 2: Analisar quais as operações chave para resolver o problema.
Próxima pergunta que você deve fazer, é quais as operações chaves que preciso para resolver o problema, se as operações são baseadas em prefixos, Trie é disparada uma das estruturas de dados que você deve levar em consideração. Ela materializa a ideia de prefixo em sua estrutura, a sua eficiência para suas operações são geralmente O(L), onde L é o comprimento do prefixo. Por exemplo:
- "Liste todas as palavras que começam com ..."(autocompletar)
- "Verifique se tem alguma palavra com prefixo ..."
Passo 3: Botar em consideração as restrições de tempo e espaço do problema
Tendo Trie como um ótimo candidato, devemos nos perguntar, será ela a estrutura certa? Ela é realmente a melhor opção?
A Trie é muito boa em remover, inserir, e buscar uma sequência de comprimento L, independente do número total de palavras no dicionário.
Qual o problema da Trie? Memória!
Para cada nó, pode ter ponteiros para cada elemento no alfabeto, desse modo, se o alfabeto é muito grande, se torna inviavel para implementação de Trie padrão. Então é preciso se perguntar:
"O afalbeto é pequeno ou é muito grande?"
Bom, e no caso de ser inviável? Considere variações de Trie com otmizações de memória, como uma TST, ou algumas otimizações como guardar um mapa de hash em cada nó invés de uma array fixo, economiza mais memória em troca de um pouco de velocidade.