1. 題目與適用情境
你需要維護一個動態有序集合，支援依鍵查找、插入、刪除，並偶爾把集合依鍵切成左右兩棵樹再合併。請實作 Treap：每個節點同時滿足依 key 的二元搜尋樹不變量與依隨機 priority 的最大堆不變量。題目先假設鍵唯一，再說明如何處理重複鍵。
2. 面試官考察點
- 能說清楚 BST 不變量與堆不變量分別解決什麼問題。
- 能用
split與merge組合出插入、刪除，而不是只背旋轉程式碼。 - 知道
O(log n)是期望複雜度，隨機數品質與優先級碰撞會影響形狀。 - 能維護子樹大小或聚合值，並指出更新順序與空子樹邊界。
3. 回答前需要釐清的問題
- 鍵是否唯一？若允許重複，要選「相同鍵放左／右」或把
(key, id)當成複合鍵，所有操作都採同一規則。 - 優先級由呼叫端提供還是內部產生？內部產生要說明隨機來源、碰撞處理與測試可重現的種子。
split的邊界是左樹包含key，還是嚴格小於key？這會改變插入與範圍查詢程式。- 是否需要第 k 小、區間和或隱式序列？需要時每個修改函數都必須更新子樹後設資料。
4. 30 秒回答框架
「我把節點依 key 維護 BST 順序，再給每個節點隨機 priority 維護最大堆。核心是 split(T, key) 回傳小於等於 key 與大於 key 的兩棵樹，merge(L, R) 假設 L 的所有 key 小於 R，並依根 priority 選擇新根。插入先 split 再 merge，刪除找到節點後 merge 兩個子樹。每次遞迴返回前更新 size。平均高度與主要操作是 O(log n)，但極端隨機優先級仍可能退化，因此生產實作需要可重現測試、深度監控或有最壞界的平衡樹。」
5. 分步驟深入解答
第一步固定不變量。對任意節點，左子樹 key 不大於節點 key，右子樹 key 更大；節點 priority 不小於兩個子節點。本文採用「相同 key 進入左側」規則，實際實作也可用 (key, uniqueId) 消除歧義。
第二步實作 split。若根 key 小於等於邊界，根與左子樹屬於左結果，只遞迴拆右子樹；否則根屬於右結果，只遞迴拆左子樹。遞迴返回後重新連接對應子節點並更新 size，因此只沿一條根到葉路徑工作。
第三步實作 merge。先處理空樹；若左根 priority 較高，左根保留為根，遞迴把左樹右子樹與右樹合併；否則右根保留為根，遞迴合併左樹與右根左子樹。前提是左樹所有 key 都不大於右樹，否則 BST 不變量會被破壞。
第四步組合操作。插入新節點時 split(root, key)，再 merge(merge(left, node), right)；刪除目標節點時用 merge(node.left, node.right) 替換它。查找沿 key 下降，不需要 split。若維護 size，在每個 split、merge、insert、erase 返回前執行 size = 1 + size(left) + size(right)。
第五步討論複雜度與失敗情境。隨機 priority 讓樹形分布等價於隨機建構的 BST，主要操作期望為 O(log n)；CP-Algorithms 也給出 split、merge、插入與刪除的對數期望複雜度。若隨機來源產生近似單調 priority，樹會退化到 O(n)；需要固定種子測試、監控高度，或改用 AVL、紅黑樹等有最壞界結構。
6. 高品質示範回答
「我會先約定重複鍵規則，再實作兩個原語。split 依邊界回傳左側與右側，遞迴拆一棵子樹後把根重新接回；merge 假設左樹 key 全部不大於右樹，比較兩個根的 priority 決定新根。插入是 split 後把新節點夾在中間，刪除是找到節點後 merge 它的兩個孩子。每次修改都更新子樹 size，因此還能支援第 k 小。隨機 priority 帶來 O(log n) 期望高度，但不是最壞保證；我會用固定種子覆蓋重複鍵、空樹與連續操作，線上監控高度，需要嚴格最壞界時則選紅黑樹。」
7. 常見錯誤
- 錯誤表現 → 只維護 BST 順序 → 有序插入仍退化成鏈表 → 同時維護 priority 堆不變量。
- 錯誤表現 →
merge不檢查兩樹 key 範圍 → 合併後查找路徑錯誤 → 在介面契約明確左樹不大於右樹。 - 錯誤表現 → split 後忘記更新子樹 size → 第 k 小與範圍統計逐漸失真 → 每次重連子節點後立即 pull。
- 錯誤表現 → 把期望
O(log n)當成最壞保證 → 對抗 priority 輸入可構造深樹 → 監控高度，必要時使用 AVL 或紅黑樹。 - 錯誤表現 → 重複鍵規則在查找、刪除與 split 不一致 → 同一鍵可能落入錯誤子樹 → 使用複合鍵或統一左右邊界。
8. 追問及應對
如何支援第 k 小元素？
維護每個節點的子樹 size。查詢時比較左子樹大小與 k；修改路徑上的 split、merge、插入與刪除都要更新 size，否則查詢結果不可信。
如何把 Treap 用作隱式序列？
不顯式儲存 key，把節點在序列中的位置定義為左子樹大小加祖先貢獻。依位置 split，再 merge 回去，就能支援任意位置插入、刪除與區間聚合；還需要 lazy 標記處理區間反轉或加法。
什麼時候不用 Treap？
如果業務要求嚴格最壞 O(log n)、隨機來源不可控，或需要成熟並行實作，優先 AVL、紅黑樹或資料庫索引。Treap 優勢是程式短、split/merge 靈活，代價是期望界與隨機狀態需要測試與監控。