Van Emde Boas樹

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

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

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

若節點為空，設定 ，所有找尋操作遇  都視作「不存在」，部分實作會採用  和  來代替。
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. . Chapter 20: The van Emde Boas tree, pp. 531–560.

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




說明：
  是每個簇的大小；
  給出  在哪個簇（簇編號從 0 開始）；
  給出  在該簇內，範圍為  內的鍵值（編號也從 0 開始）；
  則把簇編號  與簇內鍵值  重組為全局鍵值。

可以觀察到：
。
 基本操作 
以下為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.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 樹只需  時間，然後在大小為 （即  位二進制數）的子樹上遞迴處理。因此，即使算法有時會進行兩次遞迴調用，這僅在第一次遞迴調用進入空子樹時發生。可以得出這運行時間的遞迴關係是  ，其解為 。

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

 如果 ，則搜索結束，回傳 。如果 ，則後繼元素不存在，返回NIL。
 否則，計算  。如果 ，則要找的值位於  中，因此在  中遞迴搜尋。
 否則，在  中搜索值 i 的後繼，得到包含大於 x 元素的第一個簇的索引 j。
 然後，算法返回 。在簇找到的元素需要與高位組合以形成完整的後繼元素。

程式碼如下:

 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

注意，在任何情況下，這個函式本身執行  的工作，然後可能在大小為  的簇上遞迴處理。和之前的遞推關係一樣，所以複雜度仍是  。

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

 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是 ，因此可以在  時間內找到。我們從包含y的子樹中刪除它。
 如果  且 ，則從包含x的子樹  中刪除x。
 如果 ，則需要找到vEB樹中第二大的值y並設定 。首先按照前一種情況刪除x。值y要麼是 ，要麼是 ，因此可以在  時間內找到。

在上述任何情況下，如果我們從子樹  中刪除最後一個元素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樹中刪除只需  時間。特別是，只有在刪除前 x 是  中唯一元素時，才會遞迴刪除  中對應的元素。

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

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

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

上述實現使用指標，並佔用總空間 ，與鍵值空間的大小成正比。這可以通過以下方式理解：遞迴關係為 。解此遞迴關係會得到 。也可以通過數學歸納法證明 。

 參考資料 

 參見 
 平衡樹
 樹 (資料結構)

Category:数据结构
Category:树结构
Category:树结构