强烈建议在继续阅读之前，先完全理解 Proto Van Emde Boas 树。Van Emde Boas 树支持搜索、后继、前驱、插入和删除操作，时间复杂度均为 O(lglgN)，这比优先队列、二叉搜索树等相关数据结构都要快。Van Emde Boas 树在处理最小值和最大值查询时，时间复杂度为 O(1)。这里 N 是树所定义的 universe（全域）的大小，lg 表示以 2 为底的对数。
注意： Van Emde Boas 数据结构的键集必须定义在 0 到 n 的范围内（n 是形式为 2^k 的正整数），并且它在不允许有重复键的情况下工作。
缩写：
- VEB 是 Van Emde Boas 树的缩写。
- VEB(\sqrt{u}) 是包含 u 个键的 VEB 的缩写。
Van Emde Boas 树的结构：
Van Emde Boas 树是一种递归定义的结构。
- u：VEB 树中存在的键的数量。
- Minimum（最小值）：存储 VEB 树中存在的最小键。
- Maximum（最大值）：存储 VEB 树中存在的最大键。
- Summary（摘要）：指向一个新的 VEB(\sqrt{u}) 树，其中包含 clusters（集群）数组中键的概览。
- Clusters（集群）：一个大小为 \sqrt{u} 的数组，数组中的每个位置都指向一个新的 VEB(\sqrt{u}) 树。
请看下图以理解 Van Emde Boas 树的基础知识，尽管它并不代表 Van Emde Boas 树的实际结构：
Van Emde Boas 树的基本理解：
- Van Emde Boas 树是一种类似于 Proto Van Emde Boas 树的递归定义结构。
- 在 Van Emde Boas 树中，最小值和最大值查询的时间复杂度为 O(1)，因为树结构中存储了最小和最大键。
- 添加最大值和最小值属性的优势，有助于降低时间复杂度：
– 如果 VEB 树的最小值或最大值为空（代码中为 NIL 或 -1），则表示树中没有元素。
– 如果最小值和最大值相等，则结构中只存在一个值。
– 如果两者都存在且不同，则树中存在两个或更多元素。
– 我们可以通过根据条件简单地设置最大值和最小值来在常数时间内插入和删除键，这有助于减少递归调用链：如果 VEB 中只有一个键，要删除该键，我们只需将 min 和 max 设置为 nil 值。同样，如果没有键存在，我们可以通过将 min 和 max 设置为我们想要插入的键来插入键。这些都是 O(1) 操作。
– 在后继和前驱查询中，我们可以根据 VEB 的最小值和最大值做出决策，这将使我们的工作更加轻松。
在 Proto Van Emde Boas 树中，全域的大小被限制为 2^2^k 类型，但在 Van Emde Boas 树中，它允许全域大小为 2 的精确幂。因此，我们需要修改 Proto Van Emde Boas 树中使用的 High(x)、low(x)、generate_index() 辅助函数，如下所示。
- High(x)：它将返回 floor( x/ceil(\sqrt{u}) )，基本上就是键 x 所在的集群索引。
High(x) = floor(x/ceil(\sqrt{u}))
- Low(x)：它将返回 x mod ceil( \sqrt{u}) )，即它在集群中的位置。
Low(x) = x % ceil( \sqrt{u})
- generate_index(a, b)：它将根据键在集群 b 中的位置及其集群索引 a 返回键的位置。
generate_index(a, b) = a * ceil(\sqrt{u}) + b
Van Emde Boas 树的构建：
Van Emde Boas 树的构建与 Proto Van Emde Boas 树非常相似。这里的区别在于我们允许全域大小是 2 的任意幂，因此 high()、low() 和 generate_index() 会有所不同。
要构建空的 VEB：
过程与 Proto VEB 相同，只是每个 VEB 中会添加最小值和最大值。为了表示最小值和最大值为空，我们将用 -1 表示。
注意：在基础情况（Base Case）下，我们只需要最小值和最大值，因为在添加 min 和 max 值后，添加大小为 2 的集群将是多余的。
下面是实现：
C++
// C++ implementation of the approach
#include
using namespace std;
class VanEmdeBoas {
public:
int universe_size;
int minimum;
int maximum;
VanEmdeBoas* summary;
vector<VanEmdeBoas*> clusters;
// Function to return cluster numbers
// in which key is present
int high(int x)
{
int div = ceil(sqrt(universe_size));
return x / div;
}
// Function to return positio