一、什么是Trie？

Trie（發音為"try"），也稱為字典樹、前綴樹，是一種多叉樹結構，專門用于高效存儲和檢索字符串集合。其核心特點是共享字符串的公共前綴，從而大幅減少冗余存儲，同時加快查詢速度。

例如，存儲字符串 “apple”、“app”、“apricot” 時，Trie會共享前綴 “ap”，結構如下（簡化示意）：

根節點
|
a
|
p
/ \
p   r
|   |
l   i
|   |
e  ...

二、Trie的結構

Trie的基本組成單位是節點（Node），每個節點包含：

1. 子節點指針數組：用于指向后續字符（如存儲26個小寫字母時，數組大小為26）。
2. 結束標志（isEnd）：布爾值，標記當前節點是否為某個字符串的結尾。

根節點是特殊節點，不存儲任何字符，僅作為所有字符串的起始點。

從根節點到任意一個標記為isEnd = true的節點的路徑，構成一個完整的字符串。

三、Trie的基本操作

Trie的核心操作包括插入（insert）、查找（search） 和前綴查詢（startsWith），三者的時間復雜度均為$O(L)$，其中$L$是字符串的長度。

1. 插入（Insert）

目標：將字符串s插入Trie中。

步驟：

1. 從根節點開始遍歷。
2. 對字符串s的每個字符c：

• 計算字符在數組中的索引（如 c - 'a'，假設為小寫字母）。
• 若當前節點的子節點中不存在c，則創建新節點。
• 移動到對應子節點。

3. 遍歷結束后，將最后一個節點的isEnd標記為true（表示該節點是字符串的結尾）。

2. 查找（Search）

目標：判斷字符串s是否在Trie中。

步驟：

1. 從根節點開始遍歷。
2. 對字符串s的每個字符c：

• 若當前節點的子節點中不存在c，直接返回false。
• 移動到對應子節點。

3. 遍歷結束后，返回最后一個節點的isEnd值（只有isEnd = true才表示完整字符串存在）。

3. 前綴查詢（StartsWith）

目標：判斷Trie中是否存在以字符串s為前綴的字符串。

步驟：

1. 與查找操作類似，從根節點開始遍歷每個字符。
2. 若任何字符不存在，返回false。
3. 遍歷結束后，直接返回true（無需檢查isEnd，因為前綴本身不需要是完整字符串）。

四、時間復雜度分析

• 插入：遍歷字符串的每個字符，時間復雜度為$O(L)$（$L$為字符串長度）。
• 查找：同樣遍歷每個字符，時間復雜度為$O(L)$。
• 前綴查詢：與查找相同，時間復雜度為$O(L)$。

相比哈希表（平均$O(1)$，但最壞$O(N?L)$，$N$為字符串數量），Trie在前綴匹配場景（如自動補全）中更高效，且時間復雜度更穩定。

五、C++代碼實現

1. 節點結構定義

struct TrieNode {// 子節點數組：假設只存儲小寫字母，共26個TrieNode* children[26];// 標記當前節點是否為字符串的結尾bool isEnd;// 構造函數：初始化子節點為nullptr，isEnd為falseTrieNode() {for (int i = 0; i < 26; ++i) {children[i] = nullptr;}isEnd = false;}
};

2. Trie類實現

3. 使用示例

#include <iostream>
int main() {Trie trie;// 插入字符串trie.insert("apple");trie.insert("app");// 查找測試cout << trie.search("apple") << endl;   // 輸出1（true）cout << trie.search("app") << endl;     // 輸出1（true）cout << trie.search("ap") << endl;      // 輸出0（false，不是完整字符串）// 前綴查詢測試cout << trie.startsWith("ap") << endl;  // 輸出1（true，有"apple"和"app"）cout << trie.startsWith("banana") << endl;  // 輸出0（false）return 0;
}

六、Trie的應用場景

1. 自動補全：如搜索引擎輸入前綴后提示完整內容。
2. 拼寫檢查：判斷單詞是否存在于詞典中。
3. IP路由：最長前綴匹配算法（Longest Prefix Matching）。
4. 單詞游戲：如Scrabble中判斷單詞是否有效。

七、總結

Trie是一種針對字符串集合的高效數據結構，通過共享前綴實現快速插入、查找和前綴匹配。其核心優勢是：

• 時間復雜度穩定（$O(L)$），不受字符串數量影響。
• 前綴匹配能力強，適合特定場景。

缺點是空間消耗可能較大（每個節點需要存儲26個指針），但在實際應用中（如詞典、路由表），其效率優勢往往超過空間成本。

掌握Trie對于解決字符串相關的算法題（如LeetCode 208. 實現Trie）非常重要，建議結合實際題目練習加深理解。