van Emde Boas 树
van Emde Boas 树是一种用于存储整数键的树形数据结构，支持在 O(log log M) 时间内完成查找、插入、删除以及前驱/后继查询等操作，其中 M 是键的取值范围大小。它通过递归地将键空间分层平方根分解来实现高效操作，适用于键值范围已知且相对较小的场景。
背景速读
- **van Emde Boas 树（vEB 树）**是一种用于存储整数的高效数据结构，由荷兰计算机科学家 Peter van Emde Boas 于 1975 年提出。
- 它的核心特点是：在存储 **0 到 2^k − 1** 范围内的整数时，支持**插入、删除、查询前驱/后继**等操作，时间复杂度均为 **O(log log M)**，其中 M 是值域大小。这比传统平衡树（O(log N)）对密集数据集更快。
- 其思想是**递归分治**：将整个值域分成 √M 个块（高位部分），每块再递归细分（低位部分），通过“辅助树”和“簇”结构实现几乎常数级的操作。
- 代价是**空间占用较大**（经典实现 O(M)），因此更适合整数范围有限、对操作速度要求极高的场景，如路由器路由表、数据库索引或操作系统调度器中的时间戳管理。