11-字典树（Trie）

💡 核心结论

Trie本质

  • 定义：树形结构，用于高效存储和检索字符串

  • 核心：共享前缀，节省空间

  • 操作：插入O(m)、查找O(m)、前缀匹配O(m)，m为字符串长度

  • 空间：O(总字符数)，但常数大（每个节点26个指针）

  • 应用：自动补全、拼写检查、IP路由

Trie vs 哈希表

特性

Trie

哈希表

查找

O(m)

O(m)

前缀查询

O(m)

O(n×m)

空间

大

小

顺序遍历

支持

不支持

应用场景

  • 自动补全：输入前缀，返回所有单词

  • 拼写检查：查找相似单词

  • 最长公共前缀

  • IP路由表

  • 搜索引擎建议

🌳 Trie结构

插入: "cat", "car", "card", "care", "dog"

       root
       /  \
      c    d
      |    |
      a    o
     /|\   |
    t r e  g
      | |
      d r
      | 
      e

🎯 基本实现

Python实现

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

📚 LeetCode练习

💻 完整代码实现

Python 实现

  1"""
  2字典树（Trie）实现
  3"""
  4
  5class TrieNode:
  6    """Trie节点"""
  7    
  8    def __init__(self):
  9        self.children = {}
 10        self.is_end = False
 11
 12
 13class Trie:
 14    """字典树实现"""
 15    
 16    def __init__(self):
 17        self.root = TrieNode()
 18    
 19    def insert(self, word):
 20        """插入单词"""
 21        node = self.root
 22        for char in word:
 23            if char not in node.children:
 24                node.children[char] = TrieNode()
 25            node = node.children[char]
 26        node.is_end = True
 27    
 28    def search(self, word):
 29        """查找完整单词"""
 30        node = self.root
 31        for char in word:
 32            if char not in node.children:
 33                return False
 34            node = node.children[char]
 35        return node.is_end
 36    
 37    def starts_with(self, prefix):
 38        """查找前缀"""
 39        node = self.root
 40        for char in prefix:
 41            if char not in node.children:
 42                return False
 43            node = node.children[char]
 44        return True
 45    
 46    def get_all_words_with_prefix(self, prefix):
 47        """获取所有以prefix开头的单词"""
 48        node = self.root
 49        for char in prefix:
 50            if char not in node.children:
 51                return []
 52            node = node.children[char]
 53        
 54        result = []
 55        self._dfs(node, prefix, result)
 56        return result
 57    
 58    def _dfs(self, node, path, result):
 59        """DFS收集所有单词"""
 60        if node.is_end:
 61            result.append(path)
 62        
 63        for char, child in node.children.items():
 64            self._dfs(child, path + char, result)
 65    
 66    def delete(self, word):
 67        """删除单词"""
 68        def delete_helper(node, word, index):
 69            if index == len(word):
 70                if not node.is_end:
 71                    return False
 72                node.is_end = False
 73                return len(node.children) == 0
 74            
 75            char = word[index]
 76            if char not in node.children:
 77                return False
 78            
 79            should_delete = delete_helper(node.children[char], word, index + 1)
 80            
 81            if should_delete:
 82                del node.children[char]
 83                return not node.is_end and len(node.children) == 0
 84            
 85            return False
 86        
 87        delete_helper(self.root, word, 0)
 88
 89
 90def demo():
 91    """演示Trie操作"""
 92    print("=== 字典树演示 ===\n")
 93    
 94    trie = Trie()
 95    
 96    # 插入单词
 97    words = ["cat", "car", "card", "care", "dog", "dodge"]
 98    print(f"插入单词: {words}\n")
 99    for word in words:
100        trie.insert(word)
101    
102    # 查找
103    print("查找:")
104    test_words = ["cat", "can", "car", "card"]
105    for word in test_words:
106        found = trie.search(word)
107        print(f"  {word}: {'✅找到' if found else '❌未找到'}")
108    
109    # 前缀查找
110    print("\n前缀查找:")
111    prefixes = ["ca", "do", "da"]
112    for prefix in prefixes:
113        found = trie.starts_with(prefix)
114        print(f"  {prefix}: {'✅存在' if found else '❌不存在'}")
115    
116    # 自动补全
117    print("\n自动补全:")
118    prefix = "car"
119    words = trie.get_all_words_with_prefix(prefix)
120    print(f"  以'{prefix}'开头的单词: {words}")
121
122
123if __name__ == '__main__':
124    demo()
125

C++ 实现

  1/**
  2 * 字典树（Trie）实现
  3 */
  4
  5#include <iostream>
  6#include <string>
  7#include <unordered_map>
  8#include <vector>
  9
 10using namespace std;
 11
 12class TrieNode {
 13public:
 14    unordered_map<char, TrieNode*> children;
 15    bool isEnd;
 16    
 17    TrieNode() : isEnd(false) {}
 18};
 19
 20class Trie {
 21private:
 22    TrieNode* root;
 23    
 24    void deleteTree(TrieNode* node) {
 25        if (node) {
 26            for (auto& [ch, child] : node->children) {
 27                deleteTree(child);
 28            }
 29            delete node;
 30        }
 31    }
 32    
 33    void dfsCollect(TrieNode* node, const string& path, vector<string>& result) {
 34        if (node->isEnd) {
 35            result.push_back(path);
 36        }
 37        
 38        for (auto& [ch, child] : node->children) {
 39            dfsCollect(child, path + ch, result);
 40        }
 41    }
 42
 43public:
 44    Trie() {
 45        root = new TrieNode();
 46    }
 47    
 48    ~Trie() {
 49        deleteTree(root);
 50    }
 51    
 52    // 插入单词
 53    void insert(const string& word) {
 54        TrieNode* node = root;
 55        for (char ch : word) {
 56            if (!node->children.count(ch)) {
 57                node->children[ch] = new TrieNode();
 58            }
 59            node = node->children[ch];
 60        }
 61        node->isEnd = true;
 62    }
 63    
 64    // 查找完整单词
 65    bool search(const string& word) {
 66        TrieNode* node = root;
 67        for (char ch : word) {
 68            if (!node->children.count(ch)) {
 69                return false;
 70            }
 71            node = node->children[ch];
 72        }
 73        return node->isEnd;
 74    }
 75    
 76    // 查找前缀
 77    bool startsWith(const string& prefix) {
 78        TrieNode* node = root;
 79        for (char ch : prefix) {
 80            if (!node->children.count(ch)) {
 81                return false;
 82            }
 83            node = node->children[ch];
 84        }
 85        return true;
 86    }
 87    
 88    // 获取所有以prefix开头的单词
 89    vector<string> getAllWordsWithPrefix(const string& prefix) {
 90        TrieNode* node = root;
 91        for (char ch : prefix) {
 92            if (!node->children.count(ch)) {
 93                return {};
 94            }
 95            node = node->children[ch];
 96        }
 97        
 98        vector<string> result;
 99        dfsCollect(node, prefix, result);
100        return result;
101    }
102};
103
104int main() {
105    cout << "=== 字典树演示 ===" << endl << endl;
106    
107    Trie trie;
108    
109    // 插入单词
110    vector<string> words = {"cat", "car", "card", "care", "dog", "dodge"};
111    cout << "插入单词: ";
112    for (const auto& word : words) {
113        cout << word << " ";
114        trie.insert(word);
115    }
116    cout << endl << endl;
117    
118    // 查找
119    cout << "查找:" << endl;
120    vector<string> testWords = {"cat", "can", "car", "card"};
121    for (const auto& word : testWords) {
122        bool found = trie.search(word);
123        cout << "  " << word << ": " << (found ? "✅找到" : "❌未找到") << endl;
124    }
125    cout << endl;
126    
127    // 前缀查找
128    cout << "前缀查找:" << endl;
129    vector<string> prefixes = {"ca", "do", "da"};
130    for (const auto& prefix : prefixes) {
131        bool found = trie.startsWith(prefix);
132        cout << "  " << prefix << ": " << (found ? "✅存在" : "❌不存在") << endl;
133    }
134    cout << endl;
135    
136    // 自动补全
137    string prefix = "car";
138    cout << "自动补全:" << endl;
139    vector<string> completions = trie.getAllWordsWithPrefix(prefix);
140    cout << "  以'" << prefix << "'开头的单词: ";
141    for (const auto& word : completions) {
142        cout << word << " ";
143    }
144    cout << endl;
145    
146    return 0;
147}