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

参见

• 平衡树
• 树 (数据结构)