Tries para Consultas por Prefixo
Armazene e consulte prefixos de palavras rapidamente.
Tries para Consultas por Prefixo é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Armazenando palavras com inteligência
Uma árvore de prefixos é uma árvore que armazena palavras compartilhando prefixos comuns. Ela torna as consultas de prefixo extremamente rápidas. 🌳
Por que não usar apenas um conjunto
Um conjunto responde a consultas de palavras completas, mas as árvores de prefixos também respondem a consultas de prefixo, como saber se alguma palavra começa com pre.
Nós e arestas
Cada nó representa uma posição em alguma palavra, e cada aresta é rotulada com um caractere do caminho a partir da raiz.
Filhos como um dicionário
Em Python, o nó mais simples é um dicionário que mapeia um caractere para seu nó filho. É simples e flexível.
root = {}Inserindo uma palavra
Para inserir, percorra os caracteres um a um e crie um filho sempre que ele estiver ausente.
node = root
for c in word:
node = node.setdefault(c, {})Marcando o fim das palavras
Depois de inserir, defina um indicador de fim para distinguir uma palavra completa de um simples prefixo.
node['#'] = TruePesquisando uma palavra completa
Para pesquisar, siga os caracteres; se algum passo estiver ausente, a palavra não existe. Depois, verifique o indicador de fim.
for c in word:
if c not in node:
return False
node = node[c]Verificando um prefixo
Uma consulta de prefixo percorre o mesmo caminho, mas dispensa a verificação do indicador de fim. Chegar ao último nó significa que a resposta é sim.
Complexidade temporal
Inserção e consulta custam O(L), o comprimento da palavra, independentemente de quantas palavras você armazenou. O que importa é o comprimento.
Contando palavras por prefixo
Armazene uma contagem em cada nó para responder instantaneamente quantas palavras armazenadas compartilham determinado prefixo.
Onde as árvores de prefixos ajudam
As árvores de prefixos permitem criar autocompletar, verificar dicionários e resolver problemas de máximo com XOR em bits. São essenciais em problemas de cadeias de competições.
Verificação rápida
Confirme qual é o custo real de uma consulta em uma árvore de prefixos.
Recapitulação: árvores de prefixos concluídas
Agora você consegue construir uma árvore de prefixos, inserir e pesquisar em O(L) e responder rapidamente a consultas de prefixo e contagem. 🌟
Perguntas Frequentes
A aula “Tries para Consultas por Prefixo” é grátis?
Sim — o texto completo de “Tries para Consultas por Prefixo” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Tries para Consultas por Prefixo”?
Armazene e consulte prefixos de palavras rapidamente. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Tries para Consultas por Prefixo”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Função de Prefixo do KMP
- Hashing Polinomial de Strings
- Função Z para Busca de Padrões
- Tries para Consultas por Prefixo