Van Emde Boas木

van Emde Boas 木 () とは、 ビットの整数による連想配列を実現するための木構造である。オランダの計算機科学者 Peter van Emde Boas らによって 1975 年に開発された。探索・挿入・削除といった操作がすべて最悪計算量 で行える。 
vEB 木の空間計算量は悪く、例えば、32 bit 整数を扱おうとすると、 ビットの記憶域が必要になってしまう。ただし、工夫すれば、扱う要素の数を として の空間計算量を実現することもできる。
操作.
vEB 木は、順序付き連想配列の機能を持ち、挿入・削除・検索の機能を持つ。また、これに加えて、与えられた数の周辺の要素の検索も可能である。
さらに、vEB 木は最小値・最大値のクエリにも対応可能である。 最小値と最大値は木に変数として保存されているため、これらのクエリには で応答できる。
機能.
簡単のため、 がある整数 formula_1 について成り立つとする。また、 とする。vEB 木 の根は、長さ formula_2 の配列 を持つ。 は、formula_3 から formula_4 までの要素を管理する vEB 木へのポインタを持つ。さらに、 はその最小値と最大値 、 と、補助の vEB 木 を持つ。
vEB 木には以下のようにデータが保存される。
木内の最小値は に、最大値は に入る。 以外の全ての値 formula_5 は、formula_6 として で管理される。 は、 のそれぞれの要素が値を持っているかを管理する。つまり、 が空でない場合のみ は値 formula_7 を持つ。
後方検索.
vEB 木上で、"x" 以上で最小の要素を検索する は次のように実現できる：
・もし なら を返す。
・もし ならそのような要素は存在しない。
・formula_6 として、 なら、答えは で再帰的に探索して発見できる。
・そうでなければ、 で "i" 以上の最小の要素 "j" を検索して、 を返す。
 function FindNext(T, x)
 if x < T.min then
 return T.min
 if x ≥ T.max then "// no next element"
 return M
 i = floor(x/)
 lo = x mod 
 if lo < T.children[i].max then
 return ( i) + FindNext(T.children[i], lo)
 j = FindNext(T.aux, i)
 return ( j) + T.children[j].min
 end
最悪の場合でも、この関数で再帰呼び出し以外の計算は で行えて、再帰のたびに木のサイズは元のサイズの平方根となるので、ビット数は半分になる。よって、時間計算量は漸化式 formula_9 で与えられ、このオーダーは となる。
挿入.
vEB 木 への値 の挿入操作 は次のように実現できる：
 function Insert(T, x)
 if T.min > T.max then "// T is empty"
 T.min = T.max = x;
 return
 if x < T.min then
 swap(x, T.min)
 if x > T.max then
 T.max = x
 i = floor(x / )
 lo = x mod 
 Insert(T.children[i], lo)
 if T.children[i].min == T.children[i].max then
 Insert(T.aux, i)
 end
空の vEB 木への要素の挿入は で済む。もしアルゴリズムが再帰呼び出しを二回行っても、一度目の再帰呼び出しは空の vEB 木への挿入であるから、前節と同様に時間計算量の漸化式は formula_9 となる。
削除.
vEB 木からの削除は最も複雑な操作である。
vEB 木 からの値 の削除 は次のように実現できる：
 function Delete(T, x)
 if T.min == T.max == x then
 T.min = M
 T.max = −1
 return
 if x == T.min then
 hi = T.aux.min * 
 j = T.aux.min
 T.min = x = hi + T.children[j].min
 i = floor(x / )
 lo = x mod 
 Delete(T.children[i], lo)
 if T.children[i] is empty then
 Delete(T.aux, i)
 if x == T.max then
 if T.aux is empty then
 T.max = T.min
 else
 hi = T.aux.max * 
 j = T.aux.max
 T.max = hi + T.children[j].max
 end
この操作場合でも、挿入の場合と同じように、ひとつしか要素のない vEB 木からの削除が定数時間で行えることが重要である。2 番目の再帰呼び出しは、"x" が対応する部分木の唯一の要素だった時にのみ発生する。
考察.
 が整数だという仮定は実際には不要である。formula_11 と formula_12 の計算は、上位 ビットと下位 ビットを取る操作で置き換えられる。現実の計算機では、割り算や剰余の計算よりこれはずっと高速である。
実用的な実装、特にビットシフトや最上位の 0 ビットを求める命令を持つマシンでは、" がワードサイズやその小さな倍数に達したら、データの持ち方をビット配列に変更することで、パフォーマンスを向上できる。ワードサイズの値の操作は全て定数時間で行えるので、漸近的な性能には影響しないが、大部分のポインタの保存と参照を省くことができ、大幅な時間計算量と空間計算量の削減が実現できる。
明らかな vEB 木の最適化として考えられるのは、空の部分木を省くことである。必要になるまで部分木が作られないので、多くの要素を含む場合、これで vEB 木のサイズは劇的に小さくなる。最初は、要素が追加されるたびに、合計 個のポインタを含む 個の新しい木が作られる。木が大きくなるにつれて、多くの部分木が再利用されるようになり、 個の要素すべてを持つ木でも、 のメモリしか消費されない。さらに、二分探索木と異なり、このメモリの大部分はデータそのものの保存に使われる。vEB 木全体で持つポインタは、要素が数億あったとしても数千個に収まる。
これはポインタを用いて実装され、空間計算量は となり、キーのある空間の大きさに比例する。これは次のように示される。
空間計算量に対して漸化式を立てると formula_13 となり、これを解くと formula_14 となる。さらに、数学的帰納法により も示される。
類似のデータ構造.
 の空間計算量は、キー空間の大部分が使われる場合以外には無駄が多い。これは vEB 木が実用でそこまで使われていない理由のひとつでもある。これには、子部分木に別のデータ構造を利用することで対処できる。ひとつ考えられるのは、階層ごとに固定されたビット数のみを用いることであり、この結果 trie が得られる。あるいは、配列をハッシュテーブルに置き換え、順序付けを犠牲にして空間計算量を （" は管理するキーの数）に減らすことも考えられる。 や などの別のデータ構造では、vEB 木に匹敵する計算量を持ち、ハッシュテーブルを使って空間計算量を や に削減できる。
実装.
 によって、正しさと時間計算量の両面で検証された実装が存在する。