猿同學，看你簡歷上說熟悉數據結構，說說你對 Trie 樹的理解。
Trie 樹是一種多叉樹的結構，每個節點保存一個字符，一條路徑上的所有節點保存一個字符串。下圖表示了字符串：him 、 her 、 cat 、 no 、 nova 構成的 Trie 樹。從根節點到某一節點經過的字符連接起來構成一個字符串。如圖中的 him 、 her 、 cat 、 no 、 nova。在實現過程中，會在葉節點中設置一個標誌，用來表示該節點是否是一個字符串的結尾，本例中用青色填充進行標記。Trie 樹中每個節點存儲一個字符，從根節點到葉節點的一條路徑存儲一個字符串。另外，有公共前綴的字符串，他們的公共前綴會共用節點。如 her、 him 共用 h 節點。Trie 樹的生成過程，就是不斷將字符串插入樹中。
以插入字符串 him 、 her 、 cat 、 no 、 nova 為例，過程如下：節點 i 不存在子節點 m，創建子節點 m。並將該節點標記為字符串結束標誌，完成 him 字符串插入。節點 e 不存在子節點 r，創建子節點 r。並將該節點標記為字符串結束標誌，完成 her 字符串插入。節點 a 不存在子節點 t，創建子節點 t。並將該節點標記為字符串結束標誌，完成 cat 字符串插入。節點 n 不存在子節點 o，創建子節點 o。並將該節點標記為字符串結束標誌，完成 no 字符串插入。節點 n 存在子節點 o，不用重新創建子節點 o。節點 v 不存在子節點 a，創建子節點 a。並將該節點標記為字符串結束標誌，完成 nova 字符串插入。情況一：待刪除的字符串末尾為葉節點，且與其它字符串無公共前綴。將節點逐一刪除即可，例如刪除 cat。情況二：待刪除字符串末尾不是葉節點。將字符串標誌位置為 false 即可，例如刪除 no 。情況三：待刪除字符串末尾為葉節點，並且中間有其它單詞。逐一刪除節點，直到待刪除節點是另一個字符串的結尾為止，例如刪除 nova。情況四：待刪除字符串某一節點還有其它子節點。逐一刪除節點，如果待刪除節點還有其它子節點，則停止刪除，例如刪除 him。Trie 樹又叫字典樹。字典是用來查字的，Trie 樹最基本的作用是在樹上查找字符串。
例如有 5 個字符串：him 、 her 、 cat 、 no 、 nova 。現在要查找 catch 是否存在。如果使用暴力的方法，需要用 catch 與這 5 個字符串分別進行匹配，效率較低。如果將這 5 個字符串存儲成 Trie 的結構，只需要順著路徑依次比較，比較完 cat 之後，沒有節點與 c 匹配，所以字符串集合中不存在 catch。寫一下 Trie 樹實現插入，檢索，刪除字符串的代碼。
struct trie_node{ int isKey = 0; trie_node* child[26] = {nullptr}; };
void insert(string s, trie_node* root){ trie_node* p = root; for (auto c : s) { int n = c - 'a'; if (!p->child[n]) { trie_node* q =new trie_node; p->child[n] = q; } p = p->child[n]; } p->isKey = 1;}
bool search(string s, trie_node* root){ trie_node* p = root; for (auto c : s) { int n = c - 'a'; if (!p->child[n]) return 0; p = p->child[n]; } if (p->isKey) return 1; return 0;}void remove(string s, trie_node* root){ if (!search(s, root)) return; stack<trie_node*> stkt; stack<int> stkc; trie_node* p = root; for (auto c : s) { int n = c - 'a'; stkc.push(n); stkt.push(p->child[n]); p = p->child[n]; } p->isKey = 0; while (!stkt.empty()) { trie_node* q; q = stkt.top(); if (q->isKey == 1) return; for (int i = 0; i < 26; i++) { if (q->child[i]) return; } delete q; stkt.pop(); stkt.top()->child[stkc.top()] = nullptr; stkc.pop(); }}在構造樹的過程中，已經將所有字符串遍歷了一遍。可以在 Trie 樹節點的數據結構中，增加一個 count 來計數。對於每個字符串的插入操作，若已存在，計數加 1，若不存在，插入後 count 置為 1。要統計某個字符串出現的次數，只需要找到字符串結尾對應的節點，輸出對應節點的 count 值即可。struct trie_node{ int isKey = 0; int count = 0; trie_node* child[26] = {nullptr}; };
void insert(string s, trie_node* root){ trie_node* p = root; for (auto c : s) { int n = c - 'a'; if (!p->child[n]) { trie_node* q =new trie_node; q->count += 1; p->child[n] = q; } p = p->child[n]; } p->isKey = 1;}
int count(string s, trie_node* root){ if(!search(s,root)) return 0; trie_node* p = root; for (auto c : s) { int n = c - 'a'; p = p->child[n]; } return p->count;}Trie樹的核心思想是空間換時間，利用字符串的公共前綴來減少無謂的字符串比較以達到提高查詢效率的目的。
優點：插入和查詢的效率很高，都為O(m)。其中 m 是待插入/查詢的字符串的長度。