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.*) 匹配到目的地。

算法是如何“思考”的

这个算法是一个探路者。

1. 节点： 每个节点代表一个字符。
2. 边： 节点之间的链接。
3. 标志： 一个布尔标志 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 树教会我们：开头很重要。通过根据数据的起始方式组织数据，我们可以实时处理输入，在用户输完之前就预测他们的意图。它提醒我们，旅程（前缀）往往与目的地（单词）同样重要。