Trie算法详解（Java语言实现前缀树完整教程）

Trie的核心优势

• 查找、插入和删除操作的时间复杂度为 O(m)，其中 m 是字符串长度，与字典中单词总数无关。
• 天然支持前缀匹配，非常适合实现自动补全功能。
• 节省空间（尤其当字符串有大量公共前缀时）。

Java实现Trie树

我们首先定义Trie的节点类 TrieNode：

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

接下来，我们构建主类 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;    }    // 检查是否有以指定前缀开头的单词    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;    }}

使用示例

下面是如何使用我们刚实现的Trie：

public class Main {    public static void main(String[] args) {        Trie trie = new Trie();                // 插入单词        trie.insert("apple");        trie.insert("app");        trie.insert("bat");                // 搜索        System.out.println(trie.search("app"));     // true        System.out.println(trie.search("appl"));    // false        System.out.println(trie.startsWith("ap"));  // true        System.out.println(trie.startsWith("ba"));  // true    }}

常见应用场景

Trie算法在实际开发中有广泛用途：

• 搜索引擎自动补全：用户输入时实时推荐相关搜索词。
• 拼写检查器：快速判断单词是否存在于词典中。
• IP路由表：高效匹配最长前缀（虽然通常使用压缩Trie如Radix Tree）。
• 敏感词过滤：批量检测文本中是否包含违规词汇。

总结

通过本教程，你已经掌握了Java Trie实现的核心逻辑。Trie作为一种高效的字符串搜索优化工具，在处理大量文本数据时能显著提升性能。记住，理解数据结构的关键在于动手实践——尝试扩展这个Trie，比如支持大小写、Unicode字符或添加删除功能！

关键词回顾：Trie算法、Java Trie实现、前缀树教程、字符串搜索优化