Trie — The Data Structures Atlas

Categoria: Trees

O problema

Uma Hash Table responde "essa chave exata existe?" em O(1) médio, mas não consegue responder "existe alguma chave que comece com este prefixo?" sem varrer todas as chaves armazenadas — o hashing descarta de propósito qualquer relação estrutural entre chaves parecidas. Autocompletar, validação de prefixo e "faz sentido continuar digitando isso" precisam dessa relação preservada.

A solução

Armazene as chaves caractere por caractere ao longo de uma árvore: cada nó guarda seus filhos indexados pelo próximo caractere, e uma flag por nó marca "uma chave completa termina aqui". Buscar uma chave ou um prefixo significa percorrer um caractere de cada vez a partir da raiz — o custo é O(m), em que m é o comprimento da chave ou do prefixo, e, fundamentalmente, esse custo não tem nada a ver com quantas outras chaves estão armazenadas. Uma trie com 100 chaves e uma com 100.000 respondem a mesma consulta de prefixo no mesmo tempo, porque o percurso só toca nós ao longo de um único caminho.

flowchart TD
    R((root)) --> P((p))
    P --> PI((i))
    PI --> PIX(("x*"))
    PIX --> PIX1((1))
    PIX --> PIX2((2))

* marca um nó onde uma chave completa termina (por exemplo, "pix" em si é uma chave cadastrada, assim como "pix1" e "pix2").

Operação	Custo	Por quê
`insert(key)`	O(m)	um nó é criado ou reaproveitado por caractere de `key`
`contains(key)`	O(m)	percorre o caminho exato de `key`, verifica a flag de fim de palavra
`startsWith(prefix)`	O(m)	percorre o caminho exato de `prefix`, a mera existência já basta

m = comprimento da chave/prefixo. Nenhuma dessas operações depende de quantas outras chaves estão armazenadas — veja o benchmark abaixo.

Exemplo clássico

classic/Trie constrói os filhos de cada nó como um Map<Character, Node> em vez de um array fixo de 26/128 posições, já que as chaves PIX não estão restritas a um único alfabeto (letras, dígitos, @, ., +). TrieTest cobre um bug real encontrado durante a escrita: o nó raiz existe incondicionalmente como campo (não é criado por insert), então startsWith("") em uma trie completamente vazia retornaria true — uma proteção para trie vazia em startsWith corrige isso, e o teste trava o comportamento correto (false).

Exemplo aplicado: índice de prefixo de chaves PIX do BACEN

applied/PixKeyPrefixIndex valida e autocompleta chaves PIX (as chaves cadastradas no BACEN podem ser um CPF, e-mail, número de telefone ou uma chave aleatória no estilo UUID) enquanto o usuário digita em um formulário de pagamento, sem uma ida e volta ao serviço de diretório a cada tecla pressionada: hasKeyStartingWith sustenta a interface de autocompletar, isRegisteredKey é a verificação de correspondência exata quando a digitação termina. PixKeyPrefixIndexTest cobre os dois casos.

Benchmark

./gradlew :trees:trie:jmh

Execução real (JMH 1.37, JDK 26.0.2, 2 iterações de aquecimento + 3 de medição, 1 fork). O comprimento da chave é mantido constante (chaves de 12 caracteres, "PIX" + um número de 9 dígitos com zeros à esquerda) enquanto o número de chaves armazenadas varia — o formato deliberadamente diferente em relação ao benchmark de todos os outros módulos, já que a afirmação aqui é que esse eixo não deveria importar em nada:

Operação	100 chaves	10,000 chaves	100,000 chaves
`contains`	102.0 ns	98.7 ns	98.2 ns
`startsWith`	73.5 ns	89.2 ns	58.4 ns

Estável dentro da margem de ruído ao longo de um aumento de 1,000x na quantidade de chaves armazenadas — nenhuma das duas operações se importa com quantas outras chaves compartilham a trie. Compare com Hash Table, em que uma busca por correspondência exata também é estável em relação ao tamanho, mas não consegue responder a uma consulta de prefixo de jeito nenhum sem uma varredura O(n) de todas as chaves.

Quando não usar

As chaves não são naturalmente hierárquicas/sequenciais em caracteres, ou consultas de prefixo nunca são necessárias? Uma Hash Table oferece a mesma busca por correspondência exata em O(1)-ish com um overhead de memória por chave muito menor (uma trie aloca um nó por posição de caractere única, o que se acumula para um conjunto de chaves grande e com pouca sobreposição de prefixo).
Precisa de consultas de intervalo (todas as chaves entre X e Y), não de consultas de prefixo? Uma Binary Search Tree se encaixa melhor nesse tipo de pergunta.
Chaves muito longas com pouca estrutura de prefixo compartilhada fazem o overhead de nó por caractere custar mais do que economiza — uma trie compensa em dados com localidade de prefixo real (palavras, chaves PIX, caminhos de arquivo, URLs), não em strings longas arbitrárias.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :trees:trie:jacocoTestReport

Relatório em trees/trie/build/reports/jacoco/test/html/index.html.

Testes unitários

src/test/java/com/datastructures/trees/trie/classic/TrieTest.java

package com.datastructures.trees.trie.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class TrieTest {

    @Test
    void startsEmpty() {
        Trie trie = new Trie();

        assertThat(trie.isEmpty()).isTrue();
        assertThat(trie.size()).isZero();
    }

    @Test
    void insertThenContainsFindsTheExactKey() {
        Trie trie = new Trie();

        trie.insert("cat");

        assertThat(trie.contains("cat")).isTrue();
        assertThat(trie.size()).isEqualTo(1);
        assertThat(trie.isEmpty()).isFalse();
    }

    @Test
    void containsIsFalseWhenTheKeyWasNeverInserted() {
        Trie trie = new Trie();
        trie.insert("cat");

        assertThat(trie.contains("dog")).isFalse();
    }

    @Test
    void containsIsFalseForAStoredPrefixThatWasNeverInsertedAsItsOwnKey() {
        Trie trie = new Trie();
        trie.insert("caterpillar");

        // "cat" exists as a path through the trie (it's a prefix of "caterpillar"), but it was
        // never itself inserted as a complete key, so contains() must say no.
        assertThat(trie.contains("cat")).isFalse();
        assertThat(trie.startsWith("cat")).isTrue();
    }

    @Test
    void insertingTheSameKeyTwiceDoesNotDoubleCountSize() {
        Trie trie = new Trie();
        trie.insert("cat");

        trie.insert("cat");

        assertThat(trie.size()).isEqualTo(1);
        assertThat(trie.contains("cat")).isTrue();
    }

    @Test
    void insertingKeysThatShareAPrefixReusesTheSharedNodes() {
        Trie trie = new Trie();
        trie.insert("car");

        trie.insert("card"); // shares "car" with the first key, then extends with "d"

        assertThat(trie.contains("car")).isTrue();
        assertThat(trie.contains("card")).isTrue();
        assertThat(trie.size()).isEqualTo(2);
    }

    @Test
    void startsWithIsTrueForAnyStoredPrefixOfAKey() {
        Trie trie = new Trie();
        trie.insert("caterpillar");

        assertThat(trie.startsWith("c")).isTrue();
        assertThat(trie.startsWith("cate")).isTrue();
        assertThat(trie.startsWith("caterpillar")).isTrue();
    }

    @Test
    void startsWithIsFalseWhenNoStoredKeyMatchesThePrefixAtAll() {
        Trie trie = new Trie();
        trie.insert("cat");

        assertThat(trie.startsWith("dog")).isFalse();
    }

    @Test
    void startsWithIsFalseWhenThePrefixDivergesPartwayThroughAStoredKey() {
        Trie trie = new Trie();
        trie.insert("cat");

        // Shares "ca" with the stored key but diverges at the third character.
        assertThat(trie.startsWith("cow")).isFalse();
    }

    @Test
    void emptyStringIsAPrefixOfEverythingAndTheEmptyKeyIsHandledAsAWordItself() {
        Trie trie = new Trie();

        assertThat(trie.startsWith("")).isFalse(); // nothing stored yet at all

        trie.insert("");

        assertThat(trie.contains("")).isTrue();
        assertThat(trie.startsWith("")).isTrue();
        assertThat(trie.size()).isEqualTo(1);

        trie.insert("cat");

        assertThat(trie.startsWith("")).isTrue();
        assertThat(trie.size()).isEqualTo(2);
    }
}

src/test/java/com/datastructures/trees/trie/applied/PixKeyPrefixIndexTest.java

package com.datastructures.trees.trie.applied;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class PixKeyPrefixIndexTest {

    private final PixKeyPrefixIndex index = new PixKeyPrefixIndex();

    @BeforeEach
    void registerAFewPixKeysOfDifferentTypes() {
        index.register("12345678900"); // CPF-style key
        index.register("leon.gomes@example.com"); // email key
        index.register("+5511999998888"); // phone key
        index.register("a1b2c3d4-e5f6-7890-abcd-ef1234567890"); // random UUID-style key
    }

    @Test
    void anExactlyRegisteredKeyIsRecognizedAsRegistered() {
        assertThat(index.isRegisteredKey("leon.gomes@example.com")).isTrue();
    }

    @Test
    void aKeyThatWasNeverRegisteredIsNotRecognized() {
        assertThat(index.isRegisteredKey("someone-else@example.com")).isFalse();
    }

    @Test
    void autocompleteRecognizesAPartiallyTypedPrefixOfARegisteredKey() {
        assertThat(index.hasKeyStartingWith("leon.")).isTrue();
        assertThat(index.hasKeyStartingWith("+5511")).isTrue();
    }

    @Test
    void autocompleteRejectsAPrefixThatMatchesNoRegisteredKey() {
        assertThat(index.hasKeyStartingWith("99999")).isFalse();
    }

    @Test
    void anEmptyIndexHasNoStartingMatchesAndNoRegisteredKeys() {
        PixKeyPrefixIndex emptyIndex = new PixKeyPrefixIndex();

        assertThat(emptyIndex.hasKeyStartingWith("1")).isFalse();
        assertThat(emptyIndex.isRegisteredKey("12345678900")).isFalse();
    }
}

Ver relatório completo de cobertura JaCoCo →