Van Emde Boas木
van Emde Boas 木 (オランダ語発音: [vɑn ˈɛmdə ˈboːɑs]) とは、m ビットの整数による連想配列を実現するための木構造である。オランダの計算機科学者 Peter van Emde Boas らによって 1975 年に開発された。探索・挿入・削除といった操作がすべて最悪計算量 O(log log M) で行える。
vEB 木の空間計算量は悪く、例えば、32 bit 整数を扱おうとすると、M=2 ビットの記憶域が必要になってしまう。ただし、工夫すれば、扱う要素の数を n として O(n) の空間計算量を実現することもできる。
O(M) の空間計算量は、キー空間の大部分が使われる場合以外には無駄が多い。これは vEB 木が実用でそこまで使われていない理由のひとつでもある。これには、子部分木に別のデータ構造を利用することで対処できる。ひとつ考えられるのは、階層ごとに固定されたビット数のみを用いることであり、この結果 trie が得られる。あるいは、配列をハッシュテーブルに置き換え、順序付けを犠牲にして空間計算量を O(n) (n は管理するキーの数)に減らすことも考えられる。x-fast tries や y-fast tries などの別のデータ構造では、vEB 木に匹敵する計算量を持ち、ハッシュテーブルを使って空間計算量を O(n log M) や O(n) に削減できる。