关于前缀树Trie

前缀树（Trie）介绍

前缀树（字典树）是为”前缀匹配”设计的数据结构：共享公共前缀、逐字符下挂、结尾打标记。

一、解决什么问题

搜索框输入 app，要立刻联想出 apple、apply。用 HashSet 得逐个 startsWith 扫一遍，词库越大越慢。前缀树让查询只跟”要查的词多长”有关，跟词库大小无关。

二、结构

插入 app、apple、apply，共享前缀 app：

(root) → a → p → p* → l → e*   (apple)
                    → l → y     (apply)

• 根节点不存字符，只是入口。
• 节点上的 * 表示该节点是一个完整单词的结尾。

节点设计（字符集固定为 a-z 时用数组最省事）：

private static class TrieNode {
    boolean isEnd;          // 是否单词结尾
    TrieNode[] children = new TrieNode[26]; // a-z 槽位
}

三、简要代码实现

class Node {
    /** 子节点 */
    Node[] child;
    /** 是否数据结尾 */
    boolean end;

    Node() {
        // 仅考虑小写字母
        this.child = new Node[26];
        this.end = false;
    }
}

class Trie {

    /** 根节点 */
    private Node root;

    public Trie() {
        this.root = new Node();
    }

    public void insert(String word) {
        if (null == word || word.length() == 0) {
            return;
        }
        Node cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.child[i] == null) {
                cur.child[i] = new Node();
            }
            cur = cur.child[i];
        }
        cur.end = true;
    }

    /** 查询函数，返回：0-没找到，1-没找完，2-都存在 */
    private int find(String word) {
        if (null == word || word.length() == 0) {
            return 0;
        }
        Node cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.child[i] == null) {
                return 0;
            }
            cur = cur.child[i];
        }
        return cur.end ? 2 : 1;
    }

    public boolean search(String word) {
        return 2 == find(word);
    }

    public boolean startsWith(String prefix) {
        int state = find(prefix);
        return 1 == state || 2 == state;
    }
}

关键点： search 与 startsWith 共用 searchPrefix，区别只在 search 多判一个 isEnd。c - 'a' 把字母映射到 0~25。

四、复杂度

设单词平均长度 L：

• insert / search / startsWith 均为 O(L)，与词库大小无关。
• 空间：最坏 O(26 · N · L)，前缀共享越多越省。

五、子节点选型

• 数组 TrieNode[26]：字符集固定且小（如本题 a-z），访问 O(1)，最干脆。
• 哈希表 Map<Character, TrieNode>：字符集大或不定（中文、符号），代价是内存和常数时间略高。

六、应用

常见应用：搜索/输入法自动补全、敏感词过滤、IP 路由最长前缀匹配。

---

核心一句话：共享前缀、逐字符下挂、结尾打标记。