Um trie guarda uma única vez os prefixos de caracteres compartilhados. Cada aresta consome um caractere, então você responde a uma pergunta de prefixo indo direto ao nó desse prefixo. A informação extra de um nó decide a que pergunta a estrutura responde: um contador de passagem mede ocorrências, enquanto uma marca terminal registra uma palavra completa.
Esses estados são diferentes. Registrar plane cria um caminho para plan, mas não registra plan como palavra. Nesta lição você constrói as duas formas e depois as usa para raízes de roteamento mais curtas, rótulos em conflito e uma busca que permite exatamente uma substituição. Diga o que cada campo do nó significa antes de programar. Esse invariante facilita testar prefixos vazios, inserções duplicadas e finais de palavra.
Insira uma etiqueta por vez e incremente cada nó visitado, inclusive a raiz. A segunda inserção de map segue arestas existentes, mas mesmo assim incrementa seus contadores, porque este catálogo conta ocorrências. Depois das quatro etiquetas, o nó ma registra três chegadas e map registra duas. Uma consulta de ma para antes de a marca terminal importar: a pergunta diz respeito a todas as continuações desse prefixo. Uma consulta vazia não percorre nenhuma aresta e lê a contagem da raiz, quatro. Para a busca exata, use uma marca terminal separada em vez de interpretar qualquer caminho existente como uma palavra registrada.