Van Emde Boas 树

Van Emde Boas 树
Van Emde Boas 树
类型	非二元树
发明时间	1975年
发明者	Peter van Emde Boas;
算法
用大O符号表示的时间复杂度
算法
搜索
插入
删除
用大O符号表示的空间复杂度
空间

Van Emde Boas 树(或称vEB树或van Emde Boas优先队列)是一个在计算机科学中的数据结构，也是一种关系数组，也是一种树，由荷兰计算机科学家 Peter van Emde Boas^[1]领导的团队于 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)$ 空间。^[2]^[3]^[4]^[5]

结构总览

一棵 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 来代替。 ^[2]^[3]^[4]

表示法

在后续的算法描述中，我们会用到以下函数，设整体键值范围为 $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)$ 。^[4]^[5]

基本操作

以下为vEB 树支持的一些操作:^[2]^[3]^[4]

操作	描述	时间复杂度
插入	在树中插入一个新值	$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.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)$ ^[2]^[3]^[4]。

查询后继

查询后继的过程如下：

如果 x<T.min，则搜索结束，回传 T.min。如果 x≥T.max，则后继元素不存在，返回NIL。
否则，计算 i=high(x) 。如果 x < T.cluster[i].max，则要找的值位于 T.cluster[i] 中，因此在 T.cluster[i] 中递归搜索。
否则，在 T.summary 中搜索值 i 的后继，得到包含大于 x 元素的第一个簇的索引 j。
然后，算法返回 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)$ ^[2]^[3]^[4]。

查询前驱

查询前驱和查询后继的方式大致相似，只有部分地方修改，重点在T.min 也有可能是前驱，但不在子树的任何地方。^[2]^[3]^[4]

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，其运作方式如下：

如果 T.min = T.max = x，则x是树中唯一的元素。我们将 T.min = NIL 和 T.max = NIL 来表示树为空。
否则，如果 x == T.min，则需要找到vEB树中第二小的值y，从其当前位置删除它，并设置 T.min=y。第二小的值y是 T.cluster[T.summary.min].min，因此可以在 $O(1)$ 时间内找到。我们从包含y的子树中删除它。
如果 x≠T.min 且 x≠T.max，则从包含x的子树 T.cluster[i] 中删除x。
如果 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 中对应的元素。^[2]^[3]^[4]

实际实现

实际上并不需要假设 $\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$ 。^[2]^[3]^[4]

参考资料

^ Prof.dr Peter van Emde Boas | Institute for Logic, Language and Computation. www.illc.uva.nl. [2025-04-06].
^ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 van Emde Boas, P.; Kaas, R.; Zijlstra, E. Design and implementation of an efficient priority queue. Mathematical systems theory. 1976-12-01, 10 (1) [2025-04-06]. ISSN 1433-0490. doi:10.1007/BF01683268 （英语）.
^ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Chapter 20: The van Emde Boas tree, pp. 531–560.
^ ^4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 ^4.6 ^4.7 ^4.8 RuntimeErr. 你所不了解的数据结构-van Emde Boas 树. 洛谷专栏. 2021-06-27 [2025-04-06] （中文（中国大陆））.
^ ^5.0 ^5.1 Van Emde Boas Tree | Set 1 | Basics and Construction. GeeksforGeeks. 2019-08-02 [2025-04-27] （美国英语）.

参见

平衡树

树 (数据结构)

[1] Prof.dr Peter van Emde Boas | Institute for Logic, Language and Computation. www.illc.uva.nl. [2025-04-06].

[journal-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 van Emde Boas, P.; Kaas, R.; Zijlstra, E. Design and implementation of an efficient priority queue. Mathematical systems theory. 1976-12-01, 10 (1) [2025-04-06]. ISSN 1433-0490. doi:10.1007/BF01683268 （英语）.

[source1-3] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 ^3.7 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Chapter 20: The van Emde Boas tree, pp. 531–560.

[source2-4] 4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 ^4.6 ^4.7 ^4.8 RuntimeErr. 你所不了解的数据结构-van Emde Boas 树. 洛谷专栏. 2021-06-27 [2025-04-06] （中文（中国大陆））.

[:0-5] 5.0 ^5.1 Van Emde Boas Tree | Set 1 | Basics and Construction. GeeksforGeeks. 2019-08-02 [2025-04-27] （美国英语）.

[1]

[2]

[3]

[4]

[5]

查论编数据结构
类型	集合容器
抽象类型	关联数组多重关连数组串列前向串列堆栈队列双端队列优先队列双端优先队列集合多重集并查集可持久化数据结构线段树
数组	字符串位数组环形缓冲器动态数组哈希表哈希数组树（英语：Hashed array tree）稀疏矩阵
链（英语：Linked data structure）	关联表（英语：Association list）链表跳跃列表松散链表（英语：Unrolled linked list）异或链表
树	线段树 B树二叉树 AA树 AVL树红黑树平衡树伸展树二叉搜索树自平衡二叉查找树堆二叉堆左偏树二项堆斐波那契堆 R树 R*树 R+树希尔伯特R树（英语：Hilbert R-tree）希尔伯特前缀树哈希树
图	有向图有向无环图二元决策图无向图确定性非循环有限自动机（英语：Deterministic acyclic finite state automaton）
数据结构术语列表