Trie

O que é uma trie

Uma trie é uma tree que guarda chaves soletrando cada uma. Cada aresta representa um caractere, então uma chave não fica guardada em nenhum node específico: ela é o caminho da root até o ponto onde termina. Chaves que começam igual dividem o começo do caminho, e é por isso que a estrutura também é chamada de prefix tree (árvore de prefixos). Os dois nomes são a mesma coisa.

O nome vem de retrieval. Quase todo mundo pronuncia "trai", para diferenciar de "tree", mesmo ela sendo uma.

Cada node guarda uma letra, a da aresta que chega nele, e o rótulo embaixo de um node é a palavra cujo caminho termina ali. Descendo da root por c, a e r, você soletra car; mais um passo e é cart. Nada na trie compara uma chave com outra: a posição de uma chave sai só das letras dela.

O problema que as estruturas anteriores não resolviam

A hash table responde "cart está aqui?" com O(1) probes esperados. Pergunte quais chaves começam com ca e ela não tem o que oferecer: o hash de cart não diz nada sobre o hash de car, então as chaves com o mesmo prefixo ficam espalhadas pelos buckets de propósito. O único jeito de responder é ler todas as chaves.

Uma Binary Search Tree mantém as chaves ordenadas, então tudo que começa com ca fica num intervalo contínuo, e uma range query encontra. Só que cada passo descendo a tree compara duas chaves inteiras. Com n chaves de tamanho k, um lookup faz O(log n) comparações e cada uma pode ler até k caracteres, mesmo que os primeiros já tenham sido resolvidos pelas comparações de cima.

A trie lê cada caractere da chave uma vez só, e a quantidade de chaves guardadas nem entra no custo.

Search, startsWith e insert

As três operações são a mesma caminhada. Comece na root e, para cada caractere da chave, siga o child daquele caractere.

Search

Para procurar cart, siga c, a, r e t. Quatro letras, quatro passos, seja a trie com cinco palavras ou com cinco milhões.

A caminhada falha assim que uma letra não tem child. Buscar cow para em c, que não tem child o, depois de um passo só.

O marcador de fim de palavra

Buscar ca segue c e a sem problema, e mesmo assim ca não é uma palavra guardada. Chegar num node só prova que alguma palavra guardada começa com aquele prefixo. Por isso cada node carrega mais um bit, um marcador de fim (end marker), ligado quando uma chave termina exatamente ali.

É o marcador que deixa car e cart dividirem o caminho. car termina no node r e cart continua um nível abaixo, e as duas estão guardadas porque os dois nodes têm o marcador. Sem ele, a trie só conseguiria guardar chaves em que nenhuma fosse prefixo de outra.

startsWith

O startsWith é a mesma caminhada ignorando o marcador: se ela chega ao fim do prefixo, pelo menos uma chave guardada começa com ele. Juntar essas chaves é visitar a subtree embaixo daquele node, e todo node nela é um resultado.

Chegar ao prefixo custa O(k). Listar o que tem embaixo custa uma visita por node da subtree, que é o tamanho da própria resposta. Os children são visitados em ordem alfabética, então as palavras saem ordenadas.

Insert

O insert faz a mesma caminhada e, onde uma letra não tem child, cria um. No fim, liga o marcador no último node.

Inserir care reaproveita c, a e r e cria só o e. Inserir uma palavra que já é prefixo, como ca, não cria nada: os nodes já existem e só o marcador muda.

Deleção

Apagar uma chave desliga o marcador de fim dela. Só isso já faz o search parar de encontrá-la, mas pode sobrar node que nenhuma chave usa mais. Esses nodes são podados (pruning): na volta para cima, todo node sem marcador e sem children é liberado, e a poda para no primeiro node de que outra chave ainda precisa.

Apagar cart libera o t embaixo de car e para ali, porque car tem marcador de fim. Apagar car depois disso libera o node r, que a essa altura não tem children nem marcador, e para em ca, que ainda leva a cat.

Agora apague car com cart ainda guardada, e nada é podado. O node r continua no lugar, com o marcador desligado, porque cart passa por ele.

Representando uma trie na memória

O node mais simples dá um slot para cada letra: um array de 26 pointers para children, para letras minúsculas em inglês, mais o marcador de fim. Achar um child é um índice só, children[c - 'a'], sem busca nenhuma.

Search, StartsWith e Insert são um loop sobre os bytes da chave. O Delete é recursivo para poder podar na volta, e diz se a chave estava guardada. Essa versão só aceita de 'a' a 'z'; qualquer outro byte indexa fora do array e dá panic.

Quanto custa um node

O array faz do lookup de um child um índice só, e paga isso em espaço: todo node carrega 26 pointers, usando ou não. Passando dos primeiros níveis, a maioria dos nodes tem um child só, então a maior parte da trie é pointer nil. Indexar por byte, para aceitar qualquer chave, deixa cada node dez vezes maior.

Um map por node guarda só os children que existem, o que compensa quando o alfabeto é grande e os nodes são esparsos, como com bytes ou Unicode. Em troca, perde o lookup de um índice só: cada passo calcula o hash do caractere e faz probe. Algumas implementações ficam no meio do caminho, com um slice curto e ordenado de pares (char, child) por node, percorrido linearmente porque raramente tem mais que umas poucas entradas.

Teste você mesmo

O playground roda o código acima sobre a trie da primeira figura. Busque ca para ver um caminho que existe sem ser palavra, e depois use Começa com nele. Insira care e aparece um node só; apague cart e um node é podado, enquanto apagar car com cart ainda guardada não poda nada.

Compressed tries e radix trees

Chaves longas formam correntes longas: um caminho em que cada node tem um child só e nenhum marcador guarda uma letra por alocação e não decide nada. Uma compressed trie, normalmente chamada de radix tree (ou Patricia trie, na versão binária), junta cada corrente dessas num node só, rotulado com a string inteira.

As palavras e as respostas são as mesmas; só as correntes sumiram. Agora um node só existe onde as chaves se dividem ou terminam, então a quantidade de nodes fica limitada pelo número de chaves, não pelo número de letras. A caminhada muda num ponto: em cada node ela compara uma sequência de caracteres com o rótulo em vez de um caractere só, e um insert que diverge no meio de um rótulo divide aquele node em dois.

Operações comuns e seus custos

k é o tamanho da chave, n o número de chaves guardadas, m o número de resultados que uma consulta por prefixo devolve.

Num lookup de uma chave só, a trie e a hash table caem na mesma classe, porque a hash table precisa ler a chave inteira para calcular o hash. A diferença está na linha do prefixo: a trie é a única das três cujo custo depende da resposta, e não de tudo que está guardado.

Tries no mundo real

Autocomplete. Digitar ca numa caixa de busca é um startsWith: vai até o node ca e lista o que tem embaixo. Perto da root essa subtree pode ter boa parte do dicionário, então um refinamento comum guarda um peso em cada node com marcador (quantas vezes o termo foi buscado) e deixa as poucas sugestões mais pesadas em cache em cada node, o que transforma cada tecla numa caminhada mais uma leitura.

Corretor ortográfico. Conferir uma palavra contra um dicionário é um search. Sugerir correções é explorar caminhos que diferem da palavra digitada por uma ou duas letras, e a trie deixa a busca descartar um ramo inteiro assim que o prefixo dele já está longe demais do que foi digitado.

Roteamento IP. Um roteador encaminha um pacote pelo longest prefix match: entre todos os prefixos de rede da tabela (10.0.0.0/8, 10.1.0.0/16), escolhe o mais longo que bate com o endereço de destino. Isso é uma caminhada por uma trie sobre os bits do endereço, lembrando o último node que tinha uma rota. A tabela de rotas IPv4 do kernel Linux é uma LC-trie, uma trie binária que usa level compression para trocar sequências de nodes binários por nodes mais largos.

Routers HTTP em Go. O httprouter casa os paths das requests com "a compact prefix tree (or just Radix tree)", nas palavras dele; o gin usa uma versão própria do httprouter, e chi e echo também descrevem seus routers como radix trees. O ServeMux da biblioteca padrão, desde o Go 1.22, casa padrões com uma decision tree que se divide pelo host, depois pelo método, depois por cada segmento do path, o que faz dele uma trie cujos "caracteres" são segmentos de path.

Quando tries ficam aquém

Memória por node. Cada letra de cada chave que não divide prefixo vira uma alocação própria, quase toda feita de pointers vazios. Um hash set guarda os bytes de cada chave uma vez só, então, se a pergunta é só "essa chave está aqui?", ele ocupa bem menos memória.

Pointer chasing. Cada passo da caminhada carrega o pointer de um child e depois o node para onde ele aponta, que está na sua própria alocação em algum outro lugar da memória. Uma chave longa vira uma corrente de acessos dependentes, cada um provavelmente um cache miss numa trie grande, enquanto um lookup em hash calcula o hash da chave e toca uma ou duas cache lines.

As chaves precisam ser sequências. A trie precisa de chaves que se quebrem numa sequência de símbolos pequenos: caracteres, bytes, bits ou segmentos de path. Números de ponto flutuante ou registros compostos não têm uma estrutura caractere por caractere que valha a pena dividir.

Alfabeto fixo ou passo mais lento. O node com array supõe um alfabeto pequeno e conhecido. Aceitar qualquer byte ou Unicode significa ou um node de 256 posições, com dez vezes a memória, ou um map ou slice por node e um lookup que já não é um índice só.

Resumo

• Uma chave é um caminho: cada aresta é um caractere, e chaves com o mesmo prefixo dividem o começo do caminho, daí o nome "prefix tree"
• O custo depende do tamanho da chave, não de quantas chaves estão guardadas
• O marcador de fim separa uma chave guardada de um prefixo dela, e é o que deixa car e cart serem guardadas juntas
• A deleção desliga o marcador e poda os nodes que nenhuma outra chave usa, parando no primeiro que ainda é necessário
• Um node de 26 slots é um índice por passo e quase só pointers vazios; um map por node economiza memória em alfabetos grandes e esparsos
• Uma radix tree junta as correntes de child único num node só, então o número de nodes acompanha o número de chaves, e não o de letras
• Consultas por prefixo são o motivo para usar uma: autocomplete, longest prefix match em tabelas de rota, routers HTTP. Só para lookups exatos, um hash set é menor e costuma ser mais rápido