Trie 前缀树

本章导读

Trie（读作 "try"，来自 retrieval）是一种多叉树结构，每条边代表一个字符，从根到叶的路径拼出一个完整字符串。它的核心优势：前缀匹配 O(m)（m 为查询串长度），与存储的字符串总数 n 无关。这让它成为自动补全、拼写检查、IP 路由表的首选数据结构。

53.1 Trie 的原理

存储 {"cat", "car", "card", "dog"} 的 Trie：

//        (root)
//       /      \
//      c        d
//     / \        \
//    a   a        o
//   /     \        \
//  t*     r*        g*
//         |
//         d*
//
// * 表示"词尾"（isEnd = true）
// "car" 和 "card" 共享前缀 "car"
// "cat" 和 "car" 共享前缀 "ca"

关键观察：

• 共享前缀的字符串共享路径——节省空间
• 查找 "car" 只需走 3 步（c→a→r），与词典大小无关
• 前缀 "ca" 下的所有词就是 c→a 子树中的所有 isEnd 节点

53.2 节点设计

class TrieNode
    dict<int, TrieNode> children   // 字符(ASCII) → 子节点
    bool isEnd                      // 是否为某个词的结尾
    int count                       // 经过此节点的词数（用于统计）

    func init()
        children = dict<int, TrieNode>()
        isEnd = false
        count = 0
    end
end

class Trie
    TrieNode root

    func init()
        root = TrieNode()
        root.init()
    end
end

用 dict<int, TrieNode> 存储子节点映射（键为字符 ASCII 值）。对于纯小写字母，也可以用 array<TrieNode>(26) 获得 O(1) 查找，但浪费空间。

53.3 插入操作

func insert(string word)
    TrieNode node = root
    int i = 0
    while i < word.len()
        int ch = word[i]
        if not node.children.has(ch) then
            TrieNode child = TrieNode()
            child.init()
            node.children[ch] = child
        end
        node = node.children[ch]
        node.count += 1
        i += 1
    end
    node.isEnd = true
end

// 使用
Trie trie = Trie()
trie.init()
trie.insert("cat")
trie.insert("car")
trie.insert("card")
trie.insert("dog")

时间复杂度 O(m)，m 为词长。每步检查子节点是否存在，不存在则创建。

53.4 查找操作

// 精确查找：词是否完整存在
func search(string word) as bool
    TrieNode node = findNode(word)
    return node != null and node.isEnd
end

// 前缀查找：是否有词以 prefix 开头
func startsWith(string prefix) as bool
    return findNode(prefix) != null
end

// 辅助：沿路径走到末尾节点
func findNode(string s) as TrieNode
    TrieNode node = root
    int i = 0
    while i < s.len()
        int ch = s[i]
        if not node.children.has(ch) then
            return null
        end
        node = node.children[ch]
        i += 1
    end
    return node
end

// 测试
assert trie.search("car")       // true
assert trie.search("ca") == false  // "ca" 不是完整词
assert trie.startsWith("ca")    // true（有词以 "ca" 开头）
assert trie.search("dog")       // true
assert trie.search("do") == false

search 和 startsWith 的区别：search 要求 isEnd == true（完整词），startsWith 只要求路径存在。

53.5 前缀搜索

找到所有以指定前缀开头的词：

func collectWords(TrieNode node, string prefix, list<string> result)
    if node.isEnd then
        result.push(prefix)
    end
    // 遍历所有子节点（按字符排序）
    list<int> keys = node.children.keys()
    int i = 0
    while i < keys.len()
        int ch = keys[i]
        string newPrefix = prefix + string.char(ch)
        collectWords(node.children[ch], newPrefix, result)
        i += 1
    end
end

func wordsWithPrefix(string prefix) as list<string>
    list<string> result = list<string>()
    TrieNode node = findNode(prefix)
    if node == null then return result end
    collectWords(node, prefix, result)
    return result
end

// 测试
list<string> words = trie.wordsWithPrefix("car")
// → ["car", "card"]
list<string> allC = trie.wordsWithPrefix("c")
// → ["car", "card", "cat"]

53.6 自动补全

自动补全 = 前缀搜索 + 排序 + 限制数量：

func autocomplete(string prefix, int maxResults) as list<string>
    list<string> all = wordsWithPrefix(prefix)
    // 按词频排序（count 越大越热门）或按字母序
    // 这里简单取前 maxResults 个
    list<string> result = list<string>()
    int i = 0
    while i < all.len() and i < maxResults
        result.push(all[i])
        i += 1
    end
    return result
end

// 模拟搜索框
list<string> suggestions = trie.autocomplete("ca", 5)
int i = 0
while i < suggestions.len()
    println("  " + suggestions[i])
    i += 1
end
// 输出：
//   car
//   card
//   cat

53.7 删除操作

删除需要处理共享前缀的情况：

// 懒删除：只标记 isEnd = false
func deleteLazy(string word)
    TrieNode node = findNode(word)
    if node != null then
        node.isEnd = false
    end
end

// 物理删除：回收无用节点
func deletePhysical(string word) as bool
    return deleteHelper(root, word, 0)
end

func deleteHelper(TrieNode node, string word, int depth) as bool
    if depth == word.len() then
        if not node.isEnd then return false end
        node.isEnd = false
        return node.children.len() == 0   // 无子节点则可删除
    end

    int ch = word[depth]
    if not node.children.has(ch) then return false end

    bool shouldDelete = deleteHelper(node.children[ch], word, depth + 1)
    if shouldDelete then
        node.children.remove(ch)
        return not node.isEnd and node.children.len() == 0
    end
    return false
end

// 测试
trie.deletePhysical("card")
assert trie.search("card") == false
assert trie.search("car") == true    // "car" 不受影响

53.8 词频统计

记录每个词被插入的次数：

class TrieWithFreq
    TrieNode root
    dict<string, int> freq   // 词 → 频率

    func insert(string word)
        // ... 同 Trie.insert ...
        if freq.has(word) then
            freq[word] = freq[word] + 1
        else
            freq[word] = 1
        end
    end

    func getFreq(string word) as int
        if freq.has(word) then return freq[word] end
        return 0
    end

    // 热门补全：按频率降序
    func hotComplete(string prefix, int n) as list<string>
        list<string> all = wordsWithPrefix(prefix)
        // 按 freq 降序排序（简单选择排序）
        int i = 0
        while i < all.len()
            int maxIdx = i
            int j = i + 1
            while j < all.len()
                if getFreq(all[j]) > getFreq(all[maxIdx]) then
                    maxIdx = j
                end
                j += 1
            end
            if maxIdx != i then
                string tmp = all[i]
                all[i] = all[maxIdx]
                all[maxIdx] = tmp
            end
            i += 1
        end
        // 取前 n 个
        list<string> result = list<string>()
        int k = 0
        while k < all.len() and k < n
            result.push(all[k])
            k += 1
        end
        return result
    end
end

53.9 完整实现

// trie.xl — 完整测试
Trie trie = Trie()
trie.init()

// 插入词典
trie.insert("apple")
trie.insert("app")
trie.insert("application")
trie.insert("apply")
trie.insert("banana")
trie.insert("band")
trie.insert("bat")

// 精确查找
assert trie.search("app")
assert trie.search("apple")
assert not trie.search("ap")
assert trie.startsWith("ap")

// 前缀搜索
list<string> apps = trie.wordsWithPrefix("app")
println("app* → " + apps.len().toString() + " 个词")
// app, apple, application, apply

list<string> bas = trie.wordsWithPrefix("ba")
println("ba* → " + bas.len().toString() + " 个词")
// banana, band, bat

// 删除
trie.deletePhysical("app")
assert not trie.search("app")
assert trie.search("apple")    // 共享前缀不受影响

// 自动补全
list<string> suggestions = trie.wordsWithPrefix("appl")
println("补全 appl: " + suggestions.len().toString() + " 个")
// apple, application, apply

53.10 性能对比

m = 字符串长度，n = 字符串数量，k = 匹配结果数。Trie 的核心优势在前缀搜索：O(m+k) vs 暴力扫描的 O(n·m)。

深入细节

⚠️ 常见错误

本章小结

复习题

1. Trie 中 "car" 和 "card" 如何存储？它们共享哪些节点？
2. search("app") 和 startsWith("app") 的区别是什么？
3. 前缀搜索的时间复杂度为什么与词典大小无关？
4. 物理删除 "card" 时，为什么不能删除 c→a→r 路径？
5. Trie 相比 dict 的核心优势是什么？劣势是什么？
6. 压缩 Trie（Radix Tree）解决什么问题？
7. 如何用 Trie 实现拼写检查（编辑距离 ≤ 1 的建议）？
8. 对于中文词典，Trie 的边应该用什么作为键？

编程练习