当前位置：首页 > article >正文

3.5 字典树（Trie）与后缀树

article 2025/1/7 22:37:08

3.5 字典树（Trie）与后缀树

在前面的讨论中，我们涉及了一些常见的树形数据结构，如二叉树、二叉搜索树、平衡二叉树等。但在某些特定场景中，我们需要利用一些特性更强，功能更丰富的树形数据结构。这就引出了本节的主题：字典树和后缀树。

字典树（Trie）

字典树，又被称为前缀树或者Trie树，是一种专门用于处理字符串匹配问题的树形数据结构。在字典树中，节点本身并不直接存储关键字值，而是通过节点到达的路径来代表一个关键字。在一个字典树中，从根节点到某个节点的路径上经过的字符连接起来，为该节点对应的字符串。这种设计使得字典树在处理大量字符串的查找、添加和删除等操作时非常高效。

下面是一个简单的字典树的Java实现：

class TrieNode {
    public boolean isWord; 
    public TrieNode[] children = new TrieNode[26];
    public TrieNode() {}
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            }
            node = node.children[c - 'a'];
        }
        node.isWord = true;
    }

    // 检查单词是否存在
    public boolean search(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.children[c - 'a'] == null) {
                return false;
            }
            node = node.children[c - 'a'];
        }
        return node.isWord;
    }

    // 检查是否存在以某个前缀开头的单词
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (node.children[c - 'a'] == null) {
                return false;
            }
            node = node.children[c - 'a'];
        }
        return true;
    }
}