Introdução
A Trie (pronuncia-se “try”, do inglês “retrieval”) é uma estrutura de dados em árvore especializada em armazenar e buscar strings (ou sequências) de forma extremamente eficiente. Diferentemente das árvores de busca que comparam chaves inteiras, a Trie armazena caracteres individualmente nos nós, compartilhando prefixos comuns entre as chaves.
Inventada por Edward Fredkin em 1960, a Trie é a estrutura por trás de funcionalidades como autocompletar em mecanismos de busca, correção ortográfica, roteamento IP e dicionários de palavras. Sua grande vantagem é que a busca por uma string de comprimento m custa O(m), independente de quantas strings estão armazenadas.
Conceito e Teoria
Estrutura da Trie
Cada nó da Trie representa um caractere. O caminho da raiz até qualquer nó forma um prefixo. Nós marcados como “fim de palavra” indicam que o caminho da raiz até eles forma uma palavra completa.
Palavras: "rust", "run", "ruby", "rato", "rápido"
Raiz (vazio)
└── r
├── u
│ ├── s
│ │ └── t* ← "rust"
│ ├── n* ← "run"
│ └── b
│ └── y* ← "ruby"
├── a
│ ├── t
│ │ └── o* ← "rato"
│ └── p (á → a para simplificar)
│ └── i
│ └── d
│ └── o* ← "rápido"
* = fim de palavra
Observações:
- "rust", "run" e "ruby" compartilham o prefixo "ru"
- "rato" e "rápido" compartilham o prefixo "ra"
- Buscar "ru" retorna 3 sugestões
Operações Fundamentais
Inserir "gato":
Passo 1: Raiz → 'g' existe? Não → criar
Raiz
└── g
Passo 2: 'g' → 'a' existe? Não → criar
Raiz
└── g
└── a
Passo 3: 'a' → 't' existe? Não → criar
Raiz
└── g
└── a
└── t
Passo 4: 't' → 'o' existe? Não → criar, marcar como fim
Raiz
└── g
└── a
└── t
└── o*
Buscar "gato": g ✓ → a ✓ → t ✓ → o* ✓ → Encontrado!
Buscar "gat": g ✓ → a ✓ → t (sem *) → Não é palavra completa
Buscar "galo": g ✓ → a ✓ → l ✗ → Não encontrado
Prefixo "ga": g ✓ → a ✓ → Prefixo existe!
Trie Comprimida (Radix Tree / Patricia Tree)
Quando muitos nós têm apenas um filho, podemos comprimir caminhos:
Trie normal: Trie comprimida:
Raiz Raiz
└── r └── r
└── u ├── u
├── s │ ├── st*
│ └── t* │ ├── n*
├── n* │ └── by*
└── b └── a
└── y* ├── to*
└── a └── pido*
└── t
└── o*
Economia: de 12 nós para 8 nós (33% menos memória)
Complexidade
| Operação | Complexidade | Observação |
|---|---|---|
| Inserir | O(m) | m = comprimento da string |
| Buscar | O(m) | Independe do número total de strings |
| Buscar prefixo | O(m) | Verifica se alguma string começa com… |
| Remover | O(m) | Pode precisar limpar nós órfãos |
| Autocompletar | O(m + k) | m = prefixo, k = resultados |
| Espaço | O(n * m) | n = número de strings, m = comprimento médio |
Nota: A complexidade de busca O(m) é muito vantajosa quando temos milhões de strings. Em uma BST balanceada, a busca seria O(m * log n), pois cada comparação de string custa O(m).
Implementação em Rust
use std::collections::HashMap;
/// Nó da Trie
#[derive(Debug, Default)]
struct NoTrie {
filhos: HashMap<char, NoTrie>,
fim_de_palavra: bool,
/// Contador de quantas palavras passam por este nó
contagem_prefixo: usize,
}
/// Trie (Árvore de Prefixos)
#[derive(Debug, Default)]
struct Trie {
raiz: NoTrie,
total_palavras: usize,
}
impl Trie {
/// Cria uma Trie vazia
fn nova() -> Self {
Trie {
raiz: NoTrie::default(),
total_palavras: 0,
}
}
/// Retorna o número total de palavras armazenadas
fn tamanho(&self) -> usize {
self.total_palavras
}
/// Insere uma palavra na Trie
fn inserir(&mut self, palavra: &str) {
let mut atual = &mut self.raiz;
for ch in palavra.chars() {
atual.contagem_prefixo += 1;
atual = atual.filhos.entry(ch).or_default();
}
// Marca como fim de palavra (evita duplicatas)
if !atual.fim_de_palavra {
atual.fim_de_palavra = true;
atual.contagem_prefixo += 1;
self.total_palavras += 1;
}
}
/// Busca uma palavra exata na Trie
fn buscar(&self, palavra: &str) -> bool {
let mut atual = &self.raiz;
for ch in palavra.chars() {
match atual.filhos.get(&ch) {
Some(proximo) => atual = proximo,
None => return false,
}
}
atual.fim_de_palavra
}
/// Verifica se existe alguma palavra com o prefixo dado
fn comeca_com(&self, prefixo: &str) -> bool {
let mut atual = &self.raiz;
for ch in prefixo.chars() {
match atual.filhos.get(&ch) {
Some(proximo) => atual = proximo,
None => return false,
}
}
true
}
/// Conta quantas palavras começam com o prefixo dado
fn contar_com_prefixo(&self, prefixo: &str) -> usize {
let mut atual = &self.raiz;
for ch in prefixo.chars() {
match atual.filhos.get(&ch) {
Some(proximo) => atual = proximo,
None => return 0,
}
}
atual.contagem_prefixo
}
/// Retorna todas as palavras que começam com o prefixo dado
fn autocompletar(&self, prefixo: &str, limite: usize) -> Vec<String> {
let mut atual = &self.raiz;
// Navega até o nó do prefixo
for ch in prefixo.chars() {
match atual.filhos.get(&ch) {
Some(proximo) => atual = proximo,
None => return Vec::new(),
}
}
// Coleta todas as palavras a partir deste nó
let mut resultados = Vec::new();
let mut caminho = prefixo.to_string();
Self::coletar_palavras(atual, &mut caminho, &mut resultados, limite);
resultados
}
/// Coleta palavras recursivamente a partir de um nó
fn coletar_palavras(
no: &NoTrie,
caminho: &mut String,
resultados: &mut Vec<String>,
limite: usize,
) {
if resultados.len() >= limite {
return;
}
if no.fim_de_palavra {
resultados.push(caminho.clone());
}
// Itera sobre os filhos em ordem alfabética
let mut filhos: Vec<_> = no.filhos.iter().collect();
filhos.sort_by_key(|(ch, _)| *ch);
for (ch, filho) in filhos {
caminho.push(*ch);
Self::coletar_palavras(filho, caminho, resultados, limite);
caminho.pop();
if resultados.len() >= limite {
return;
}
}
}
/// Remove uma palavra da Trie
fn remover(&mut self, palavra: &str) -> bool {
if !self.buscar(palavra) {
return false;
}
Self::remover_rec(&mut self.raiz, palavra, 0);
self.total_palavras -= 1;
true
}
/// Remoção recursiva — retorna true se o nó pode ser removido
fn remover_rec(no: &mut NoTrie, palavra: &str, profundidade: usize) -> bool {
let chars: Vec<char> = palavra.chars().collect();
if profundidade == chars.len() {
no.fim_de_palavra = false;
no.contagem_prefixo -= 1;
return no.filhos.is_empty();
}
let ch = chars[profundidade];
if let Some(filho) = no.filhos.get_mut(&ch) {
let pode_remover = Self::remover_rec(filho, palavra, profundidade + 1);
if pode_remover {
no.filhos.remove(&ch);
}
}
no.contagem_prefixo -= 1;
!no.fim_de_palavra && no.filhos.is_empty()
}
/// Retorna todas as palavras armazenadas na Trie (em ordem)
fn todas_palavras(&self) -> Vec<String> {
let mut resultados = Vec::new();
let mut caminho = String::new();
Self::coletar_palavras(&self.raiz, &mut caminho, &mut resultados, usize::MAX);
resultados
}
/// Encontra a maior palavra que é prefixo da entrada
fn maior_prefixo(&self, texto: &str) -> String {
let mut atual = &self.raiz;
let mut ultimo_prefixo = String::new();
let mut caminho = String::new();
for ch in texto.chars() {
match atual.filhos.get(&ch) {
Some(proximo) => {
caminho.push(ch);
atual = proximo;
if atual.fim_de_palavra {
ultimo_prefixo = caminho.clone();
}
}
None => break,
}
}
ultimo_prefixo
}
}
fn main() {
let mut trie = Trie::nova();
// Inserir palavras
let palavras = vec![
"rust", "rustlings", "rustico", "rota", "roteiro",
"programa", "programar", "programacao", "projeto",
"python", "performance", "compilador",
];
println!("Inserindo palavras:");
for palavra in &palavras {
trie.inserir(palavra);
println!(" + {}", palavra);
}
println!("\nTotal de palavras: {}", trie.tamanho());
// Busca
println!("\n=== Busca ===");
println!(" 'rust' existe: {}", trie.buscar("rust"));
println!(" 'rustico' existe: {}", trie.buscar("rustico"));
println!(" 'ruby' existe: {}", trie.buscar("ruby"));
// Busca por prefixo
println!("\n=== Busca por Prefixo ===");
println!(" Prefixo 'ru' existe: {}", trie.comeca_com("ru"));
println!(" Palavras com 'ru': {}", trie.contar_com_prefixo("ru"));
println!(" Prefixo 'xyz' existe: {}", trie.comeca_com("xyz"));
// Autocompletar
println!("\n=== Autocompletar ===");
let sugestoes = trie.autocompletar("pro", 10);
println!(" 'pro' → {:?}", sugestoes);
let sugestoes = trie.autocompletar("rust", 10);
println!(" 'rust' → {:?}", sugestoes);
let sugestoes = trie.autocompletar("r", 5);
println!(" 'r' (máx 5) → {:?}", sugestoes);
// Maior prefixo
println!("\n=== Maior Prefixo ===");
println!(
" Maior prefixo de 'programacao_avancada': '{}'",
trie.maior_prefixo("programacao_avancada")
);
// Remoção
println!("\n=== Remoção ===");
println!(" Remover 'rust': {}", trie.remover("rust"));
println!(" 'rust' existe: {}", trie.buscar("rust"));
println!(" 'rustlings' existe: {}", trie.buscar("rustlings"));
println!(" Total: {}", trie.tamanho());
// Todas as palavras
println!("\n=== Todas as palavras (ordenadas) ===");
for palavra in trie.todas_palavras() {
println!(" {}", palavra);
}
}
Métodos Principais
| Método | Descrição |
|---|---|
nova() | Cria uma Trie vazia |
inserir(palavra) | Insere uma palavra na Trie |
buscar(palavra) | Retorna true se a palavra exata existe |
comeca_com(prefixo) | Retorna true se alguma palavra começa com o prefixo |
contar_com_prefixo(prefixo) | Conta palavras que começam com o prefixo |
autocompletar(prefixo, lim) | Retorna até lim palavras que começam com o prefixo |
remover(palavra) | Remove uma palavra da Trie |
todas_palavras() | Retorna todas as palavras armazenadas (ordenadas) |
maior_prefixo(texto) | Encontra a maior palavra que é prefixo do texto |
tamanho() | Retorna o número total de palavras |
Exemplo Prático: Sistema de Autocompletar
use std::collections::HashMap;
/// Nó da Trie com pontuação de popularidade
#[derive(Debug, Default)]
struct NoAutocompletar {
filhos: HashMap<char, NoAutocompletar>,
fim_de_palavra: bool,
popularidade: u32, // Quantas vezes a busca foi feita
}
/// Sistema de autocompletar com ranking por popularidade
#[derive(Debug, Default)]
struct Autocompletar {
raiz: NoAutocompletar,
}
impl Autocompletar {
fn novo() -> Self {
Autocompletar::default()
}
/// Registra uma consulta (ou incrementa popularidade se já existe)
fn registrar_consulta(&mut self, consulta: &str) {
let mut atual = &mut self.raiz;
for ch in consulta.to_lowercase().chars() {
atual = atual.filhos.entry(ch).or_default();
}
atual.fim_de_palavra = true;
atual.popularidade += 1;
}
/// Retorna sugestões ordenadas por popularidade
fn sugerir(&self, prefixo: &str, limite: usize) -> Vec<(String, u32)> {
let mut atual = &self.raiz;
let prefixo_lower = prefixo.to_lowercase();
// Navega até o nó do prefixo
for ch in prefixo_lower.chars() {
match atual.filhos.get(&ch) {
Some(proximo) => atual = proximo,
None => return Vec::new(),
}
}
// Coleta todas as sugestões
let mut sugestoes = Vec::new();
let mut caminho = prefixo_lower.clone();
Self::coletar(atual, &mut caminho, &mut sugestoes);
// Ordena por popularidade (decrescente)
sugestoes.sort_by(|a, b| b.1.cmp(&a.1));
sugestoes.truncate(limite);
sugestoes
}
fn coletar(
no: &NoAutocompletar,
caminho: &mut String,
resultados: &mut Vec<(String, u32)>,
) {
if no.fim_de_palavra {
resultados.push((caminho.clone(), no.popularidade));
}
let mut filhos: Vec<_> = no.filhos.iter().collect();
filhos.sort_by_key(|(ch, _)| *ch);
for (ch, filho) in filhos {
caminho.push(*ch);
Self::coletar(filho, caminho, resultados);
caminho.pop();
}
}
}
fn main() {
let mut sistema = Autocompletar::novo();
// Simular histórico de buscas
let historico = vec![
("rust programming", 50),
("rust tutorial", 30),
("rust vs go", 20),
("rust game engine", 15),
("rust web framework", 25),
("ruby on rails", 40),
("react hooks", 35),
("react native", 28),
("redis cache", 22),
("rest api", 18),
];
println!("=== Registrando histórico de buscas ===");
for (consulta, vezes) in &historico {
for _ in 0..*vezes {
sistema.registrar_consulta(consulta);
}
println!(" '{}' ({} vezes)", consulta, vezes);
}
// Simulação de autocompletar
println!("\n=== Autocompletar ===");
let prefixos = vec!["ru", "re", "rust", "r"];
for prefixo in prefixos {
let sugestoes = sistema.sugerir(prefixo, 5);
println!("\n Digitou: '{}'", prefixo);
if sugestoes.is_empty() {
println!(" (sem sugestões)");
} else {
for (i, (texto, pop)) in sugestoes.iter().enumerate() {
println!(" {}. {} (popularidade: {})", i + 1, texto, pop);
}
}
}
}
Aplicação: Roteamento IP com Trie
/// Simula uma tabela de roteamento IP usando Trie binária
/// Cada bit do endereço IP é um nó na Trie
#[derive(Debug, Default)]
struct NoRota {
filhos: [Option<Box<NoRota>>; 2], // 0 e 1
interface: Option<String>, // Nome da interface de saída
}
struct TabelaRoteamento {
raiz: NoRota,
}
impl TabelaRoteamento {
fn nova() -> Self {
TabelaRoteamento {
raiz: NoRota::default(),
}
}
/// Adiciona uma rota (prefixo em bits + interface)
fn adicionar_rota(&mut self, prefixo_bits: &str, interface: &str) {
let mut atual = &mut self.raiz;
for bit in prefixo_bits.chars() {
let indice = (bit as u8 - b'0') as usize;
if atual.filhos[indice].is_none() {
atual.filhos[indice] = Some(Box::new(NoRota::default()));
}
atual = atual.filhos[indice].as_mut().unwrap();
}
atual.interface = Some(interface.to_string());
}
/// Encontra a rota mais específica para um IP (longest prefix match)
fn buscar_rota(&self, ip_bits: &str) -> Option<String> {
let mut atual = &self.raiz;
let mut melhor_rota = atual.interface.clone();
for bit in ip_bits.chars() {
let indice = (bit as u8 - b'0') as usize;
match &atual.filhos[indice] {
Some(proximo) => {
atual = proximo;
if atual.interface.is_some() {
melhor_rota = atual.interface.clone();
}
}
None => break,
}
}
melhor_rota
}
}
fn main() {
let mut tabela = TabelaRoteamento::nova();
// Rotas simplificadas (8 bits para demonstração)
tabela.adicionar_rota("0", "eth0"); // 0.0.0.0/1 → padrão
tabela.adicionar_rota("10", "eth1"); // 128.0.0.0/2
tabela.adicionar_rota("1010", "eth2"); // 160.0.0.0/4
tabela.adicionar_rota("10101100", "eth3"); // 172.x.x.x/8
println!("=== Tabela de Roteamento ===");
println!(" 0.0.0.0/1 → eth0");
println!(" 128.0.0.0/2 → eth1");
println!(" 160.0.0.0/4 → eth2");
println!(" 172.x.x.x/8 → eth3");
// Buscar rotas (longest prefix match)
let ips = vec![
("01100100", "100.x.x.x"),
("10000001", "129.x.x.x"),
("10100000", "160.x.x.x"),
("10101100", "172.x.x.x"),
];
println!("\n=== Busca de Rotas ===");
for (bits, descricao) in ips {
let rota = tabela.buscar_rota(bits).unwrap_or("nenhuma".to_string());
println!(" {} ({}) → {}", descricao, bits, rota);
}
}
Comparação com Outras Estruturas
| Critério | Trie | HashMap | BTreeMap | Array Ordenado |
|---|---|---|---|---|
| Busca exata | O(m) | O(m)* | O(m * log n) | O(m * log n) |
| Busca por prefixo | O(m + k) | O(n * m) | O(m * log n) | O(m * log n) |
| Inserção | O(m) | O(m)* | O(m * log n) | O(n) |
| Autocompletar | O(m + k) | O(n * m) | O(m * log n + k) | O(m * log n + k) |
| Uso de memória | Alto | Médio | Médio | Baixo |
| Dados ordenados | Sim (alfab.) | Não | Sim | Sim |
* m = comprimento da string, n = número de strings, k = resultados.
Quando usar Trie?
- Use para autocompletar e busca por prefixo.
- Use para dicionários com busca frequente por palavras que começam com um prefixo.
- Use para roteamento IP (longest prefix match).
- Use para verificação ortográfica e correção de palavras.
- Não use se o espaço em memória é crítico — Tries consomem muita memória com conjuntos esparsos.
- Não use para busca exata simples —
HashMapé mais eficiente e consome menos memória.
Exercícios
Exercício 1: Verificação Ortográfica
Implemente um corretor ortográfico simples que, dada uma palavra não encontrada na Trie, sugira palavras similares. Use a estratégia de gerar todas as variações de 1 edição (inserção, remoção, substituição, transposição de caracteres adjacentes) e verificar quais existem na Trie.
Entrada: "ruts" (não existe)
Sugestões: ["rust", "ruts" → "rust" (substituição u↔t), "runs", "ruts"]
Exercício 2: Trie Comprimida (Radix Tree)
Modifique a implementação para comprimir caminhos onde nós têm um único filho. Em vez de armazenar um caractere por nó, armazene strings inteiras nas arestas. Compare o uso de memória entre a Trie normal e a comprimida para um dicionário de 10.000 palavras.
Exercício 3: Contador de Palavras em Texto
Use uma Trie para contar a frequência de cada palavra em um texto. Implemente os métodos processar_texto(texto: &str) e top_k(k: usize) -> Vec<(String, usize)> que retorna as k palavras mais frequentes. Compare o desempenho com uma solução usando HashMap.
Conclusão
A Trie é uma estrutura de dados poderosa e especializada que brilha em cenários envolvendo busca por prefixo e manipulação de strings. Sua capacidade de compartilhar prefixos comuns entre milhares de strings a torna ideal para sistemas de autocompletar, dicionários e tabelas de roteamento.
Em Rust, a implementação usando HashMap<char, NoTrie> oferece flexibilidade para qualquer conjunto de caracteres (incluindo Unicode), enquanto alternativas com arrays de tamanho fixo podem ser mais eficientes para conjuntos de caracteres limitados (como ASCII). O sistema de ownership de Rust garante que a memória da Trie é gerenciada automaticamente, eliminando vazamentos mesmo em operações complexas como remoção recursiva.
Para cenários de produção em Rust, considere bibliotecas como fst (Finite State Transducer) para conjuntos de strings imutáveis e compactos, ou trie-rs para uma implementação genérica otimizada. A compreensão da Trie, porém, é fundamental para qualquer programador que trabalhe com processamento de texto ou networking.