Learning Objectives
- 說明 Trie 一個字元一層、從根到某個節點的路徑就是一個前綴，以及字尾標記的作用
- 追蹤插入時共用既有前綴、只新建缺少的節點
- 分辨「搜尋完整單字」和「搜尋前綴」，說明兩者都只和字串長度有關
- 寫出列出某個前綴開頭所有字的走訪（自動完成），說明依字元排序走訪就會得到字典順序
- 寫出刪除：拿掉字尾標記，並由下往上剪掉沒有用的節點
- 比較 Trie 與雜湊表的取捨，說明 Trie 的空間成本與壓縮 Trie 的想法
輸入法和搜尋框怎麼知道你接下來要打什麼
在搜尋框打 ca，下面立刻列出 car、card、care、cat。這個問題叫前綴查詢：給一個前綴，找出字典裡所有以它開頭的字。
用雜湊表存字典時，查「card 在不在」很快，但雜湊函數會把 car、card、care 打散到不相干的桶裡，
問「哪些字以 ca 開頭」只能把整個字典掃一遍。依字母排序的陣列可以用二分搜尋找到 ca 的範圍，但每加入一個字都要搬動後面的元素。
Trie（字典樹，也叫前綴樹）換個方式存字：一個字元一層。從根出發，讀到 c 就走 c 這條邊，再讀 a 就走 a 這條邊……
開頭相同的字走的是同一條路，所以「以 ca 開頭的字」剛好就是 ca 那個節點底下的整棵子樹。
Trie 這個結構最早由 René de la Briandais 在 1959 年描述；1960 年 Edward Fredkin 發表〈Trie Memory〉，取 retrieval（檢索）的中間幾個字母命名。 Fredkin 的原意是唸成 tree，後來不少人唸成 try，和一般的樹區分。
節點裡放什麼
Trie 的節點本身不存字母，字母寫在邊上。一個節點只有兩個欄位：
| 欄位 | Python | C++ | Java |
|---|---|---|---|
children：字元 → 子節點 |
dict |
map<char, Node*> |
TreeMap<Character, Node> |
end：有沒有一個字在這裡結束 |
bool |
bool |
boolean |
從根走到某個節點，沿路讀到的字元連起來就是一個字串，叫做這個節點代表的前綴。
為什麼需要 end？car 和 card 都在字典裡時，car 的最後一個節點底下還接著 d，它不是葉節點。
只靠「是不是葉節點」分不出 car 是一個字，還是只是 card 的前綴；字尾標記就是用來記錄「到這裡為止是一個完整的字」。
C++ 用 map、Java 用 TreeMap，是因為它們依鍵排序，走訪子節點時自然依字母順序。
Python 的 dict 依加入的先後走訪，所以下面需要順序時都寫 sorted(node.children)，三種語言的輸出才會相同。
下方的視覺化也一律依字元排序畫子節點，字尾節點畫成青綠色，邊上的字母是走到下一層要讀的字元。
插入：共用前綴，只補上缺的節點
依序加入 to、tea、ten、in、inn。加入 to 新建 2 個節點；tea 的 t 已經有了，只新建 e、a 兩個；ten 只要新建 n 一個。看每個字加入後新建了幾個節點，以及哪些節點變成青綠色的字尾。
搜尋單字與搜尋前綴
搜尋只要沿著字串一個字元一個字元往下走，結果有三種：
| 走的結果 | 是完整的單字？ | 是某些字的前綴？ |
|---|---|---|
| 走到一半，某個字元沒有對應的邊（路斷了） | 否 | 否 |
| 走完了，停下的節點有字尾標記 | 是 | 是 |
| 走完了，停下的節點沒有字尾標記 | 否 | 是 |
搜尋單字和搜尋前綴用的是同一段「往下走」的程式，差別只在最後要不要檢查 end。
每讀一個字元只往下走一層，長度 L 的字串最多走 L 層，所以搜尋是 O(L)，和字典裡有幾個字無關。
字典從一百個字變成一百萬個字，查 card 一樣只走 4 層（每一層在 map／TreeMap 裡找子節點要 O(log k)，k 是子節點數，英文小寫最多 26，可以當成常數）。
同一段走法回答兩個問題
to、tea、ten、in、inn 已經加進去了。查 tea 走完 3 層停在字尾：是單字。查 te 也走得完，但停下的節點不是字尾：只是前綴。查 tex 在第 3 個字元找不到 x 這條邊，回傳空值（Python None、C++ nullptr、Java null）。
想一想：Trie 的形狀與搜尋
把 app、apple、apply、ape 加進一個空的 Trie，總共有幾個節點（含根）？
同一個 Trie（app、apple、apply、ape）裡搜尋 appl，結果是？
Trie 裡有 n 個字，搜尋一個長度 L 的字串，最多往下走幾層？
自動完成：走到前綴，再把子樹走完
列出所有以 prefix 開頭的字分兩步：
- 和搜尋一樣，沿著
prefix走到它的節點；路斷了就表示沒有任何字以它開頭 - 從這個節點做深度優先走訪（DFS），一路把走過的字元接在後面；遇到字尾節點就收下目前拼出來的字
走訪子節點時依字元由小到大，收集到的字就自然依字典順序排好，不需要另外排序。 這也是 Trie 比雜湊表多出來的能力：雜湊表的鍵沒有順序，要列出某個範圍的字只能全部掃過再排序。
成本：走到前綴要 O(L)，接著要看前綴底下整棵子樹。實際的自動完成通常只要前幾個建議，可以收集到 k 個字就停下來。
列出以 car、ca 開頭的字
字加入的順序是 card、cat、car、dog、care，但列出來的結果依字典順序：car card care。看 collect 怎麼一層一層往下，path 每深一層就多接一個字元；遇到青綠色的字尾就把 path 收進結果。
刪除：拿掉標記，再由下往上剪
刪除一個字不能直接把路上的節點全拿掉，因為那條路可能被別的字共用。做法是：
- 走到這個字的最後一個節點，拿掉字尾標記
- 回頭往上看：一個節點如果沒有子節點、也不是字尾，就沒有任何字需要它，從父節點剪掉
- 一路往上，遇到還有其他子節點、或本身是另一個字字尾的節點就停
用遞迴寫最自然：remove(node, word, d) 處理第 d 層，回傳「這個節點還有沒有用」，由父節點決定要不要剪掉它。
C++ 剪掉節點前要先 delete，否則那塊記憶體就再也找不回來（記憶體洩漏）；Python 和 Java 只要拿掉參照，沒有人指向的物件由垃圾回收處理。
刪除 card、car、care
字典是 car、card、care、cat。刪 card：d 節點變成沒用，剪掉 1 個。刪 car：r 節點底下還有 e（care），只拿掉字尾標記，剪掉 0 個。刪 care：e 沒用剪掉，r 也沒用了（car 已經刪掉）一起剪掉；a 底下還有 t（cat），停下。
和雜湊表比較，以及空間成本
同樣是存一組字串，Trie 和雜湊表（hash set）各有長處。L 是字串長度：
| 操作 | Trie | 雜湊表 |
|---|---|---|
| 加入、查詢一個字 | O(L) | 平均 O(L)（算雜湊值要看整個字串） |
| 查詢「有沒有字以 p 開頭」 | O(L) | 只能全部掃過 |
| 列出某前綴開頭的所有字、依字典順序 | 走訪子樹，自然有序 | 全部掃過再排序 |
| 記憶體 | 每個字元可能是一個節點，加上子節點表 | 每個字一筆 |
空間成本是 Trie 的主要缺點。子節點表有兩種常見做法：
- 陣列：每個節點固定一個長度 26 的陣列（
children[ch - 'a']），找子節點只要一次索引；但大部分格子是空的，n 個節點就要 26n 個指標 - 雜湊表或排序的 map（本課的寫法）：只存真的有的子節點，省空間，找子節點稍慢
壓縮 Trie（compressed trie，也叫 radix tree）把「只有一個子節點、又不是字尾」的一長串節點合併成一條邊，邊上存一整段字串。
例如字典只有 internet 和 interval 時，i-n-t-e-r 五個節點可以合成一條標著 inter 的邊。節點數會大幅減少，代價是插入時可能要把一條邊從中間切開。
路由器的 IP 位址查詢、許多程式語言的網址路由，都用這一類結構做最長前綴比對。
想一想：自動完成、刪除與取捨
依序加入 tea、ted、ten、te、to，再列出以 te 開頭的字（子節點依字母順序走訪），會印出什麼？
字典只有 app 和 apple。刪除 app 之後，Trie 會剪掉幾個節點？
下面哪一種需求，用 Trie 比用雜湊表更合適？
實作：有幾個字以這個前綴開頭
Trie 和 insert 已經寫好了。請完成 count_words（數一棵子樹裡有幾個字尾）和 count_prefix（先走到前綴的節點，再數它底下有幾個字），印出 ap、app、ba、c 開頭的字各有幾個。預期輸出在右邊；可以切換成你熟悉的語言。
重點整理
- Trie 一個字元一層，字母寫在邊上；從根到某個節點的路徑就是一個前綴，開頭相同的字共用同一條路
- 字尾標記
end記錄「有一個字在這裡結束」，用來分辨car是單字還是只是card的前綴 - 插入：沿路走，缺的節點才新建，最後標字尾；搜尋單字和搜尋前綴走法相同，差別只在最後檢查
end，都是 O(L) - 自動完成：走到前綴的節點，再依字元排序做 DFS，收集到的字自然依字典順序
- 刪除：拿掉字尾標記，再由下往上剪掉「沒有子節點也不是字尾」的節點；C++ 剪掉前要
delete - 和雜湊表比，Trie 多了前綴查詢與有序走訪，代價是記憶體；陣列子節點最快也最佔空間，壓縮 Trie 把單線的節點合成一條邊
下一課：圖的表示法。從樹再往前一步，節點之間可以任意相連，要比較鄰接矩陣、鄰接串列與邊列表各自的成本。