Van Emde Boas木

**van Emde Boas 木** () とは、 ビットの整数による連想配列を実現するための木構造である。オランダの計算機科学者 Peter van Emde Boas らによって 1975 年に開発された。探索・挿入・削除といった操作がすべて最悪計算量  で行える。 

vEB 木の空間計算量は悪く、例えば、32 bit 整数を扱おうとすると、 ビットの記憶域が必要になってしまう。ただし、工夫すれば、扱う要素の数を  として  の空間計算量を実現することもできる。

## 操作
vEB 木は、順序付き連想配列の機能を持ち、挿入・削除・検索の機能を持つ。また、これに加えて、与えられた数の周辺の要素の検索も可能である。

* 挿入： ビットのキーと、対応する値のペアを挿入する
* 削除：与えられたキーを持つ要素を削除する
* 検索：キーから要素を検索する
* 後方検索： 以上で最小のキーを持つ要素を検索する
* 前方検索： 以上で最大のキーを持つ要素を検索する

さらに、vEB 木は最小値・最大値のクエリにも対応可能である。  最小値と最大値は木に変数として保存されているため、これらのクエリには  で応答できる。

## 機能

簡単のため、  がある整数 k について成り立つとする。また、 とする。vEB 木  の根は、長さ \sqrt{M} の配列  を持つ。 は、i\sqrt{M} から (i+1)\sqrt{M}-1 までの要素を管理する vEB 木へのポインタを持つ。さらに、 はその最小値と最大値 、 と、補助の vEB 木  を持つ。

vEB 木には以下のようにデータが保存される。

木内の最小値は  に、最大値は  に入る。  以外の全ての値 x は、i=\lfloor x/\sqrt{M}\rfloor として  で管理される。 は、 のそれぞれの要素が値を持っているかを管理する。つまり、 が空でない場合のみ  は値 j を持つ。

### 後方検索
vEB 木上で、*x* 以上で最小の要素を検索する  は次のように実現できる：

・もし  なら  を返す。

・もし  ならそのような要素は存在しない。

・i=\lfloor x/\sqrt{M}\rfloor として、 なら、答えは  で再帰的に探索して発見できる。

・そうでなければ、 で *i* 以上の最小の要素 *j* を検索して、 を返す。
 **function** FindNext(T, x)
     **if** x T(m)=T(m/2)+O(1) で与えられ、このオーダーは  となる。

### 挿入
vEB 木  への値  の挿入操作  は次のように実現できる：

# もし  が空なら、 として、操作は終了する。
# もし  なら、 を対応する部分木  に挿入して、 とする。もし  がもともと空なら、 に  を挿入する。
# それ以外の場合、対応する部分木  に  を挿入して、もし  がもともと空なら、 に  を挿入する。 なら、 とする。 とする。

 **function** Insert(T, x)
     **if** T.min > T.max **then** *// T is empty*
         T.min = T.max = x;
         **return**
     **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 木への挿入であるから、前節と同様に時間計算量の漸化式は T(m)=T(m/2)+O(1) となる。

### 削除
vEB 木からの削除は最も複雑な操作である。

vEB 木  からの値  の削除  は次のように実現できる：

# も なら、*x* が唯一の要素であるから、木は空になり、 と  とする。
#  なら vEB 木で 2 番目に小さい値 *y* を探してそれを削除し、 とする。*y* は  を計算すれば求められるから、 で求まって、あとは *y* を部分木から削除すればよいだけである。
# かつ  なら、 から *x* を削除する。
# もし  なら、vEB 木で 2 番目に大きい値 *y* を探して、 としなければならない。前の場合と同じように *x* を削除した後、2 番目に大きい値は  か  であるから、 で計算できる。
# 上のすべての場合において、削除によって  が空になったら、*i* を  から削除する。

 **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* が対応する部分木の唯一の要素だった時にのみ発生する。

### 考察
 が整数だという仮定は実際には不要である。x\sqrt{M} と x\bmod\sqrt{M} の計算は、上位  ビットと下位  ビットを取る操作で置き換えられる。現実の計算機では、割り算や剰余の計算よりこれはずっと高速である。

実用的な実装、特にビットシフトや最上位の 0 ビットを求める命令を持つマシンでは、**' がワードサイズやその小さな倍数に達したら、データの持ち方をビット配列に変更することで、パフォーマンスを向上できる。ワードサイズの値の操作は全て定数時間で行えるので、漸近的な性能には影響しないが、大部分のポインタの保存と参照を省くことができ、大幅な時間計算量と空間計算量の削減が実現できる。

明らかな vEB 木の最適化として考えられるのは、空の部分木を省くことである。必要になるまで部分木が作られないので、多くの要素を含む場合、これで vEB 木のサイズは劇的に小さくなる。最初は、要素が追加されるたびに、合計  個のポインタを含む  個の新しい木が作られる。木が大きくなるにつれて、多くの部分木が再利用されるようになり、 個の要素すべてを持つ木でも、 のメモリしか消費されない。さらに、二分探索木と異なり、このメモリの大部分はデータそのものの保存に使われる。vEB 木全体で持つポインタは、要素が数億あったとしても数千個に収まる。

これはポインタを用いて実装され、空間計算量は  となり、キーのある空間の大きさに比例する。これは次のように示される。

空間計算量に対して漸化式を立てると <math> S(M) = O( \sqrt{M}) + (\sqrt{M}+1) \cdot S(\sqrt{M}) </math> となり、これを解くと <math> S(M) \in (1 + \sqrt{M})^{\log \log M}  + \log \log M \cdot O( \sqrt{M} )</math> となる。さらに、数学的帰納法により  も示される。

=== 類似のデータ構造 ===
 の空間計算量は、キー空間の大部分が使われる場合以外には無駄が多い。これは vEB 木が実用でそこまで使われていない理由のひとつでもある。これには、子部分木に別のデータ構造を利用することで対処できる。ひとつ考えられるのは、階層ごとに固定されたビット数のみを用いることであり、この結果 [[trie]] が得られる。あるいは、配列を[[ハッシュテーブル]]に置き換え、順序付けを犠牲にして空間計算量を  （**' は管理するキーの数）に減らすことも考えられる。x-fast tries や y-fast tries などの別のデータ構造では、vEB 木に匹敵する計算量を持ち、ハッシュテーブルを使って空間計算量を  や  に削減できる。

## 実装
Isabelle によって、正しさと時間計算量の両面で検証された実装が存在する。

*

## 出典