字典树

问题描述

字典树（Trie）是一种用于高效存储和查找字符串的树形数据结构。
每个节点代表一个字符，从根节点到某一节点的路径上的字符连接起来，表示该节点对应的字符串。

基本操作

算法思想

将字符串集合构建成树形结构
每个节点包含多个子节点（通常为26个小写字母）
使用标记表示某个节点是否为字符串的结尾
利用字符串的公共前缀来节省空间

时间复杂度

插入时间： $\mathcal{O}(L)$ ，其中 $L$ 是字符串长度
查找时间： $\mathcal{O}(L)$
空间复杂度： $\mathcal{O}(N \cdot \Sigma)$ ，其中 $N$ 是字符串总长度， $\Sigma$ 是字符集大小

代码实现

c++
java
python

class Trie {
private:
    struct TrieNode {
        vector<TrieNode*> children;
        bool isEnd;
        TrieNode() : children(26, nullptr), isEnd(false) {}
    };
    
    TrieNode* root;
    
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return true;
    }
};

class Trie {
    private class TrieNode {
        TrieNode[] children;
        boolean isEnd;
        
        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }
    
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word: str) -> bool:
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end
    
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

压缩字典树

算法思想

合并只有一个子节点的节点链
节省空间但增加了实现复杂度
适用于字符串集合稀疏的情况

时间复杂度

时间复杂度：与普通字典树相同
空间复杂度：显著优于普通字典树

应用场景

前缀匹配
字符串检索
自动补全
拼写检查
IP路由表查找

注意事项

内存使用效率
字符集大小的选择
删除操作的实现
空间与时间的权衡
并发访问的处理

字典树

字典树

问题描述

基本操作

算法思想

时间复杂度

代码实现

压缩字典树

算法思想

时间复杂度

应用场景

注意事项

全站热榜

创作者周榜