題干與適用場景
給定 /api、/api/users、/api/users/admin 等字串鍵，實作一棵基數樹。每條邊保存非空字串，每個節點可以保存一個值。支援 insert(key, value)、get(key)、longestPrefix(key) 和 delete(key)。除非題目另有說明，空鍵只允許作為根節點的值。面試官考察資料結構與推導，不是呼叫現成套件。
面試官考察點
- 是否維持每條非根邊非空、同一父節點下子邊首位元組不同的不變量。
- 能否在第一次不匹配處拆分邊，同時保留舊子樹和值。
- 能否區分精確查找與最長前綴查找。
- 刪除後是否只合併無值的單子節點，並給出按鍵長度計算的實際複雜度。
回答前需要釐清的問題
先問鍵以位元組或 Unicode 碼點處理、是否區分大小寫、重複插入是否取代值、是否需要並行，以及最長前綴要回傳匹配鍵、值或兩者。按位元組實作最直接，複雜度按位元組數計算；Unicode 正規化應由樹外策略負責。若需要並行，應明確加入鎖或快照，不要暗示演算法天生具備執行緒安全。
30 秒回答框架
每個節點保存邊標籤、可選值和按首位元組索引的子節點。插入時比較剩餘鍵和子邊標籤：完全匹配就下沉，部分匹配就在共同前綴處拆分成兩個後綴。精確查找必須消耗完整鍵並落在有值節點。最長前綴查找沿路徑記錄最後一個有值節點。刪除先清除值；若節點無值且只有一個子節點，就串接標籤並提升子節點。
分步驟深入解答
- 宣告不變量。 根節點沒有邊標籤，其他節點標籤非空，同一父節點的子節點首位元組不同。節點即使有子節點也可有值，因此
/api與/api/users能共存。 - 按最長共同前綴插入。 設剩餘鍵與子邊標籤的共同前綴為
p。若p為空，換下一個子節點；若p等於整個子邊，消耗後遞迴；若p更短，建立標籤為p的新父節點，把舊節點移到舊後綴下，再掛上新後綴；若新後綴為空，就把值放在拆分節點。 - 查找。 精確查找逐邊消耗，遇到不匹配或缺少子節點就失敗。最長前綴查找先記錄根值，再記錄沿途每個有值節點，鍵消耗完時回傳最後一次記錄。
- 刪除與壓縮。 清除目標值。若節點無值且只有一個子節點，就串接兩個標籤並提升子節點的子樹；若仍有值或有多個子節點則保留節點，維持兄弟不變量。
- 複雜度。 子節點使用雜湊表時，每次操作最多比較輸入鍵的位元組數，因此時間為 O(k) 加雜湊表開銷，空間為所有鍵標籤的總位元組數。路徑壓縮可減少稀疏單鏈節點，但不會讓長鍵變成常數時間。
- 測試對抗案例。 覆蓋空鍵、單字元鍵、先插入長鍵再插入其前綴、反向插入、邊中間拆分、重複取代、刪除葉子、刪除前綴值、刪除唯一鍵，以及沒有匹配的最長前綴查詢。
高品質示範回答
我會讓每條邊保存非空位元組字串，子節點按首位元組存放。插入最關鍵：比較子邊標籤和剩餘鍵，在第一次不匹配處拆分。拆分節點保存共同前綴，舊後綴繼續攜帶原子樹，新後綴掛上新值；若新鍵正好結束，就把值放在拆分節點。查找逐邊匹配，最長前綴查找記住最後一個有值節點。刪除清值後，只合併無值且只有一個子節點的節點。
type node struct {
label string
value any
hasValue bool
child map[byte]*node
}
// common 短於 child.label 時：
parent := &node{label: common, child: map[byte]*node{}}
oldSuffix := child.label[len(common):]
child.label = oldSuffix
parent.child[oldSuffix[0]] = child
parent.child[newSuffix[0]] = &node{label: newSuffix, value: v, hasValue: true}實際程式要處理 newSuffix 為空，把值放在 parent；刪除時只有 hasValue 為 false 且子節點恰好一個才合併。我會在每次變更後檢查不變量，而不只驗證幾個範例查找。
常見錯誤
- 把基數樹寫成每字元一個節點 → 失去路徑壓縮 → 使用非空邊標籤並比較整條標籤。
- 拆邊時丟棄舊值或子樹 → 舊鍵消失 → 先把舊節點按後綴移入，再掛新後綴。
- 最長前綴一遇到值就回傳 → 更具體路由遺失 → 在每個有值節點更新候選。
- 合併仍有值的節點 → 短鍵被誤刪 → 只合併無值的單子節點。
- 聲稱查找 O(1) → 仍需比較鍵 → 說明按鍵長 O(k)，並交代子節點索引成本。
追問及應對
如果鍵不區分大小寫，怎麼改？
在插入和查找前統一依一條明確規則正規化，例如 ASCII 轉小寫。不能只在查找時正規化，否則不同拼法會進入不一致路徑。Unicode 折疊與正規化應作為獨立策略說明。
如何支援通配路由段？
增加明確優先順序，例如靜態邊優先於參數邊，參數邊優先於 catch-all。字面前綴仍可使用基數樹，但匹配會在不同邊型別間搜尋，必須說明最大分支並測試歧義路由。
如何讓樹支援並行讀寫？
使用讀寫鎖或寫入時複製快照。無鎖方案還需要記憶體回收設計；只把根指標設為原子並不能讓原地拆分和合併安全。把資料結構不變量與同步策略分開描述。