Van Emde Boas木

van Emde Boas tree
種類	非二分木
発表時期	1975
発明者	Peter van Emde Boas
ビッグオー記法による計算量
アルゴリズム 平均 最悪の場合 空間 O(M) O(M) 探索 O(log log M) O(log log M) 挿入 O(log log M) O(log log M) 削除 O(log log M) O(log log M)

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

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

操作

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

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

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

機能

1, 2, 3, 5, 8, 10 が挿入された後の vEB 木と、根が持つ補助構造の例

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

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

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

後方検索

vEB 木上で、x 以上で最小の要素を検索する テンプレート:Mono は次のように実現できる：

・もし テンプレート:Mono なら テンプレート:Mono を返す。

・もし テンプレート:Mono ならそのような要素は存在しない。

・$i=\lfloor x/\sqrt{M}\rfloor$ として、テンプレート:Mono なら、答えは テンプレート:Mono で再帰的に探索して発見できる。

・そうでなければ、テンプレート:Mono で i 以上の最小の要素 j を検索して、テンプレート:Mono を返す。

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/テンプレート:Radic)
    lo = x mod テンプレート:Radic
    
    if lo < T.children[i].max then
        return (テンプレート:Radic i) + FindNext(T.children[i], lo)
    j = FindNext(T.aux, i)
    return (テンプレート:Radic j) + T.children[j].min
end

最悪の場合でも、この関数で再帰呼び出し以外の計算は テンプレート:Math で行えて、再帰のたびに木のサイズは元のサイズの平方根となるので、ビット数は半分になる。よって、時間計算量は漸化式 $T(m)=T(m/2)+O(1)$ で与えられ、このオーダーは テンプレート:Math となる。

挿入

vEB 木 テンプレート:Mono への値 テンプレート:Mono の挿入操作 テンプレート:Mono は次のように実現できる：

1. もし テンプレート:Mono が空なら、テンプレート:Mono として、操作は終了する。
2. もし テンプレート:Mono なら、テンプレート:Mono を対応する部分木 テンプレート:Mono に挿入して、テンプレート:Mono とする。もし テンプレート:Mono がもともと空なら、テンプレート:Mono に テンプレート:Mono を挿入する。
3. それ以外の場合、対応する部分木 テンプレート:Mono に テンプレート:Mono を挿入して、もし テンプレート:Mono がもともと空なら、テンプレート:Mono に テンプレート:Mono を挿入する。テンプレート:Mono なら、テンプレート:Mono とする。 とする。

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 / テンプレート:Radic)
    lo = x mod テンプレート:Radic
    Insert(T.children[i], lo)
    if T.children[i].min == T.children[i].max then
        Insert(T.aux, i)
end

空の vEB 木への要素の挿入は テンプレート:Math で済む。もしアルゴリズムが再帰呼び出しを二回行っても、一度目の再帰呼び出しは空の vEB 木への挿入であるから、前節と同様に時間計算量の漸化式は $T(m)=T(m/2)+O(1)$ となる。

削除

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

vEB 木 テンプレート:Mono からの値 テンプレート:Mono の削除 テンプレート:Mono は次のように実現できる：

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

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 * テンプレート:Radic
        j = T.aux.min
        T.min = x = hi + T.children[j].min
    i = floor(x / テンプレート:Radic)
    lo = x mod テンプレート:Radic
    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 * テンプレート:Radic
            j = T.aux.max
            T.max = hi + T.children[j].max
end

この操作場合でも、挿入の場合と同じように、ひとつしか要素のない vEB 木からの削除が定数時間で行えることが重要である。2 番目の再帰呼び出しは、x が対応する部分木の唯一の要素だった時にのみ発生する。

考察

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

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

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

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

空間計算量に対して漸化式を立てると $S(M)=O(\sqrt{M})+(\sqrt{M}+1)\cdot S(\sqrt{M})$ となり、これを解くと $S(M)\in (1+\sqrt{M}{)}^{\log \log M}+\log \log M\cdot O(\sqrt{M})$ となる。さらに、数学的帰納法により テンプレート:Math も示される。

類似のデータ構造

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

実装

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