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 樹教會我們：開頭很重要。透過根據數據的起始方式組織數據，我們可以即時處理輸入，在用戶輸完之前就預測她們的意圖。它提醒我們，旅程（前綴）往往與目的地（單詞）同樣重要。