van Emde Boas樹

van Emde Boas樹
类型	非二元樹
发明时间	1975年
发明者	Peter van Emde Boas
用大O符号表示的时间复杂度 算法 平均 最差 搜索 $O(\log \log u)$ $O(\log \log u)$ 插入 $O(\log \log u)$ $O(\log \log u)$ 删除 $O(\log \log u)$ $O(\log \log u)$ 用大O符号表示的空间复杂度 空间 $O(u)$ 或 $O(n\log u)$ $O(u)$

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 樹，追蹤哪些簇有資料。當且僅當 T.cluster[i] 非空時 T.summary 才會包含值 $i$。

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

若節點為空，設定 T.min = T.max = NIL，所有找尋操作遇 NIL 都視作「不存在」，部分實作會採用 -1 和 u 來代替。

表示法

在後續的演算法描述中，我們會用到以下函數，設整體鍵值範圍為 $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$

說明：

1. ${\sqrt {u}}$ 是每個簇的大小；
2. $\mathrm {high} (x)$ 給出 $x$ 在哪個簇（簇編號從 0 開始）；
3. $\mathrm {low} (x)$ 給出 $x$ 在該簇內，範圍為 ${\sqrt {u}}$ 內的鍵值（編號也從 0 開始）；
4. $\mathrm {index} (i,j)$ 則把簇編號 $i$ 與簇內鍵值 $j$ 重組為全局鍵值。

可以觀察到： $x=\mathrm {index} \left(\mathrm {high} (x),\,\mathrm {low} (x)\right)$。

基本操作

以下為vEB 樹支援的一些操作:

操作	描述	时间复杂度
插入	在樹中插入一個新值	$O(\log \log u)$
查詢後繼	給定一個數，查找下一個數	$O(\log \log u)$
查詢前驅	給定一個數，查找上一個數	$O(\log \log u)$
刪除	在樹中刪除一個值	$O(\log \log u)$

插入

將值 x 插入到 vEB 樹 T 的操作 insert(T, x) 過程如下：

1. 如果 x 和 T.min 或 T.max 相等，操作結束。
2. 如果 T 為空，則設定 T.min = T.max = x，操作結束。
3. 如果 x < T.min，則將 T.min 和 x 交換，接下來的操作會把舊的T.min插入。
4. 如果 x > T.max，則設定 T.max = x。
5. 最後，把 x 插入到負責 x 的簇 T.cluster[high(x)] 中。如果 T.cluster[high(x)] 之前為空，則同時將 high(x) 插入到 T.summary 中。

程式碼如下:

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.min then
        swap(x, T.min) // 更新最小點，插入舊的最小點
    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)$。

查詢後繼

查詢後繼的過程如下：

1. 如果 x<T.min，則搜索結束，回傳 T.min。如果 x≥T.max，則後繼元素不存在，返回NIL。
2. 否則，計算 i=high(x) 。如果 x < T.cluster[i].max，則要找的值位於 T.cluster[i] 中，因此在 T.cluster[i] 中遞迴搜尋。
3. 否則，在 T.summary 中搜索值 i 的後繼，得到包含大於 x 元素的第一個簇的索引 j。
4. 然後，算法返回 T.cluster[j].min。在簇找到的元素需要與高位組合以形成完整的後繼元素。

程式碼如下:

function FindNext(T, x)
    if x < T.min then
        return T.min
    if x ≥ T.max then // 無後繼數
        return u
    i = high(x)
    
    if low(x) < T.cluster[i].max then // 後繼在這個簇中
        return index(i,FindNext(T.cluster[i], low(x))) 
    
    j = FindNext(T.summary, i)  // 後繼在其他簇，搜尋輔助vEB樹
    if j == NIL then  // 檢查是否存在後繼簇
        return NIL
   else
        return index(j, T.cluster[j].min)  // 與高位合併
end

注意，在任何情況下，這個函式本身執行 $O(1)$ 的工作，然後可能在大小為 $u^{1/2}$ 的簇上遞迴處理。和之前的遞推關係一樣，所以複雜度仍是 $O(\log m)=O(\log \log u)$。

查詢前驅

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

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樹中刪除節點是最複雜的操作。呼叫 Delete(T, x) 來刪除vEB樹T中的值x，其運作方式如下：

1. 如果 T.min = T.max = x，則x是樹中唯一的元素。我們將 T.min = NIL 和 T.max = NIL 來表示樹為空。
2. 否則，如果 x == T.min，則需要找到vEB樹中第二小的值y，從其當前位置刪除它，並設定 T.min=y。第二小的值y是 T.cluster[T.summary.min].min，因此可以在 $O(1)$ 時間內找到。我們從包含y的子樹中刪除它。
3. 如果 x≠T.min 且 x≠T.max，則從包含x的子樹 T.cluster[i] 中刪除x。
4. 如果 x == T.max，則需要找到vEB樹中第二大的值y並設定 T.max=y。首先按照前一種情況刪除x。值y要麼是 T.min，要麼是 T.cluster[T.summary.max].max，因此可以在 $O(1)$ 時間內找到。

在上述任何情況下，如果我們從子樹 T.cluster[i] 中刪除最後一個元素x或y，則還需要從 T.summary 中刪除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 是 T.cluster[i] 中唯一元素時，才會遞迴刪除 T.summary 中對應的元素。

實際實現

實際上並不需要假設 $\log m$ 必須是整數。運算 low(x) 和 high(x) 可以分別替換為只取 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$。

參見

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