Tries

Uma trie armazena chaves por prefixos. Cada aresta representa um símbolo, e cada nó representa o prefixo no caminho da raiz até esse nó. Um marcador terminal distingue uma chave completa de um prefixo que não está armazenado como chave.

Modelo de complexidade

Para uma chave de comprimento m, a inserção, a busca exata e a busca por prefixo exigem O(m) etapas de símbolos, supondo acesso aos filhos em tempo esperado constante. Isso não é O(1): o comprimento da chave faz parte da entrada. O uso de memória pode ser alto porque os nós e os mapeamentos de filhos representam prefixos compartilhados e capacidade de ramificação não utilizada.

final class Trie {
    private final Node root = new Node();

    void add(String word) {
        Node node = root;
        for (int offset = 0; offset < word.length(); ) {
            int symbol = word.codePointAt(offset);
            node = node.children.computeIfAbsent(symbol, ignored -> new Node());
            offset += Character.charCount(symbol);
        }
        node.terminal = true;
    }

    boolean contains(String word) {
        Node node = findPrefix(word);
        return node != null && node.terminal;
    }

    private Node findPrefix(String prefix) {
        Node node = root;
        for (int offset = 0; offset < prefix.length(); ) {
            int symbol = prefix.codePointAt(offset);
            node = node.children.get(symbol);
            if (node == null) return null;
            offset += Character.charCount(symbol);
        }
        return node;
    }

    private static final class Node {
        private final Map<Integer, Node> children = new HashMap<>();
        private boolean terminal;
    }
}

Este exemplo itera sobre pontos de código Unicode, não sobre unidades de código UTF-16, mas não normaliza strings canonicamente equivalentes. Normalização de texto e regras de localidade são decisões de projeto separadas.

Tries compactadas unem caminhos com um único filho. Tries de busca ternária e autômatos finitos oferecem outros compromissos de espaço e tempo. Tries são úteis para consultas por prefixo, sugestões de preenchimento automático, roteamento e cargas semelhantes a dicionários.

Exercícios

1. Adicione consulta de existência de prefixo e remoção, preservando os prefixos compartilhados.
2. Compare o armazenamento de filhos baseado em array e em mapa.
3. Explique como a normalização Unicode afeta a identidade das chaves.