字典樹（Trie） 是一種專門用來處理字串（單字）的樹狀結構，特別適合解決字串（單字）集合中的「前綴匹配」問題。它的每個節點代表一個字母，並且從根節點到某個葉節點的路徑能組成一個完整的字串（單字）。在字典樹中，每個單詞的共用前綴（例如：「cat」和「car」的開頭皆為『c』，故此處指的共用前綴為『c』。）只會儲存一次，因此具有節省空間的效果。字典樹最常見的應用是單詞查詢、拼字檢查和自動補全。每個節點通常有一個字母和指向下一個字母的多個子節點。如果一個單字完全插入到樹中，最後的節點會標記為單字的結尾。插入、查找、刪除操作都能高效率地進行，特別是處理具有共同前綴的單字集合。

【補充】字典樹的根節點

字典樹的根節點是整個字典樹的起點，通常是空的或不包含任何字母。根節點主要作為一個入口，從這裡開始，每一個分支代表著不同的單字或字母的前綴。從根節點向下層層遍歷，直到達到葉節點時，會形成一個完整的單字。

字典樹根節點的特點：

1. 不儲存字母：根節點一般不會儲存具體的字母，只是作為樹的起點。
2. 連接所有單詞的起點：根節點會連接所有插入字典樹的單字，這些單字從根節點開始分叉，逐步形成不同的前綴和單字路徑。
3. 幫助進行查詢和插入操作：從根節點開始，可以方便地進行查詢和插入操作。查詢時，會從根節點依次根據單字的字母進行匹配；插入時，則會從根節點開始創建新的分支節點。

範例說明

假設我們要在字典樹中插入以下單詞：cat、 car、dog、dot。創建字典樹的步驟如下：

1. 插入單字 "cat"：
   • 根節點 → c → a → t，表示 "cat" 完整地插入到字典樹中，最後的 t 節點標記為此單字的結尾。
2. 插入單字 "car"：
   • 前綴 "ca" 和 "cat" 相同，所以共用前面的兩個節點，接著插入新的節點 r，最後的 r 節點同樣標記為單字的結尾。
3. 插入單字 "dog"：
   • 從根節點開始，插入新的分支 d → o → g，最後的 g 節點標記為單字的結尾。
4. 插入單字 "dot"：
   • 由於前綴 "do" 和 "dog" 相同，所以共用這部分的節點，接著插入 t 節點，最後的 t 節點標記為單字的結尾。

最終的字典樹結構如下：

優點：

• 快速的前綴查詢：字典樹的查詢效率很高，特別是查找和自動補全某個前綴。查找時間複雜度為 O(m)，其中 m 是查詢字串的長度。

  例子：如果我們要查詢前綴 "ca"，只需沿著樹遍歷三個節點即可，效率高於線性掃描整個單字列表的方式。

• 節省空間：共用相同前綴的字母只儲存一次，節省了不少空間。例如單詞 "cat" 和 "car" 共用前綴 "ca"，因此樹中不需要重複儲存 "ca"。

• 自動補全：在字典樹中，可以很輕鬆地實現自動補全功能，透過前綴快速查找可能的單字，這是字典樹的強大應用之一。

缺點：

• 空間消耗仍然較大：即使共用前綴，字典樹依然需要儲存每個字母的節點。在最壞的情況下（例如單字之間幾乎沒有前綴共用），空間消耗會比較大。
• 實作複雜度高：字典樹的操作（插入、刪除、查詢等）雖然高效，但其結構和實作相對複雜，特別是在處理多種字串集（如字母表較大的情況）時，節點數量會迅速增加。
• 非最佳查找效率的方法：對於精確匹配查詢，哈希表能在 O(1) 的時間內完成，而字典樹查詢仍需要 O(m)，對於非前綴查詢，字典樹未必是最佳選擇。

參考資料：

1. [九章演算法] 範本 — Trie Tree 字典樹 - Medium by 范德瑞克
2. 資料結構筆記 - Trie - HackMD by blackdiz
3. Trie Data Structure 字典樹 - Medium by tzuyi yang