A Trie (pronuncia-se “trai”, de retrieval) e uma estrutura de dados em arvore especializada para armazenar e buscar strings de forma extremamente eficiente. Enquanto uma busca em uma lista de palavras custa O(n*m) e em uma tabela hash pode ter colisoes, a Trie garante busca, insercao e remocao em O(m), onde m e o comprimento da string – independentemente de quantas strings estao armazenadas.
A Trie e a estrutura por tras de funcionalidades como autocompletar em motores de busca, verificacao ortografica, roteamento de IP e dicionarios. Em Rust, implementar uma Trie e um excelente exercicio que explora os conceitos de ownership, Box<T> para alocacao no heap e HashMap para filhos dinamicos.
Como Funciona
Cada no da Trie representa um caractere. O caminho da raiz ate um no forma um prefixo. Nos marcados como “fim de palavra” indicam que o caminho da raiz ate ali forma uma palavra completa.
Inserindo: "rust", "run", "runner", "ruby", "go"
(raiz)
/ \
r g
/ \ \
u . o*
/|\
s n b
| | |
t* | y*
*
n
|
e
|
r*
Legenda: * = fim de palavra
Busca "run":
raiz -> r (existe) -> u (existe) -> n (existe, marcado *) -> ENCONTRADO
Busca "ru":
raiz -> r (existe) -> u (existe, NAO marcado *) -> NAO E PALAVRA
(mas e um prefixo valido!)
Busca "rat":
raiz -> r (existe) -> a (NAO existe) -> NAO ENCONTRADO
Estrutura de um No
+------------------+
| No Trie |
+------------------+
| filhos: HashMap | -> mapeia char para No filho
| fim_palavra: bool| -> indica se aqui termina uma palavra
+------------------+
|
v
'a' -> No { filhos: {...}, fim_palavra: false }
'b' -> No { filhos: {...}, fim_palavra: true }
...
Complexidade
| Operacao | Tempo | Espaco |
|---|---|---|
| Insercao | O(m) | O(m) |
| Busca | O(m) | O(1) |
| Busca por prefixo | O(m) | O(1) |
| Remocao | O(m) | O(1) |
| Autocompletar | O(m+k) | O(k) |
| Espaco total | – | O(N*A) |
Onde m = comprimento da string, k = numero de resultados, N = total de caracteres armazenados, A = tamanho do alfabeto. O uso de HashMap para filhos reduz o espaco quando o alfabeto e grande e esparsamente usado.
Implementacao em Rust
use std::collections::HashMap;
/// Representa um no da Trie.
/// Cada no possui um mapa de filhos (caractere -> no filho)
/// e um indicador de fim de palavra.
#[derive(Debug, Default)]
struct NoTrie {
filhos: HashMap<char, Box<NoTrie>>,
fim_palavra: bool,
}
/// Estrutura principal da Trie.
#[derive(Debug, Default)]
struct Trie {
raiz: NoTrie,
}
impl Trie {
/// Cria uma nova Trie vazia.
fn nova() -> Self {
Trie {
raiz: NoTrie::default(),
}
}
/// Insere uma palavra na Trie.
fn inserir(&mut self, palavra: &str) {
let mut no_atual = &mut self.raiz;
for ch in palavra.chars() {
// entry() cria o filho se nao existir
no_atual = no_atual
.filhos
.entry(ch)
.or_insert_with(|| Box::new(NoTrie::default()));
}
no_atual.fim_palavra = true;
}
/// Verifica se uma palavra exata existe na Trie.
fn buscar(&self, palavra: &str) -> bool {
let mut no_atual = &self.raiz;
for ch in palavra.chars() {
match no_atual.filhos.get(&ch) {
Some(filho) => no_atual = filho,
None => return false,
}
}
no_atual.fim_palavra
}
/// Verifica se alguma palavra na Trie comeca com o prefixo dado.
fn comeca_com(&self, prefixo: &str) -> bool {
let mut no_atual = &self.raiz;
for ch in prefixo.chars() {
match no_atual.filhos.get(&ch) {
Some(filho) => no_atual = filho,
None => return false,
}
}
true // chegou ao final do prefixo, logo ele existe
}
/// Retorna todas as palavras que comecam com o prefixo dado.
fn autocompletar(&self, prefixo: &str) -> Vec<String> {
let mut no_atual = &self.raiz;
// Navega ate o no do prefixo
for ch in prefixo.chars() {
match no_atual.filhos.get(&ch) {
Some(filho) => no_atual = filho,
None => return Vec::new(),
}
}
// Coleta todas as palavras a partir deste no
let mut resultados = Vec::new();
let mut palavra_atual = prefixo.to_string();
Self::coletar_palavras(no_atual, &mut palavra_atual, &mut resultados);
resultados
}
/// Funcao auxiliar recursiva para coletar palavras.
fn coletar_palavras(no: &NoTrie, palavra_atual: &mut String, resultados: &mut Vec<String>) {
if no.fim_palavra {
resultados.push(palavra_atual.clone());
}
// Ordena as chaves para resultados deterministicos
let mut chaves: Vec<&char> = no.filhos.keys().collect();
chaves.sort();
for &ch in &chaves {
if let Some(filho) = no.filhos.get(ch) {
palavra_atual.push(*ch);
Self::coletar_palavras(filho, palavra_atual, resultados);
palavra_atual.pop();
}
}
}
/// Remove uma palavra da Trie.
/// Retorna true se a palavra existia e foi removida.
fn remover(&mut self, palavra: &str) -> bool {
Self::remover_recursivo(&mut self.raiz, palavra, 0)
}
fn remover_recursivo(no: &mut NoTrie, palavra: &str, profundidade: usize) -> bool {
let chars: Vec<char> = palavra.chars().collect();
if profundidade == chars.len() {
// Chegamos ao final da palavra
if !no.fim_palavra {
return false; // palavra nao existe
}
no.fim_palavra = false;
return no.filhos.is_empty(); // pode remover se nao tem filhos
}
let ch = chars[profundidade];
if let Some(filho) = no.filhos.get_mut(&ch) {
let deve_remover_filho = Self::remover_recursivo(filho, palavra, profundidade + 1);
if deve_remover_filho {
no.filhos.remove(&ch);
// Pode remover este no se nao e fim de palavra e nao tem filhos
return !no.fim_palavra && no.filhos.is_empty();
}
}
false
}
/// Conta o numero total de palavras na Trie.
fn contar_palavras(&self) -> usize {
Self::contar_recursivo(&self.raiz)
}
fn contar_recursivo(no: &NoTrie) -> usize {
let mut contagem = if no.fim_palavra { 1 } else { 0 };
for filho in no.filhos.values() {
contagem += Self::contar_recursivo(filho);
}
contagem
}
}
fn main() {
let mut trie = Trie::nova();
// Insere palavras
let palavras = vec![
"rust", "ruby", "run", "runner", "running",
"python", "php", "perl",
"go", "golang",
];
for palavra in &palavras {
trie.inserir(palavra);
println!("Inserido: \"{}\"", palavra);
}
println!();
// Busca palavras
println!("Busca por \"rust\": {}", trie.buscar("rust"));
println!("Busca por \"ru\": {}", trie.buscar("ru"));
println!("Busca por \"java\": {}", trie.buscar("java"));
println!();
// Busca por prefixo
println!("Comeca com \"ru\": {}", trie.comeca_com("ru"));
println!("Comeca com \"py\": {}", trie.comeca_com("py"));
println!("Comeca com \"ja\": {}", trie.comeca_com("ja"));
println!();
// Autocompletar
println!("Autocompletar \"ru\": {:?}", trie.autocompletar("ru"));
println!("Autocompletar \"go\": {:?}", trie.autocompletar("go"));
println!("Autocompletar \"p\": {:?}", trie.autocompletar("p"));
println!();
// Remocao
println!("Total de palavras: {}", trie.contar_palavras());
trie.remover("runner");
println!("Apos remover \"runner\": {}", trie.contar_palavras());
println!("Busca \"runner\": {}", trie.buscar("runner"));
println!("Busca \"running\": {}", trie.buscar("running"));
}
Exemplo de Execucao
Inserido: "rust"
Inserido: "ruby"
Inserido: "run"
Inserido: "runner"
Inserido: "running"
Inserido: "python"
Inserido: "php"
Inserido: "perl"
Inserido: "go"
Inserido: "golang"
Busca por "rust": true
Busca por "ru": false
Busca por "java": false
Comeca com "ru": true
Comeca com "py": true
Comeca com "ja": false
Autocompletar "ru": ["ruby", "run", "runner", "running", "rust"]
Autocompletar "go": ["go", "golang"]
Autocompletar "p": ["perl", "php", "python"]
Total de palavras: 10
Apos remover "runner": 9
Busca "runner": false
Busca "running": true
Visualizacao da Trie apos todas as insercoes:
(raiz)
/ | \
r p g
/ \ | |
u . | o*
/|\ | \
s n b /|\ l
| |* | e h y |
t* | y* | \ \ a
n r p t |
| |* * h n
e l o |
| n* g*
r*
* = fim de palavra
Variacoes e Otimizacoes
1. Trie com Contagem de Frequencia
Util para contar ocorrencias de palavras em textos:
#[derive(Debug, Default)]
struct NoTrieContagem {
filhos: HashMap<char, Box<NoTrieContagem>>,
contagem: usize, // quantas vezes esta palavra foi inserida
}
struct TrieContagem {
raiz: NoTrieContagem,
}
impl TrieContagem {
fn nova() -> Self {
TrieContagem {
raiz: NoTrieContagem::default(),
}
}
fn inserir(&mut self, palavra: &str) {
let mut no = &mut self.raiz;
for ch in palavra.chars() {
no = no
.filhos
.entry(ch)
.or_insert_with(|| Box::new(NoTrieContagem::default()));
}
no.contagem += 1;
}
fn frequencia(&self, palavra: &str) -> usize {
let mut no = &self.raiz;
for ch in palavra.chars() {
match no.filhos.get(&ch) {
Some(filho) => no = filho,
None => return 0,
}
}
no.contagem
}
/// Retorna as k palavras mais frequentes com o prefixo dado.
fn top_k(&self, prefixo: &str, k: usize) -> Vec<(String, usize)> {
let mut no = &self.raiz;
for ch in prefixo.chars() {
match no.filhos.get(&ch) {
Some(filho) => no = filho,
None => return Vec::new(),
}
}
let mut todas: Vec<(String, usize)> = Vec::new();
let mut palavra = prefixo.to_string();
Self::coletar_com_freq(no, &mut palavra, &mut todas);
// Ordena por frequencia decrescente
todas.sort_by(|a, b| b.1.cmp(&a.1));
todas.truncate(k);
todas
}
fn coletar_com_freq(
no: &NoTrieContagem,
palavra: &mut String,
resultado: &mut Vec<(String, usize)>,
) {
if no.contagem > 0 {
resultado.push((palavra.clone(), no.contagem));
}
let mut chaves: Vec<&char> = no.filhos.keys().collect();
chaves.sort();
for &ch in &chaves {
if let Some(filho) = no.filhos.get(ch) {
palavra.push(*ch);
Self::coletar_com_freq(filho, palavra, resultado);
palavra.pop();
}
}
}
}
2. Trie com Array de Filhos (Mais Rapida)
Quando o alfabeto e limitado (ex.: apenas letras minusculas), usar um array em vez de HashMap e significativamente mais rapido:
const TAMANHO_ALFABETO: usize = 26;
#[derive(Debug)]
struct NoTrieArray {
filhos: [Option<Box<NoTrieArray>>; TAMANHO_ALFABETO],
fim_palavra: bool,
}
impl NoTrieArray {
fn novo() -> Self {
// Cria array com 26 posicoes None usando Default
NoTrieArray {
filhos: Default::default(),
fim_palavra: false,
}
}
}
struct TrieArray {
raiz: NoTrieArray,
}
impl TrieArray {
fn nova() -> Self {
TrieArray {
raiz: NoTrieArray::novo(),
}
}
fn inserir(&mut self, palavra: &str) {
let mut no = &mut self.raiz;
for ch in palavra.chars() {
let idx = (ch as u8 - b'a') as usize;
if idx >= TAMANHO_ALFABETO {
continue; // ignora caracteres fora do alfabeto
}
no = no.filhos[idx].get_or_insert_with(|| Box::new(NoTrieArray::novo()));
}
no.fim_palavra = true;
}
fn buscar(&self, palavra: &str) -> bool {
let mut no = &self.raiz;
for ch in palavra.chars() {
let idx = (ch as u8 - b'a') as usize;
if idx >= TAMANHO_ALFABETO {
return false;
}
match &no.filhos[idx] {
Some(filho) => no = filho,
None => return false,
}
}
no.fim_palavra
}
}
3. Trie Compactada (Radix Tree)
A Trie compactada funde nos com filho unico, economizando espaco:
Trie normal: Trie compactada:
r r
| / \
u u .
/|\ /|\
s n b st* n by*
| | | |
t* |* y* n*
n |
| er*
e |
| (ing*)
r*
Na Trie compactada, "st", "by" e "er" sao armazenados
como uma unica string no no, em vez de um caractere por no.
Aplicacoes Praticas
Sistema de Autocompletar
/// Simula um sistema de autocompletar para mecanismo de busca.
fn autocompletar_busca() {
let mut trie = Trie::nova();
// Popula com buscas populares
let buscas = vec![
"rust programming",
"rust lang",
"rust tutorial",
"rust vs go",
"rust cargo",
"ruby on rails",
"ruby gems",
"react native",
"react hooks",
];
for busca in &buscas {
trie.inserir(busca);
}
// Simula digitacao do usuario
let digitado = "rus";
let sugestoes = trie.autocompletar(digitado);
println!("Voce digitou: \"{}\"", digitado);
println!("Sugestoes:");
for (i, sugestao) in sugestoes.iter().enumerate() {
println!(" {}. {}", i + 1, sugestao);
}
}
Filtro de Palavras Proibidas
/// Verifica se um texto contem alguma palavra proibida.
fn filtrar_conteudo(texto: &str, palavras_proibidas: &[&str]) -> Vec<String> {
let mut trie = Trie::nova();
for &palavra in palavras_proibidas {
trie.inserir(palavra);
}
let mut encontradas = Vec::new();
let palavras_texto: Vec<&str> = texto.split_whitespace().collect();
for palavra in palavras_texto {
// Remove pontuacao simples para comparacao
let limpa: String = palavra.chars().filter(|c| c.is_alphanumeric()).collect();
let limpa_lower = limpa.to_lowercase();
if trie.buscar(&limpa_lower) {
encontradas.push(limpa_lower);
}
}
encontradas
}
Comparacao com Outros Algoritmos
| Estrutura | Busca | Insercao | Prefixo | Espaco |
|---|---|---|---|---|
| Lista/Array | O(n*m) | O(1) | O(n*m) | O(N) |
| HashSet | O(m)* | O(m)* | O(n*m) | O(N) |
| Trie | O(m) | O(m) | O(m) | O(N*A) |
| Arvore Binaria | O(m*logn) | O(m*logn) | O(m*logn) | O(N) |
| Suffix Array | O(m*logn) | O(n*logn) | O(m*logn) | O(n) |
* Caso medio com boa funcao hash. n = numero de strings, m = comprimento da busca, N = total de caracteres, A = tamanho do alfabeto.
A Trie e imbativel para operacoes com prefixos. Se voce precisa apenas de busca exata sem operacoes de prefixo, um HashSet pode ser mais eficiente em termos de espaco. Para dicionarios grandes com alfabeto limitado, a Trie compactada (Radix Tree) oferece um bom equilibrio.
Desafios de Ownership em Rust
Implementar arvores em Rust exige cuidado com o sistema de ownership. Alguns pontos importantes:
- Box<T>: Usamos
Box<NoTrie>para alocar nos no heap, evitando tamanho infinito da struct. - HashMap para filhos: Em vez de ponteiros brutos, usamos
HashMap<char, Box<NoTrie>>que gerencia a memoria automaticamente. - Mutabilidade: A travessia mutavel (
&mut self) so e possivel por um caminho de cada vez, o que naturalmente evita problemas de concorrencia. - Recursao: A remocao recursiva funciona bem com Rust porque cada chamada recursiva toma emprestimo mutavel do filho, liberando-o ao retornar.
Exercicios Praticos
Dicionario com definicoes: Modifique a Trie para armazenar nao apenas palavras, mas tambem suas definicoes (use
Option<String>no no). Implementebuscar_definicao(palavra: &str) -> Option<&str>.Contagem de prefixos: Adicione um campo
contagem_prefixoa cada no que armazena quantas palavras passam por aquele no. Isso permite responder “quantas palavras comecam com X?” em O(m).Maior prefixo comum: Dado um conjunto de palavras, encontre o maior prefixo comum entre todas elas usando a Trie. Dica: siga o caminho enquanto houver exatamente um filho.
Verificador ortografico: Implemente uma funcao que, dada uma palavra nao encontrada na Trie, sugira correcoes (palavras na Trie com distancia de edicao 1). Combine com Distancia de Levenshtein.
Veja Tambem
- HashMap na Biblioteca Padrao – mapa hash usado para filhos dos nos
- String em Rust – tipo String e manipulacao
- Box<T>: Ponteiro Inteligente – alocacao no heap para nos da arvore
- Option<T> – representacao de valores opcionais
- Algoritmo Aho-Corasick – Trie com links de falha para busca multi-padrao
- Distancia de Levenshtein – para correcao ortografica combinada com Trie