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)$