Van Emde Boas木

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

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

1. 操作
-----

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

挿入：//m//}} ビットのキーと、対応する値のペアを挿入する
削除：与えられたキーを持つ要素を削除する
検索：キーから要素を検索する
後方検索：//k//}} 以上で最小のキーを持つ要素を検索する
前方検索：//k//}} 以上で最大のキーを持つ要素を検索するさらに、vEB 木は最小値・最大値のクエリにも対応可能である。 最小値と最大値は木に変数として保存されているため、これらのクエリには //O//}} で応答できる。

2. 機能
-----

簡単のため、 log2 //m// =}} //k//}} がある整数 について成り立つとする。また、//M// =}} 2//m//}} とする。vEB 木 T}} の根は、長さ の配列 T.children}} を持つ。T.children[i]}} は、 から までの要素を管理する vEB 木へのポインタを持つ。さらに、T}} はその最小値と最大値 T.min}}、T.max}} と、補助の vEB 木 T.aux}} を持つ。

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

木内の最小値は T.min}} に、最大値は T.max}} に入る。 T.min}} 以外の全ての値 は、 として T.children[i]}} で管理される。T.aux}} は、T.children}} のそれぞれの要素が値を持っているかを管理する。つまり、T.children[j]}} が空でない場合のみ T.aux}} は値 を持つ。

2.1. 後方検索
---------

vEB 木上で、//x// 以上で最小の要素を検索する FindNext}} は次のように実現できる：

・もし //x//<T.min}} なら T.min}} を返す。

・もし x≥T.max}} ならそのような要素は存在しない。

・ として、x<T.children[i].max}} なら、答えは T.children[i]}} で再帰的に探索して発見できる。

・そうでなければ、T.aux}} で //i// 以上の最小の要素 //j// を検索して、T.children[j].min}} を返す。function FindNextif x < T.min thenreturn T.minif x ≥ T.max then //// no next element//return M i = floor lo = x mod

if lo < T.children[i].max thenreturn  + FindNext j = FindNextreturn  + T.children[j].minend 最悪の場合でも、この関数で再帰呼び出し以外の計算は //O//}} で行えて、再帰のたびに木のサイズは元のサイズの平方根となるので、ビット数は半分になる。よって、時間計算量は漸化式 で与えられ、このオーダーは 1=//O// = //O//}} となる。

2.2. 挿入
-------

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

もし T}} が空なら、1=T.min = T.max = x}} として、操作は終了する。
もし x<T.min}} なら、T.min}} を対応する部分木 T.children[i]}} に挿入して、1=T.min = x}} とする。もし T.children[i]}} がもともと空なら、T.aux}} に i}} を挿入する。
それ以外の場合、対応する部分木 T.children[i]}} に x}} を挿入して、もし T.children[i]}} がもともと空なら、T.aux}} に i}} を挿入する。x>T.max}} なら、1=T.max = x}} とする。 とする。function Insertif T.min > T.max then //// T is empty// T.min = T.max = x;returnif x < T.min then swapif x > T.max then T.max = x i = floor lo = x mod Insertif T.children[i].min == T.children[i].max then Insertend 空の vEB 木への要素の挿入は //O//}} で済む。もしアルゴリズムが再帰呼び出しを二回行っても、一度目の再帰呼び出しは空の vEB 木への挿入であるから、前節と同様に時間計算量の漸化式は となる。

2.3. 削除
-------

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

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

も1=T.min = T.max = x}} なら、//x// が唯一の要素であるから、木は空になり、1=T.min = M}} と 1=T.max = −1}} とする。
1=x == T.min}} なら vEB 木で 2 番目に小さい値 //y// を探してそれを削除し、1=T.min = y}} とする。//y// は T.children[T.aux.min].min}} を計算すれば求められるから、//O//}} で求まって、あとは //y// を部分木から削除すればよいだけである。
x≠T.min}}かつ x≠T.max}} なら、T.children[i]}} から //x// を削除する。
もし 1=x == T.max}} なら、vEB 木で 2 番目に大きい値 //y// を探して、1=T.max=y}} としなければならない。前の場合と同じように //x// を削除した後、2 番目に大きい値は T.min}} か T.children[T.aux.max].max}} であるから、//O//}} で計算できる。
上のすべての場合において、削除によって T.children[i]}} が空になったら、//i// を T.aux}} から削除する。function Deleteif T.min == T.max == x then T.min = M T.max = −1returnif x == T.min then hi = T.aux.min * j = T.aux.min T.min = x = hi + T.children[j].min i = floor lo = x mod Deleteif T.children[i] is empty then Deleteif x == T.max thenif T.aux is empty then T.max = T.minelse hi = T.aux.max * j = T.aux.max T.max = hi + T.children[j].maxend この操作場合でも、挿入の場合と同じように、ひとつしか要素のない vEB 木からの削除が定数時間で行えることが重要である。2 番目の再帰呼び出しは、//x// が対応する部分木の唯一の要素だった時にのみ発生する。

2.4. 考察
-------

log //m//}} が整数だという仮定は実際には不要である。 と の計算は、上位 ⌈//m///2⌉}} ビットと下位 ⌊//m///2⌋}} ビットを取る操作で置き換えられる。現実の計算機では、割り算や剰余の計算よりこれはずっと高速である。

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

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

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

空間計算量に対して漸化式を立てると となり、これを解くと となる。さらに、数学的帰納法により //S// =}} //M//−2}} も示される。

2.5. 類似のデータ構造
-------------

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

3. 実装
-----

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

4. 出典
-----