van Emde Boas 树

vEB tree 把一个 $w$ 位键拆成高、低各约一半：高位选择 cluster，低位在 cluster 内递归，summary 再只记录哪些 cluster 非空。每层把宇宙开平方，所以递归深度是 $\log \log U$；代价是朴素结构为整个宇宙预留线性空间。

van Emde Boas 树是利用整数宇宙递归分簇的前驱数据结构；van Emde Boas 布局公理库van Emde Boas 布局van Emde Boas layout · vEB layout递归切分树高并连续摆放上下子树，使根叶路径对未知块大小保持局部性。是把一棵既有树递归排入内存以改善多层缓存局部性的布局。二者共享递归尺度名称，却分别解决查询语义和存储排列问题。

十六元宇宙例子 ​

$U=16$ 时高低各两位，共四个 cluster。集合 $\{2,3,12\}$ 在 cluster 0 存低位 $\{2,3\}$，cluster 3 存 $\{0\}$，summary 为 $\{0,3\}$。查询 10 的前驱时 cluster 2 为空，summary 的前驱是 0，于是返回 cluster 0 的 max，即 3。

空间与模型边界 ​

朴素递归为所有 cluster 预留结构，空间满足 $S(U)=(\sqrt{U}+1)S(\sqrt{U})+O(1)=\mathrm{\Theta }(U)$。当 $U\gg n$ 时不可接受，x/y-fast Trie公理库x-fast 与 y-fast Triex-fast trie · y-fast trie以全前缀哈希实现双对数前驱查询，再用抽样分桶把空间压到线性。以哈希和抽样换线性空间。时间依赖宇宙 $U$ 而非元素数 $n$；它需要整数可分位操作，不适用于任意比较键。

时间界来自递推关系公理库递推关系Recurrence relation用先前项规定序列当前项的关系。 T(U)=T(√U)+O(1)：每次操作只递归进入一个大小约 √U 的簇，并用 summary 处理非空簇前驱。连续开方给 O(log log U)。

Base case 与 min 特判 ​

$U=2$ 时可直接以两个 bit 维护成员。一般节点把全局 min 单独放在 cluster 外：插入小于当前 min 的键时先交换，让旧 min 递归进入 cluster；这使空结构和首元素插入为常数。前驱查询若 $x>\min$ 且所属 cluster 无更小低位，才去 summary 找前一 cluster；若 summary 也无前驱，最后仍可能返回全局 min。

删除最大值同样需在最后非空 cluster 消失时从 summary 与 cluster max 重算。min/max 特判减少递归，却是实现最容易遗漏的正确性分支。

空簇查询的返回路径 ​

求 successor(x) 时，先看 $x$ 所在簇中是否有大于 low(x) 的元素；若有，就在该簇递归。若没有，转而在 summary 中求下一个非空簇编号 $j$，答案是 index(j, cluster[j].min)。summary 也无后继时返回不存在。这个分支解释了为什么每簇必须显式维护 min，也解释了空簇不能先递归再访问其字段。

当 $U=2$ 时直接用两个比特或 min/max 回答，递归停止。若实际键宇宙不是二次幂，可向上取整并拒绝填充区间中的假键；若只说“压缩坐标”，动态插入新键会改变秩，已不再是原本的在线前驱问题。