van Emde Boas木
van Emde Boas木（vEB木）は、整数キーを効率的に格納・検索するための木構造データ構造であり、挿入、削除、検索、および次/前の要素の検索をO(log log M)時間で実行できる。ここでMはキーの最大値である。このデータ構造はPeter van Emde Boasによって考案された。
背景メモ
- van Emde Boas木（vEB木）は、1975年にオランダの計算機科学者Peter van Emde Boasが考案したデータ構造。整数の集合を保持し、挿入・削除・検索・次/前の要素の取得などの操作をすべてO(log log M)で実行できる。Mは扱う整数の上限値（ユニバースサイズ）。
- 通常の二分探索木がO(log N)（Nは要素数）なのに対し、vEB木はNとは無関係にMの対数の対数に依存する。例えばM=2^32でもlog log M=5回の操作で目的に達する。
- 実用的にはビット長の短い整数や、操作回数が極めて重要なシステム（ルーティングテーブルなど）で使われるが、メモリ使用量が大きく実装が複雑なため、普及は限定的。
- 基本アイデアは「再帰的な分割」：ユニバースを√M個の「クラスター」に分け、各クラスター内で同じ構造を繰り返す。トップレベルのサマリー構造がどのクラスターに要素があるかを管理する。