A imagem de capa deste artigo foi retirada da Wikipedia
Este post tem um carinho especial, pois minha falta de conhecimento sobre Trie foi o motivo de eu não passar para os próximos passos de uma entrevista com a Amazon há um tempo atrás, na época em que eu atuava como o equivalente à um “Desenvolvedor Pleno”.
Tries são estruturas magníficas que pouquíssimos desenvolvedores conhecem. E não, por incrível que pareça, o termo “Trie” não está errado (todos perguntam isso, inclusive eu!) e sim, ela tem relação com árvores (Trees).
Neste post abordaremos todo o conhecimento necessário sobre Tries!
O que é uma Trie?
A Trie, também chamada de árvore prefixada ou árvore digital, é uma estrutura de dados em forma de árvore usada principalmente para armazenar strings de forma eficiente, especialmente quando há sobreposição de prefixos.
Cada nó em uma Trie representa um caractere de uma string, e as strings são construídas percorrendo os nós. Por exemplo, ao armazenar as palavras gato, galo e galho, os prefixos comuns (ga) são compartilhados, economizando espaço.
Exemplo visual de uma Trie armazenando essas palavras:
Trie vs. Árvores Comuns
Embora as Tries sejam tecnicamente árvores, elas têm características específicas que as diferenciam de outras estruturas comuns, como árvores binárias de busca (BSTs):
| Característica | Trie | Árvores Comuns (ex.: BST) |
|---|---|---|
| Foco | Operações com strings | Qualquer tipo de dado |
| Organização | Baseada em prefixos | Baseada em valores (ex.: menor à esquerda, maior à direita) |
| Espaço | Compartilha prefixos | Não há compartilhamento de prefixos |
| Eficiência | Busca rápida por strings específicas | Depende do balanceamento da árvore |
Análise de Complexidade
Tempo de Execução
- Inserção e Busca: O tempo de execução depende do comprimento da string n, e não do número de strings armazenadas:
- Inserção: O(n)
- Busca: O(n)
- Remoção: O(n)
Uso de Memória
O uso de memória é maior em Tries do que em outras árvores, porque cada nó precisa armazenar:
- Caractere.
- Ponteiros para os próximos caracteres.
- Um marcador indicando o fim de uma palavra.
Para uma grande quantidade de dados, especialmente com poucos prefixos comuns, o custo de memória pode se tornar proibitivo.
Implementação de uma Trie em Python
Aqui está uma implementação básica de uma Trie em Python:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
Métodos Comuns em uma Trie
insert(word): Insere uma palavra na Trie.search(word): Retorna se uma palavra existe na Trie.starts_with(prefix): Verifica se há palavras que começam com um prefixo.- delete(opcional): Remove palavras da Trie, ajustando nós desnecessários.
Por que usar uma Trie?
- Busca Rápida: Ideal para sistemas de autocomplete ou dicionários.
- Prefixos Compartilhados: Reduz duplicação e economiza espaço para palavras com prefixos comuns.
- Operações Previsíveis: O tempo de execução é constante para strings de mesmo comprimento, independentemente do número de palavras armazenadas.
Exemplos de uso
- Motores de busca.
- Autocorreção em editores de texto.
- Sistemas de prefixos telefônicos.
Por que não usar uma Trie?
- Uso de Memória: Tries consomem mais memória que listas ou árvores binárias, especialmente quando há poucas semelhanças entre os dados.
- Implementação Complexa: Embora não seja extremamente difícil, a implementação de Tries pode ser mais trabalhosa do que alternativas mais simples.
Um pequeno desafio
Vamos simular um pouco do uso da Trie, mais na prática? Tente resolver o problema abaixo
Você está desenvolvendo um aplicativo de lista de contatos e precisa implementar um sistema eficiente para realizar buscas por nomes. O objetivo é criar uma funcionalidade que permita:
- Adicionar Contatos: Inserir novos nomes na lista.
- Buscar por Nome Completo: Verificar se um nome específico está na lista.
- Buscar por Prefixo: Retornar todos os contatos que começam com um determinado prefixo.
Exemplo de Entrada e Saída:
Operações:
1. Inserir: ["Ana", "André", "Beatriz", "Bruno"]
2. Buscar por nome completo: "Ana"
3. Buscar por prefixo: "An" -> ["Ana", "André"]
4. Buscar por prefixo: "B" -> ["Beatriz", "Bruno"]
5. Buscar por nome completo: "Carlos"
DICA: Este é um cenário ideal para o uso de Tries 😉
Requisitos
- Deve ser possível inserir milhões de contatos com eficiência.
- As buscas por prefixo devem ser rápidas, mesmo com uma grande lista.
Implemente as funções principais para atender às operações acima.
Conclusão
A Trie é uma estrutura de dados poderosa para trabalhar com strings e é indispensável em contextos onde busca rápida e prefixos comuns são cruciais. Contudo, ela deve ser usada com cautela, especialmente se a memória for um recurso limitado.
Ao considerar Tries para o seu projeto, avalie a necessidade real e compare com alternativas como tabelas hash ou árvores binárias. Se bem empregada, a Trie pode ser um divisor de águas em performance e organização.
