Van Emde Boas樹

$O(u)$ 或 $O(n \log u)$

$$O(u)$$

$$O(\log \log u)$$

$$O(\log \log u)$$

$$O(\log \log u)$$

$$O(\log \log u)$$

$$O(\log \log u)$$

$$O(\log \log 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.clusteri 非空時 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$$

說明：

- $\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 樹支援的一些操作:

操作｜描述｜時間複雜度

插入｜在樹中插入一個新值｜$O(\log \log u)$

查詢後繼｜給定一個數，查找下一個數｜$O(\log \log u)$

查詢前驅｜給定一個數，查找上一個數｜$O(\log \log u)$

刪除｜在樹中刪除一個值｜$O(\log \log u)$

### 插入

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

- 如果 x 和 T.min 或 T.max 相等，操作結束。
- 如果 T 為空，則設定 T.min = T.max = x，操作結束。
- 如果 x < T.min，則將 T.min 和 x 交換，接下來的操作會把舊的T.min插入。
- 如果 x > T.max，則設定 T.max = x。
- 最後，把 x 插入到負責 x 的簇 T.clusterhigh(x) 中。如果 T.clusterhigh(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)$。

### 查詢後繼

查詢後繼的過程如下：

- 如果 xx 的高位 $\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$。

## 基本資料

- 日語原文：van Emde Boas樹
- 類型：非二元樹
- 搜索：Peter van Emde Boas
- 演算法：1975年
- space_avg：$O(u)$ 或 $O(n \log u)$
- space_worst：$O(u)$
- search_avg：$O(\log \log u)$
- search_worst：$O(\log \log u)$
- insert_avg：$O(\log \log u)$
- insert_worst：$O(\log \log u)$
- delete_avg：$O(\log \log u)$
- delete_worst：$O(\log \log u)$