O que é uma Trie?

Uma trie (pronunciada "try", abreviação de retrieval) é uma estrutura de dados em forma de árvore construída para armazenar e pesquisar strings por seus caracteres. Cada aresta na árvore é rotulada com um único caractere, e cada caminho da raiz até um nó marcado soletra uma palavra armazenada.

Essa estrutura torna as consultas de prefixo extremamente rápidas. Verificar se a trie contém qualquer palavra começando com "car" são apenas três buscas de caracteres a partir da raiz, não importa quantos milhares de palavras estejam armazenadas. Tries são o motor por trás de recursos como preenchimento automático, verificação ortográfica e tabelas de roteamento IP.

Cada nó na trie contém dois estados:

• children: um mapa de um caractere para o próximo TrieNode.
• isEndOfWord: uma flag que é true quando o caminho da raiz até este nó soletra uma palavra completa que foi inserida.

As cinco principais operações em uma trie são:

1. Insert: Adiciona uma palavra, criando quaisquer nós ausentes ao longo do caminho.
2. Search: Verifica se uma palavra completa está armazenada.
3. StartsWith: Verifica se alguma palavra armazenada possui o prefixo fornecido.
4. Delete: Remove uma palavra e poda quaisquer ramos mortos.
5. WordCount: Conta quantas palavras distintas estão armazenadas.

Vamos construir uma classe Trie!