深入理解Trie树（Java语言Trie树实现与字符串高效检索教程）

例如，如果我们有单词 "app"、"apple"、"apply"，它们共享前缀 "app"，Trie树只需存储一次 "app"，然后分别延伸出不同的后缀。这种结构非常适合用于字典、搜索引擎的自动补全、IP路由等场景。

Trie树的基本结构

在Java中，我们可以定义一个内部类 TrieNode 来表示Trie树的每个节点：

class TrieNode {    // 子节点，数组大小为26（对应a-z）    TrieNode[] children = new TrieNode[26];        // 标记当前节点是否为某个单词的结尾    boolean isEndOfWord = false;}  

说明：

• children 数组用于存储当前字符之后可能出现的字符（这里假设只处理小写英文字母）。
• isEndOfWord 用于标记从根节点到当前节点是否构成一个完整单词。例如，在插入 "app" 后，第二个 'p' 节点的 isEndOfWord 应设为 true。

实现Trie树的核心操作

我们主要实现三个操作：插入（insert）、查找（search）和前缀匹配（startsWith）。

1. 插入单词（insert）

public void insert(String word) {    TrieNode current = root;    for (char c : word.toCharArray()) {        int index = c - 'a';        if (current.children[index] == null) {            current.children[index] = new TrieNode();        }        current = current.children[index];    }    current.isEndOfWord = true;}  

2. 查找完整单词（search）

public boolean search(String word) {    TrieNode node = searchPrefix(word);    return node != null && node.isEndOfWord;}// 辅助方法：查找前缀对应的最后一个节点private TrieNode searchPrefix(String prefix) {    TrieNode current = root;    for (char c : prefix.toCharArray()) {        int index = c - 'a';        if (current.children[index] == null) {            return null;        }        current = current.children[index];    }    return current;}  

3. 判断是否存在以指定前缀开头的单词（startsWith）

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

完整Trie类代码

public class Trie {    private TrieNode root;    public Trie() {        root = new TrieNode();    }    // 插入单词    public void insert(String word) {        TrieNode current = root;        for (char c : word.toCharArray()) {            int index = c - 'a';            if (current.children[index] == null) {                current.children[index] = new TrieNode();            }            current = current.children[index];        }        current.isEndOfWord = true;    }    // 查找完整单词    public boolean search(String word) {        TrieNode node = searchPrefix(word);        return node != null && node.isEndOfWord;    }    // 判断是否存在以prefix开头的单词    public boolean startsWith(String prefix) {        return searchPrefix(prefix) != null;    }    // 辅助方法    private TrieNode searchPrefix(String prefix) {        TrieNode current = root;        for (char c : prefix.toCharArray()) {            int index = c - 'a';            if (current.children[index] == null) {                return null;            }            current = current.children[index];        }        return current;    }    // 节点内部类    private class TrieNode {        TrieNode[] children = new TrieNode[26];        boolean isEndOfWord = false;    }}  

使用示例

public class Main {    public static void main(String[] args) {        Trie trie = new Trie();        trie.insert("apple");        System.out.println(trie.search("apple"));   // true        System.out.println(trie.search("app"));     // false        System.out.println(trie.startsWith("app")); // true        trie.insert("app");        System.out.println(trie.search("app"));     // true    }}  

性能分析与应用场景

时间复杂度：插入和查找操作的时间复杂度均为 O(m)，其中 m 是单词的长度。这比哈希表在最坏情况下的 O(n) 更稳定。

空间复杂度：最坏情况下为 O(ALPHABET_SIZE * N * M)，其中 N 是单词数量，M 是平均长度。但在实际中，由于共享前缀，空间占用通常远小于理论值。

常见应用场景包括：

• 搜索引擎的自动补全（如输入“Jav”提示“Java”、“JavaScript”）
• 拼写检查器
• IP地址路由（最长前缀匹配）
• 敏感词过滤系统

总结

通过本教程，你已经掌握了Java Trie树实现的基本方法，理解了前缀树教程中的核心概念，并学会了如何用它进行字符串高效检索。Trie树虽然简单，但在处理字符串集合时非常高效。希望你能将所学应用到实际项目中，提升程序性能！

如果你对Trie数据结构Java还有疑问，欢迎在评论区留言交流！