字典树 Trie：前缀检索的数据结构

如果只看定义，“字典树 Trie：前缀检索的数据结构”并不一定显得难。我当时真正卡住的是：我以前做前缀查询会遍历所有字符串，Trie 让我第一次直观看到：把公共前缀只存一次，本身就是一种索引。这次整理没有刻意追求一次讲完所有技巧，而是把我最容易断掉的几个理解环节重新接上。

Trie 把字符串拆成字符路径。共同前缀只保存一次，因此查询时间主要取决于字符串长度，而不是词条总数。

Trie 中 cat、car、care 和 dog 的前缀共享图

图：Trie 让共同前缀共享路径，并用结束标记区分完整单词

如果没有结束标记，就无法区分 car 只是 care 的前缀，还是本身也在集合中。

它从哪里来

Trie 的早期形式可追溯到 René de la Briandais 在 1959 年提出的字符串检索结构，Edward Fredkin 随后使用了 trie 这个名称。它把公共前缀只保存一次，特别适合词典、自动补全和路由匹配。

最小实现

public final class Trie {
    private static final class Node {
        java.util.Map<Character, Node> children = new java.util.HashMap<>();
        boolean word;
    }

    private final Node root = new Node();

    public void insert(String text) {
        Node node = root;
        for (char ch : text.toCharArray()) {
            node = node.children.computeIfAbsent(ch, ignored -> new Node());
        }
        node.word = true;
    }

    public boolean contains(String text) {
        Node node = walk(text);
        return node != null && node.word;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private Node walk(String text) {
        Node node = root;
        for (char ch : text.toCharArray()) {
            node = node.children.get(ch);
            if (node == null) return null;
        }
        return node;
    }
}

设字符串长度为 m，在子节点查找近似常数时，插入和查询约为 O(m)。这个结论不应写成绝对 O(1)，因为输入字符串越长，路径就越长。

空间与孩子表示

若字符集固定且很小，可让每个节点持有数组，访问快但空槽多。字符集大或分支稀疏时，用 Map 更省空槽，却增加对象和哈希开销。真实系统还可能采用压缩 Trie、基数树或双数组 Trie，合并单分支路径并减少对象数量。

中文文本还涉及 Unicode。Java 的 char 是 UTF-16 代码单元，不等于所有情况下的完整字符。若要正确支持补充平面字符，应按 code point 遍历；搜索系统还要先统一大小写、全半角、变音符号和分词规则。

按 code point 遍历时，可以让 children 的键类型变为 Integer：

text.codePoints().forEach(codePoint -> {
    // 使用完整 Unicode code point 进行节点转移
});

但“字符正确”仍不等于“搜索语义正确”。英文大小写是否等价、中文是否需要简繁转换、用户输入是否包含组合字符，都应该在插入和查询前经过同一条规范化流水线。

自动补全

先沿前缀走到目标节点，再从该节点 DFS 收集完整单词：

private void collect(Node node, StringBuilder path,
                     java.util.List<String> result, int limit) {
    if (result.size() >= limit) return;
    if (node.word) result.add(path.toString());
    for (var entry : node.children.entrySet()) {
        path.append(entry.getKey());
        collect(entry.getValue(), path, result, limit);
        path.deleteCharAt(path.length() - 1);
    }
}

若要求“最热门建议优先”，每个节点可维护 Top K 热词或子树最高权重。否则每次遍历巨大子树会使响应时间失控。实时热度更新还要考虑重建与并发成本。

删除为什么更谨慎

删除单词不能直接砍掉整条路径，因为节点可能被其他词共享。应先取消结束标记，再从叶子向上删除“既不是单词结尾、又没有孩子”的节点。

private boolean delete(Node node, String word, int index) {
    if (index == word.length()) {
        if (!node.word) return false;
        node.word = false;
        return node.children.isEmpty();
    }
    char ch = word.charAt(index);
    Node child = node.children.get(ch);
    if (child == null) return false;
    if (delete(child, word, index + 1)) node.children.remove(ch);
    return !node.word && node.children.isEmpty();
}

这个布尔值表示“当前节点是否已经可以被父节点清理”，而不是单纯表示删除是否成功。生产实现最好拆成更明确的返回类型，避免语义混淆。

压缩 Trie 与工程优化

普通 Trie 在分支稀疏时会创建大量只有一个孩子的节点。Radix Tree 把连续单分支路径压成一段字符串，减少节点数和指针跳转。双数组 Trie 使用两个整数数组编码转移，适合静态大词典，但增量更新更复杂。

优化方向包括：

小字符集使用定长数组，大字符集使用紧凑 Map。
对孩子集合按数量在数组、排序数组和哈希表之间切换。
静态词典构建后冻结，便于压缩和并发无锁读取。
只保留必要的词频、文档 ID 或 Top K，不把完整业务对象复制到每个节点。

适用边界

Trie 适合自动补全、词典、路由前缀和敏感词扫描。若只做精确键查询，HashMap 通常更简单；若词条极多且内存敏感，需要压缩结构或外部搜索引擎。数据结构选择应从查询模式出发，而不是因为 Trie 看起来更专业。

测试清单

空字符串是否允许作为单词。
一个词同时是另一个词的前缀，如 car 与 care。
删除共享前缀后其他单词仍可查询。
重复插入是计数还是保持幂等。
大小写、全半角和 Unicode 补充字符。
自动补全的数量限制、稳定排序和热门权重。