每日算法 — 使用java实现Trie前缀树：高效字符串检索与自动补全系统

可莉爸爸 AI算法

Trie（发音同”try”），又称前缀树或字典树，是一种高效的多叉树形数据结构，专门用于处理字符串的存储与检索。其核心思想是利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。从搜索引擎的关键词提示到IDE的代码补全，Trie 树无处不在。本文将用 Java 从零实现一套完整的 Trie 树，涵盖插入、精确搜索、前缀匹配三大核心操作，并基于它构建一个命令行自动补全系统。

一、Trie 树的核心思想

假设需要存储单词：cat、car、cars、dog、door。若使用普通列表存储，搜索是否存在 “cars” 需要逐个比对，时间复杂度为 O(N×L)（N 为单词数，L 为单词长度）。而 Trie 树将这些单词按字符层级展开：

  • 根节点为空，第一层分叉为 ‘c’ 和 ‘d’
  • ‘c’ 下再分 ‘a’，’a’ 下再分 ‘t’ 和 ‘r’
  • ‘r’ 下再继续分 ‘s’

如此，搜索 “cars” 只需沿着 c→a→r→s 走 4 步即可判定存在与否，时间复杂度降至 O(L)。前缀匹配同样高效：查找所有以 “ca” 开头的单词，只需先走到 ‘c’→’a’ 节点，再遍历其整个子树即可。

二、核心数据结构

2.1 Trie 节点

每个节点保存一个字符到子节点的映射，以及一个标记位 isEndOfWord，表示从根到该节点是否构成一个完整单词。

import java.util.HashMap;
import java.util.Map;

/**
 * Trie 树的节点类
 * 每个节点代表一个字符，通过 children 映射维护后续字符分支
 */
public class TrieNode {
    // 子节点映射：字符 -> 子节点
    private final Map<Character, TrieNode> children;
    // 标记从根到当前节点是否构成一个完整单词
    private boolean isEndOfWord;
    // 记录经过该节点的单词数量（用于前缀频率统计）
    private int passCount;

    public TrieNode() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
        this.passCount = 0;
    }

    public boolean containsChild(char ch) {
        return children.containsKey(ch);
    }

    public TrieNode getChild(char ch) {
        return children.get(ch);
    }

    public void putChild(char ch, TrieNode node) {
        children.put(ch, node);
    }

    public boolean isEndOfWord() {
        return isEndOfWord;
    }

    public void setEndOfWord(boolean endOfWord) {
        isEndOfWord = endOfWord;
    }

    public int getPassCount() {
        return passCount;
    }

    public void incrementPassCount() {
        passCount++;
    }

    public void decrementPassCount() {
        passCount--;
    }

    public Map<Character, TrieNode> getChildren() {
        return children;
    }
}

2.2 Trie 树主体

import java.util.ArrayList;
import java.util.List;

/**
 * Trie 前缀树实现
 * 支持：插入、搜索、前缀匹配、删除、自动补全
 */
public class Trie {
    private final TrieNode root;
    private int size; // 存储的单词总数

    public Trie() {
        this.root = new TrieNode();
        this.size = 0;
    }

    /**
     * 插入一个单词到 Trie 树
     * 时间复杂度：O(L)，L 为单词长度
     */
    public void insert(String word) {
        if (word == null || word.isEmpty()) {
            return;
        }
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            if (!current.containsChild(ch)) {
                current.putChild(ch, new TrieNode());
            }
            current = current.getChild(ch);
            current.incrementPassCount();
        }
        // 如果该单词已存在，不重复计数
        if (!current.isEndOfWord()) {
            current.setEndOfWord(true);
            size++;
        }
    }

    /**
     * 精确搜索：判断单词是否存在于 Trie 树中
     * 时间复杂度：O(L)
     */
    public boolean search(String word) {
        if (word == null || word.isEmpty()) {
            return false;
        }
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord();
    }

    /**
     * 前缀搜索：判断是否存在以指定前缀开头的单词
     * 时间复杂度：O(P)，P 为前缀长度
     */
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.isEmpty()) {
            return false;
        }
        return searchNode(prefix) != null;
    }

    /**
     * 获取指定前缀的出现频率（有多少单词以此前缀开头）
     */
    public int prefixCount(String prefix) {
        TrieNode node = searchNode(prefix);
        return node != null ? node.getPassCount() : 0;
    }

    /**
     * 自动补全：返回所有以指定前缀开头的完整单词
     * 时间复杂度：O(P + M)，P 为前缀长度，M 为子树节点总数
     */
    public List<String> autoComplete(String prefix) {
        List<String> results = new ArrayList<>();
        if (prefix == null) {
            return results;
        }
        TrieNode prefixNode = searchNode(prefix);
        if (prefixNode == null) {
            return results;
        }
        // 从 prefixNode 开始 DFS 遍历所有子树路径
        collectAllWords(prefixNode, new StringBuilder(prefix), results);
        return results;
    }

    /**
     * 删除单词（可选高级操作）
     * 采用自底向上的递归清理空分支
     */
    public boolean delete(String word) {
        if (word == null || word.isEmpty() || !search(word)) {
            return false;
        }
        deleteHelper(root, word, 0);
        size--;
        return true;
    }

    public int size() {
        return size;
    }

    // ========== 私有辅助方法 ==========

    /**
     * 沿着字符串路径查找最终节点
     */
    private TrieNode searchNode(String str) {
        TrieNode current = root;
        for (char ch : str.toCharArray()) {
            if (!current.containsChild(ch)) {
                return null;
            }
            current = current.getChild(ch);
        }
        return current;
    }

    /**
     * DFS 收集以当前节点为根的所有完整单词
     */
    private void collectAllWords(TrieNode node, StringBuilder prefix, List<String> results) {
        if (node.isEndOfWord()) {
            results.add(prefix.toString());
        }
        for (Map.Entry<Character, TrieNode> entry : node.getChildren().entrySet()) {
            prefix.append(entry.getKey());
            collectAllWords(entry.getValue(), prefix, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    /**
     * 递归删除单词并清理无用节点
     */
    private boolean deleteHelper(TrieNode current, String word, int index) {
        if (index == word.length()) {
            current.setEndOfWord(false);
            current.decrementPassCount();
            // 如果没有子节点，可以删除
            return current.getChildren().isEmpty();
        }
        char ch = word.charAt(index);
        TrieNode child = current.getChild(ch);
        boolean shouldDeleteChild = deleteHelper(child, word, index + 1);
        if (shouldDeleteChild) {
            current.getChildren().remove(ch);
            current.decrementPassCount();
            // 如果当前节点既不是单词结尾也没有其他子节点，也可删除
            return !current.isEndOfWord() && current.getChildren().isEmpty();
        }
        current.decrementPassCount();
        return false;
    }
}

三、自动补全系统

基于 Trie 树构建一个实用的命令行自动补全系统，模拟 IDE 或搜索引擎的输入提示效果。

import java.util.List;
import java.util.Scanner;

/**
 * 基于 Trie 的自动补全演示系统
 */
public class AutoCompleteSystem {
    private final Trie trie;

    public AutoCompleteSystem() {
        this.trie = new Trie();
    }

    /**
     * 批量初始化词典
     */
    public void loadDictionary(String[] words) {
        for (String word : words) {
            trie.insert(word.toLowerCase());
        }
        System.out.println("词典加载完成，共 " + trie.size() + " 个单词");
    }

    /**
     * 查询自动补全建议
     */
    public void query(String prefix) {
        prefix = prefix.toLowerCase().trim();
        if (prefix.isEmpty()) {
            System.out.println("请输入非空前缀");
            return;
        }

        List<String> suggestions = trie.autoComplete(prefix);
        int prefixFreq = trie.prefixCount(prefix);

        System.out.println("\n前缀 '" + prefix + "' 的匹配结果：");
        System.out.println("  匹配单词数：" + suggestions.size());
        System.out.println("  前缀频率：" + prefixFreq);

        if (suggestions.isEmpty()) {
            System.out.println("  （无匹配结果）");
        } else {
            // 最多展示 10 条建议
            int limit = Math.min(suggestions.size(), 10);
            for (int i = 0; i < limit; i++) {
                System.out.println("  " + (i + 1) + ". " + suggestions.get(i));
            }
            if (suggestions.size() > limit) {
                System.out.println("  ... 还有 " + (suggestions.size() - limit) + " 条结果");
            }
        }
    }

    /**
     * 交互式命令行界面
     */
    public void interactiveMode() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("\n=== Trie 自动补全系统 ===");
        System.out.println("输入前缀查看补全建议，输入 'quit' 退出");

        while (true) {
            System.out.print("\n> ");
            String input = scanner.nextLine().trim();
            if ("quit".equalsIgnoreCase(input)) {
                System.out.println("再见！");
                break;
            }
            query(input);
        }
    }

    public static void main(String[] args) {
        AutoCompleteSystem system = new AutoCompleteSystem();

        // 模拟编程语言关键词词典
        String[] dictionary = {
            "abstract", "assert", "boolean", "break", "byte",
            "case", "catch", "char", "class", "const",
            "continue", "default", "do", "double", "else",
            "enum", "extends", "final", "finally", "float",
            "for", "goto", "if", "implements", "import",
            "instanceof", "int", "interface", "long", "native",
            "new", "package", "private", "protected", "public",
            "return", "short", "static", "strictfp", "super",
            "switch", "synchronized", "this", "throw", "throws",
            "transient", "try", "void", "volatile", "while",
            // 额外补充一些常见类名和方法前缀
            "string", "stringbuilder", "stringbuffer",
            "system", "scanner", "random", "math",
            "arraylist", "linkedlist", "hashmap", "hashset",
            "treeset", "treemap", "priorityqueue", "arraydeque",
            "comparable", "comparator", "runnable", "callable",
            "exception", "runtimeexception", "throwable", "error"
        };

        system.loadDictionary(dictionary);

        // 演示几个查询
        System.out.println("\n--- 演示查询 ---");
        system.query("st");
        system.query("str");
        system.query("th");
        system.query("java");

        // 进入交互模式
        system.interactiveMode();
    }
}

四、复杂度分析

操作 时间复杂度 空间复杂度 说明
插入 (insert) O(L) O(L) L 为单词长度，最坏情况下每个字符都创建新节点
精确搜索 (search) O(L) O(1) 只需沿着路径遍历，无需额外空间
前缀匹配 (startsWith) O(P) O(1) P 为前缀长度
自动补全 (autoComplete) O(P + M) O(M) P 为前缀长度，M 为子树节点数；结果收集需遍历子树
删除 (delete) O(L) O(1) 递归清理，仅修改引用

与哈希表的对比

场景 Trie 哈希表
精确查找 O(L) O(1) 平均
前缀匹配 O(P) 极快 需遍历所有键 O(N)
自动补全 O(P + M) 高效 需遍历所有键 O(N)
空间占用 公共前缀共享，较节省 每个键独立存储

结论：Trie 树在前缀相关操作上有绝对优势，是自动补全、拼写检查、IP 路由查找等场景的首选数据结构。

五、扩展方向

  1. 压缩 Trie (Radix Tree)：将只有一个子节点的链压缩为单条边，进一步节省空间，常用于 Linux 内核的路由表和 Redis 的集群槽位管理。
  2. 后缀树 (Suffix Tree)：存储字符串的所有后缀，可在 O(L) 时间内解决最长重复子串、最长公共子串等问题。
  3. AC 自动机 (Aho-Corasick)：在 Trie 基础上增加失败指针，实现多模式串的并行匹配，广泛应用于敏感词过滤和病毒特征码扫描。
  4. 持久化 Trie：每次修改创建新路径复用旧节点，支持高效的历史版本查询，常见于区块链状态存储和函数式编程语言。

六、项目结构

trie-demo/
├── src/
│   ├── TrieNode.java
│   ├── Trie.java
│   └── AutoCompleteSystem.java
└── README.md

七、总结

Trie 前缀树通过将字符串按字符层级展开，将前缀匹配的时间复杂度从 O(N) 降低到 O(P)，是处理字符串检索问题的利器。本文用 Java 完整实现了 Trie 的核心操作，并构建了一个可交互的自动补全系统。理解 Trie 的设计思想，不仅能帮助解决实际的字符串检索问题，也为学习更高级的结构（如后缀树、AC 自动机）打下坚实基础。

Tagged with: