van Emde Boas樹（或稱vEB樹或van Emde Boas優先隊列）是一個在電腦科學中的資料結構，也是一種關聯陣列，也是一種樹，由荷蘭電腦科學家 Peter van Emde Boas領導的團隊於 1975 年發明，可以儲存鍵值範圍在 m 位以內的二進制整數，也就是 u= 2^m 是樹中可以儲存的最大數字時，它可以在 O(\log m) 時間內執行所有種類的基本操作（假設對 m 的位元操作可以在常數時間內執行），也就是 O(\log \log u)時間。參數u不要與樹中儲存的實際元素數量混淆，其他樹資料結構的效能通常透過該數量來衡量。 標準vEB樹的空間效率不夠。例如，用於儲存 32 位元整數（即當 m=32 ），它需要 u=2^{32} 個儲存位。然而，具有相似的時間效率和空間效率的資料結構可以使用 O(n) 空間（當 𝑛 是儲存元素的數量），但是也可以修改vEB樹讓它只需要 O(n \log u) 空間。

結構總覽
一棵 vEB 樹的每個節點包含以下資料：

• u：紀錄該節點管理的鍵值集合範圍，範圍為 \{0, \ldots, u-1\}。
• min：節點目前儲存的最小元素。若節點為空，則設為NIL標記為空。
• max：節點目前儲存的最大元素。若節點為空，則設為NIL標記為空。
• cluster：一個大小為 \sqrt{u} 的陣列，其中每個元素是指向簇的指標，每個簇是一個子 vEB 樹，第 i 個簇負責管理範圍\{i \sqrt{u}, \ldots, (i+1) \sqrt{u} - 1\}的資料，在該簇中會被重新映射到 \{0, \ldots, \sqrt{u} - 1\} 儲存。
• summary：一棵輔助 vEB 樹，追蹤哪些簇有資料。當且僅當 非空時 才會包含值 i。

值得注意的是，若 x 是最小元素，直接記錄在，不會被記錄在其他地方。

若節點為空，設定 ，所有找尋操作遇 都視作「不存在」，部分實作會採用 和 來代替。

表示法
在後續的演算法描述中，我們會用到以下函數，設整體鍵值範圍為 u，定義:

• \mathrm{high}(x) = \left\lfloor \dfrac{x}{\sqrt{u}} \right\rfloor
• \mathrm{low}(x) = x \bmod \sqrt{u}
• \mathrm{index}(i, j) = i \times \sqrt{u} + j

說明：

\sqrt{u} 是每個簇的大小；

\mathrm{high}(x) 給出 x 在哪個簇（簇編號從 0 開始）；

\mathrm{low}(x) 給出 x 在該簇內，範圍為 \sqrt{u} 內的鍵值（編號也從 0 開始）；

\mathrm{index}(i,j) 則把簇編號 i 與簇內鍵值 j 重組為全局鍵值。

可以觀察到：

x = \mathrm{index}\left( \mathrm{high}(x),\,\mathrm{low}(x) \right)
。
基本操作
以下為vEB 樹支援的一些操作:

插入
將值 插入到 vEB 樹 的操作 過程如下：

如果 和 或 相等，操作結束。

如果 為空，則設定 ，操作結束。

如果 ，則將 和 交換，接下來的操作會把舊的插入。

如果 ，則設定 。

最後，把 插入到負責 的簇 中。如果 之前為空，則同時將 插入到 中。

程式碼如下:

function Insert(T, x)
if T.min == x || T.max == x then // x 已經被插入了
return
if T.min == NIL then // T 是空樹
T.min = T.max = x;
return

if x T.max then
T.max = x // 更新最大點
i = high(x)
Insert(T.cluster[i], low(x))
if T.cluster[i].min == T.cluster[i].max then
Insert(T.summary, i)
end

此過程的效率關鍵在於，將元素插入到空的 vEB 樹只需 O(1) 時間，然後在大小為 u^{1/2}（即 m/2 位二進制數）的子樹上遞迴處理。因此，即使算法有時會進行兩次遞迴調用，這僅在第一次遞迴調用進入空子樹時發生。可以得出這運行時間的遞迴關係是 T(m) = T(m/2) + O(1)，其解為 O(\log m) = O(\log \log u)。

查詢後繼
查詢後繼的過程如下：

如果 ，則搜索結束，回傳 。如果 ，則後繼元素不存在，返回NIL。

否則，計算 。如果 ，則要找的值位於 中，因此在 中遞迴搜尋。

否則，在 中搜索值 i 的後繼，得到包含大於 x 元素的第一個簇的索引 j。

然後，算法返回 。在簇找到的元素需要與高位組合以形成完整的後繼元素。

程式碼如下:

function FindNext(T, x)
if x O(1) 的工作，然後可能在大小為 u^{1/2} 的簇上遞迴處理。和之前的遞推關係一樣，所以複雜度仍是 O(\log m) = O(\log \log u)。

查詢前驅
查詢前驅和查詢後繼的方式大致相似，只有部分地方修改，重點在 也有可能是前驅，但不在子樹的任何地方。

function FindPrev(T, x)
if x > T.max then
return T.max
if x ≤ T.min then // 無前驅數
return NIL
i = high(x)

if low(x) > T.cluster[i].min then // 前驅在這個簇
s = FindPrev(T.cluster[i], low(x))
if s == NIL then // 前驅在T.min
return T.min
return index(i,s) // 與高位合併
j = FindPrev(T.summary, i) // 前驅在其他子樹，搜尋輔助vEB樹
if j == NIL then // 檢查是否存在前驅子樹
return NIL
else
return index(j, T.cluster[j].max) // 與高位合併
end

刪除
從vEB樹中刪除節點是最複雜的操作。呼叫 來刪除vEB樹T中的值x，其運作方式如下：

如果 ，則x是樹中唯一的元素。我們將 和 來表示樹為空。

否則，如果 ，則需要找到vEB樹中第二小的值y，從其當前位置刪除它，並設定 。第二小的值y是 ，因此可以在 O(1) 時間內找到。我們從包含y的子樹中刪除它。

如果 且 ，則從包含x的子樹 中刪除x。

如果 ，則需要找到vEB樹中第二大的值y並設定 。首先按照前一種情況刪除x。值y要麼是 ，要麼是 ，因此可以在 O(1) 時間內找到。

在上述任何情況下，如果我們從子樹 中刪除最後一個元素x或y，則還需要從 中刪除i。

程式碼如下:
function Delete(T, x)
// 刪除最後一個元素
if T.min == T.max == x then
T.min = NIL // 標記空樹
T.max = NIL
return
// 刪除當前最小值
if x == T.min then
j = T.summary.min // 通過輔助樹找最小簇索引
T.min = x = index(j, T.cluster[j].min) // 新min = 樹中存在的最小值
Delete(T.cluster[j], T.cluster[j].min) // 從子樹中刪除，因為T.min不應在子樹中出現
return
// 分解高位和低位
i = high(x) // 計算簇索引
// 遞迴刪除
Delete(T.cluster[i], low(x))
// 處理空子樹
if T.cluster[i] is empty then
Delete(T.summary, i) // 從輔助樹刪除該子樹索引
// 刪除的是當前最大值
if x == T.max then
if T.summary is empty then // 沒有其他子樹
T.max = T.min // 只剩min值
else
j = T.summary.max //找最大值
T.max = index(j, T.cluster[j].max) // 合併
end

同樣，此程序的效率取決於從僅包含一個元素的vEB樹中刪除只需 O(1) 時間。特別是，只有在刪除前 x 是 中唯一元素時，才會遞迴刪除 中對應的元素。

實際實現
實際上並不需要假設 \log m 必須是整數。運算 和 可以分別替換為只取 x 的高位 \lceil m/2 \rceil 位元和低位 \lfloor m/2 \rfloor 位元。在大部分情況下，這都比除法或取餘運算更高效。

在實際實現中，特別是在具有「位移 k 位」和「尋找首位零」指令的機器上，當 m 達到字長（或其小倍數）時，可以切換為使用位陣列來進一步提升效能。由於單一字長上的所有操作都是常數時間，這不會影響漸進效能，但能避免多數指標儲存和多次指標解引用，從而顯著節省實際的時間和空間。

vEB 樹的一個優化是捨棄空子樹。這使得 vEB 樹在包含大量元素時非常緊湊，因為只有在需要添加元素時才會創建子樹。最初，每添加一個元素會創建約 \log(m) 個新樹，總共包含約 m/2 個指標。隨著樹的增長，越來越多的子樹會被重複使用，尤其是較大的子樹。

上述實現使用指標，並佔用總空間 O(u) = O(2^m)，與鍵值空間的大小成正比。這可以通過以下方式理解：遞迴關係為 S(u) = O( \sqrt{u}) + (\sqrt{u}+1) \cdot S(\sqrt{u}) 。解此遞迴關係會得到 S(u) \in (1 + \sqrt{u})^{\log \log u} + \log \log u \cdot O( \sqrt{u} )。也可以通過數學歸納法證明 S(u) = u-2。

參考資料
參見

• 平衡樹
• 樹 (資料結構)