Trie 树 (前缀树)

Published: Sat Feb 21 2026 | Modified: Sat Feb 07 2026 , 3 minutes reading.

Trie 树：先知

算法背后的故事：共享的小径

想象你在词语的森林中漫步。

你想找到 “Cat”（猫）、“Car”（车）和 “Cart”（手推车）。
你会修建三条独立的路吗？不。
你修建一条以 ‘C’ 开头的路，通向 ‘A’。
在 ‘A’ 处，路分岔了：一条通向 ‘T’ (Cat)，一条通向 ‘R’。
在 ‘R’ 处，路又分岔了：一条就在这里结束 (Car)，一条继续通向 ‘T’ (Cart)。

这就是 Trie 树（取自 Retrieval，检索）。它合并了单词共同的开头。它允许你搜索所有以 “Ca” 开头的单词，而无需查看那些以 “Do” 开头的单词。

为什么需要它？

自动补全： 当你输入 “Alg” 时，Google 瞬间建议 “Algorithm”、“Algebra”、“Algiers”。它在 Trie 树中找到了 ‘Alg’ 节点，并查看了其所有子节点。
拼写检查： 如果你输入 “Appl”，Trie 树知道 ‘e’ 是一个有效的后续字符。
IP 路由： 路由器使用 Trie 树将 IP 前缀 (192.168.*) 匹配到目的地。

算法是如何“思考”的

这个算法是一个探路者。

节点： 每个节点代表一个字符。
边：节点之间的链接。
标志： 一个布尔标志 is_end_of_word 标记一个有效单词在哪里结束。（例如，‘Car’ 是一个单词，但它也是 ‘Cart’ 的前缀。节点 ‘r’ 需要一个标志）。

复杂度：

搜索一个长度为 $L$ 的单词需要 $O(L)$ 时间。
它不依赖于字典中单词的数量 ( $N$ )。这就是为什么在前缀搜索中它比哈希表更快。

工程决策：内存成本

Trie 树很快，但它吃内存。

一个标准的 Trie 节点包含一个大小为 26 的数组（对应 ‘a’ 到 ‘z’）。其中大多数通常是空的 (None)。
优化： 工程师使用 基数树 (Radix Tree)（压缩的 Trie），其中单个节点可以保存像 “at” 这样的字符串，而不仅仅是 ‘a’ -> ‘t’。

实现参考 (Python)

class TrieNode:
    def __init__(self):
        self.children = {} # Map: 字符 -> TrieNode
        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

# 使用示例
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))   # True
print(trie.search("app"))     # False (不是完整单词)
print(trie.starts_with("app")) # True

小结

Trie 树教会我们：开头很重要。通过根据数据的起始方式组织数据，我们可以实时处理输入，在用户输完之前就预测他们的意图。它提醒我们，旅程（前缀）往往与目的地（单词）同样重要。

Luke Sun