題目
給定固定的整數宇宙，鍵值範圍為 0 到 U-1。請實作 van Emde Boas Tree，支援插入、刪除、成員查詢、最小值、最大值、前驅與後繼。說明高低位分解、summary 結構、空簇處理，以及為什麼操作時間是 O(log log U) 而不是 O(log U)。
面試官考察點
- 能否明確 vEB Tree 依賴固定整數宇宙與位元運算，不能直接取代任意物件鍵的平衡樹。
- 能否正確計算高位簇編號與低位偏移，並讓 summary 記錄非空簇。
- 能否處理空樹、單元素、邊界鍵、刪除最小值與刪除後清理空簇。
- 能否同時說明理論複雜度與 O(U) 空間成本，給出 y-fast trie、排序陣列或普通平衡樹的替代條件。
參考答案
設宇宙大小 U 為 2 的冪，位寬為 w。每個 vEB 節點負責大小為 u 的子宇宙，把鍵拆成高位 cluster 與低位 offset。常用遞迴定義是高半部與低半部各占約一半位寬，因此一個節點擁有約 sqrt(u) 個簇，每個簇又是大小為 sqrt(u) 的 vEB，另有一個大小為 sqrt(u) 的 summary 記錄哪些簇非空。
節點額外維護 min 與 max，避免每次查詢都遞迴到葉子。插入第一個元素時只設定 min 與 max；後續插入先把較小鍵放到 min，再把原 min 插入對應簇。刪除時要處理刪除 min 或 max 後從 summary 找到下一個非空簇，並在簇變空時從 summary 移除。
遞迴深度滿足 T(u)=T(sqrt(u))+O(1)。連續開平方後，宇宙規模的指數每層減半，因此深度為 O(log log U)。空間方面，樸素配置會為每個節點預留簇指標與 summary，整體為 O(U)；稀疏實作可減少常數，但不能自動消除理論上的宇宙依賴。
實作範例
以下偽程式碼使用 high、low 與 index 表示分解與合併，省略記憶體池與參數檢查。
high(x, bits) = x >> ceil(bits / 2)
low(x, bits) = x & ((1 << floor(bits / 2)) - 1)
index(h, l, bits) = (h << floor(bits / 2)) | l
insert(v, x):
if v.min is empty:
v.min = x; v.max = x; return
if x < v.min:
swap(x, v.min)
if v.bits > 1:
h = high(x, v.bits); l = low(x, v.bits)
if v.cluster[h].min is empty:
insert(v.summary, h)
insert(v.cluster[h], l)
if x > v.max:
v.max = x
successor(v, x):
if v.min is empty or x >= v.max: return empty
if v.bits == 1:
return v.max if v.max > x else empty
if x < v.min: return v.min
h = high(x, v.bits); l = low(x, v.bits)
c = v.cluster[h]
if c is not empty and l < c.max:
return index(h, successor(c, l), v.bits)
next_h = successor(v.summary, h)
if next_h is empty: return empty
return index(next_h, v.cluster[next_h].min, v.bits)真實刪除實作需要維護與插入對稱的空簇規則。葉節點通常直接用小位圖或兩個值表示，避免遞迴建立無意義的物件。實作時應先固定位寬計算，再寫隨機操作測試，驗證前驅與後繼和有序集合結果一致。
常見誤區
- 把 U 當成元素數量 n，聲稱所有操作都是 O(log log n)。複雜度參數是宇宙大小 U。
- 忽略 U 不是 2 的冪時的位寬與簇大小取整，導致 high、low 與 index 不互逆。
- 只實作成員查詢與最小值，未處理刪除空簇後 summary 的清理。
- 認為 vEB 一定比紅黑樹更快，忽略 O(U) 空間、快取區域性與真實鍵分布。
- 讓 summary 也使用同樣的遞迴結構，卻沒有明確它的宇宙邊界與空值表示。
複雜度取捨
在鍵是機器字整數、宇宙範圍已知且查詢集中在前驅後繼時，vEB 的 O(log log U) 理論上很有吸引力。若 U 接近 2 的字寬而實際元素很少，樸素空間會浪費；可以改用 x-fast 或 y-fast trie，把空間降到與 n 更相關的規模，但會引入雜湊、隨機性或更複雜的實作。
普通平衡樹提供 O(log n) 操作、O(n) 空間與更簡單的迭代器語意。排序陣列適合靜態集合與批量查詢。面試中應根據鍵域、更新比例、記憶體預算與可維護性選擇，而不是只報出最快的漸進式複雜度。
先測試 U 為 2、4、16 與非冪次宇宙的邊界轉換。再產生隨機插入、刪除與查詢序列，與語言內建有序集合逐步對照 min、max、member、predecessor 與 successor。額外覆蓋重複插入、刪除不存在鍵、刪除最後一個鍵，以及連續刪除 min 或 max 的路徑。
參考資料
- MIT OpenCourseWare 的 van Emde Boas Trees 講義：遞迴分簇、summary 與操作推導。
- Carnegie Mellon Graduate Algorithms Lecture 7：O(log log U) 遞迴分析與實作細節。
- Springer 的 predecessor search 綜述：原始 van Emde Boas 工作與前驅問題背景。
追問
為什麼需要 summary？
目前簇沒有更大元素時，必須快速找到下一個非空簇。summary 把「哪些簇非空」壓縮成另一個前驅後繼問題，避免線性掃描所有簇。
min 與 max 為什麼可以不放進簇？
把 min 與 max 單獨保存能讓空樹與單元素操作成為常數時間，並減少遞迴層數。插入時把較小值交換到 min，刪除時從 summary 找到新的極值再恢復不變量。
U 不是 2 的冪時怎麼辦？
可以向上取整到覆蓋所有鍵的 2 的冪宇宙，並拒絕超出原始範圍的輸入；也可以實作帶取整的簇劃分，但必須證明 high、low、index 的互逆關係與複雜度。
如何把空間從 O(U) 降下來？
使用稀疏簇、x-fast trie 或 y-fast trie。選擇時要說明雜湊衝突、隨機性、迭代器語意與常數開銷，而不是只比較大 O。
什麼場景不該使用 vEB？
鍵域巨大且稀疏、宇宙邊界無法固定、需要通用比較器或必須提供成熟迭代器時，平衡樹或 B-tree 通常更合適。