Tries

A trie stores keys by prefixes. Each edge represents a symbol and each node represents the prefix along the root-to-node path. A terminal marker distinguishes a complete key from a prefix that is not itself stored.

Complexity model

For a key of length m, insertion, exact lookup, and prefix lookup take O(m) symbol steps, assuming child access is constant expected time. This is not O(1): the key length is part of the input. Memory can be high because nodes and child mappings represent shared prefixes and unused branching capacity.

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;
    }
}

This example iterates Unicode code points rather than UTF-16 code units, but it does not normalize canonically equivalent strings. Text normalization and locale rules are separate design decisions.

Compressed tries merge single-child paths. Ternary search tries and finite-state automata offer other space/time trade-offs. Tries are useful for prefix queries, autocomplete candidates, routing, and dictionary-like workloads.

Exercises

1. Add prefix existence and deletion while retaining shared prefixes.
2. Compare array-backed and map-backed child storage.
3. Explain how Unicode normalization affects key identity.