Classe TrieNode: inserção e busca
Construa uma TrieNode com um dicionário de filhos e um indicador is_end, implemente inserção e busca exata e analise o tempo O(m) por operação, em que m é o comprimento da palavra.
Classe TrieNode: inserção e busca é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 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.
O que é uma Trie?
Uma Trie (árvore de prefixos) é uma estrutura de dados em forma de árvore na qual cada nó representa um caractere. As palavras são armazenadas encadeando caracteres da raiz até a folha. A raiz representa uma string vazia. Cada caminho da raiz até um nó is_end = True forma uma palavra armazenada. As estruturas Trie são ideais para consultas baseadas em prefixos, como autocomplete, verificação ortográfica e roteamento de IP, superando mapas de dispersão nesses casos de uso.
Projeto da classe TrieNode
Um TrieNode tem dois campos: children — um dicionário que associa caracteres a TrieNodes filhos — e is_end — um booleano que indica se este nó é o fim de uma palavra armazenada. Usar um dicionário (em vez de um vetor fixo de 26 caracteres) generaliza a estrutura para qualquer conjunto de caracteres e economiza memória em Tries esparsas. Cada nó da Trie representa exatamente uma posição de caractere nas palavras abaixo dele.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)Operação de inserção
Para inserir uma palavra, percorra a partir da raiz, criando um novo TrieNode para cada caractere que ainda não exista nos children do nó atual. Depois de processar todos os caracteres, defina is_end = True no nó final. Inserir 'apple' e 'app' cria a cadeia a→p→p→l→e (is_end=True para 'apple'), com o p na posição 3 também marcado como is_end=True para 'app'.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = 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 = True
t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)Operação de busca
Para buscar uma palavra exata, percorra a Trie seguindo cada caractere. Se algum caractere estiver ausente nos children do nó atual, retorne False. Se todos os caracteres forem encontrados, retorne node.is_end — Verdadeiro somente se uma palavra terminar exatamente aqui, e não apenas um prefixo. Essa distinção entre 'prefixo existente' e 'palavra exata existente' é fundamental e costuma ser avaliada.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_end # must be a complete word
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False (app not inserted)
print(t.search('orange')) # FalseComeça com (busca por prefixo)
O método starts_with verifica se alguma palavra inserida tem o prefixo fornecido. Ele segue a mesma travessia de search, mas, em vez de verificar is_end, retorna Verdadeiro assim que todos os caracteres do prefixo são seguidos com sucesso — o que significa que o caminho do prefixo existe na Trie.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children: return False
node = node.children[c]
return node.is_end
def starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return False
node = node.children[c]
return True # prefix path exists
t = Trie()
t.insert('apple')
print(t.starts_with('app')) # True
print(t.starts_with('ape')) # False
print(t.search('app')) # False (not inserted)Complexidade de tempo e espaço
Cada operação da Trie (insert, search, starts_with) leva tempo O(m), em que m é o comprimento da palavra — percorremos no máximo m nós. Espaço: O(ALPHABET_SIZE × N × M), em que N é o número de palavras e M é o comprimento médio das palavras. Na prática, os prefixos compartilhados reduzem significativamente o espaço. Um dicionário de children baseado em mapa de dispersão usa menos espaço que um vetor fixo de 26 caracteres para Tries esparsas, ao custo de uma sobrecarga constante um pouco maior por consulta.
Usando um vetor em vez de um dicionário
Para usar somente letras minúsculas do inglês, utilize um vetor de tamanho fixo children = [None] * 26 com o índice ord(c) - ord('a'). Isso é mais rápido (consulta ao filho em O(1), em vez de um mapa de dispersão) e oferece um layout de memória previsível. Use a versão com dicionário quando o conjunto de caracteres for grande ou desconhecido (por exemplo, Unicode), e a versão com vetor em problemas de programação competitiva que usem somente letras minúsculas.
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26
self.is_end = False
class TrieArray:
def __init__(self):
self.root = TrieNodeArray()
def insert(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = TrieNodeArray()
node = node.children[idx]
node.is_end = True
def search(self, word):
node = self.root
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None: return False
node = node.children[idx]
return node.is_end
t = TrieArray()
t.insert('cat')
print(t.search('cat')) # True
print(t.search('car')) # FalseOperação de exclusão
A exclusão de uma Trie precisa lidar com três casos: (1) palavra ausente — não fazer nada; (2) palavra presente, mas prefixo de outra palavra — apenas desmarcar is_end; (3) palavra presente e que não é prefixo — excluir os nós de baixo para cima, parando quando um nó tiver outros filhos ou for o fim de outra palavra. A exclusão raramente é avaliada em entrevistas, mas é um conceito importante de conhecer.
Contagem de palavras com prefixo
Adicione a cada nó um campo count, incrementado a cada passagem durante uma inserção. Para contar palavras com determinado prefixo, percorra até o nó final do prefixo e retorne sua contagem. Isso permite consultas de autocomplete em O(m) sem percorrer todos os filhos — uma extensão útil para sistemas reais de autocomplete.
class TrieNodeCount:
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0 # words passing through this node
class TrieCount:
def __init__(self):
self.root = TrieNodeCount()
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNodeCount()
node = node.children[c]
node.count += 1 # increment on each level
node.is_end = True
def count_with_prefix(self, prefix):
node = self.root
for c in prefix:
if c not in node.children: return 0
node = node.children[c]
return node.count
t = TrieCount()
for w in ['apple','app','application','apply']:
t.insert(w)
print(t.count_with_prefix('app')) # 4
print(t.count_with_prefix('appl')) # 3Comparação entre Trie e mapa de dispersão
Um mapa de dispersão pode fazer uma busca exata em tempo médio O(m), mas não consegue responder com eficiência a consultas por prefixo (é necessário examinar todas as chaves). Uma Trie responde a consultas por prefixo em O(p), em que p é o comprimento do prefixo, agrupa naturalmente as palavras por prefixos compartilhados e não precisa de uma função de dispersão. Use uma Trie quando houver: consultas frequentes por prefixo, autocomplete ou verificação ortográfica. Use um mapa de dispersão quando forem necessárias apenas buscas exatas.
Tries em sistemas do mundo real
Entre os usos de Tries no mundo real estão: autocomplete (sugestões de pesquisa do Google), verificadores ortográficos (localização das palavras correspondentes mais próximas), roteamento de IP (correspondência do prefixo mais longo em roteadores), texto preditivo T9 (desambiguação de caracteres) e resolvedores de DNS (consulta hierárquica de nomes de domínio). Em cada caso, o compromisso entre O(m) por operação e O(ALPHABET × nós) de espaço faz da Trie a ferramenta adequada para consultas rápidas e que levam prefixos em conta em grande escala.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: um TrieNode tem um dicionário children e um booleano is_end, insert percorre os caracteres um a um, criando nós conforme necessário e definindo is_end no final e search verifica is_end, enquanto starts_with verifica apenas se o caminho do prefixo existe. A seguir, adicionaremos o autocomplete baseado em prefixos e estudaremos com mais profundidade o método starts_with.
Perguntas Frequentes
A aula “Classe TrieNode: inserção e busca” é grátis?
Sim — o texto completo de “Classe TrieNode: inserção e busca” é 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 “Classe TrieNode: inserção e busca”?
Construa uma TrieNode com um dicionário de filhos e um indicador is_end, implemente inserção e busca exata e analise o tempo O(m) por operação, em que m é o comprimento da palavra. 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 1 de 4.
Quanto tempo leva a aula “Classe TrieNode: inserção e busca”?
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
- Classe TrieNode: inserção e busca
- Busca por prefixo e começa com
- Busca com curingas e expressões regulares em uma trie
- Busca de palavras II: trie + retrocesso em uma grade