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