Classe TrieNode: inserção e busca

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.

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.

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'.

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.

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.

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.

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.

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.

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.

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.

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.

Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta 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.