Van Emde Boas木

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

van Emde Boas 木 (オランダ語発音: [vɑn ˈɛmdə ˈboːɑs]) とは、 $m$ ビットの整数による連想配列を実現するための木構造である。オランダの計算機科学者 Peter van Emde Boas らによって 1975 年に開発された。探索・挿入・削除といった操作がすべて最悪計算量 $O (log log M)$ で行える。

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

操作

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

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

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

機能

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

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

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

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

後方検索

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

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

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

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

・そうでなければ、T.aux で i 以上の最小の要素 j を検索して、T.children[j].min を返す。

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/√M)
    lo = x mod √M
    
    if lo < T.children[i].max then
        return (√M i) + FindNext(T.children[i], lo)
    j = FindNext(T.aux, i)
    return (√M j) + T.children[j].min
end

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

挿入

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

もし T が空なら、T.min = T.max = x として、操作は終了する。
もし x<T.min なら、T.min を対応する部分木 T.children[i] に挿入して、T.min = x とする。もし T.children[i] がもともと空なら、T.aux に i を挿入する。
それ以外の場合、対応する部分木 T.children[i] に x を挿入して、もし T.children[i] がもともと空なら、T.aux に i を挿入する。x>T.max なら、T.max = x とする。とする。

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 / √M)
    lo = x mod √M
    Insert(T.children[i], lo)
    if T.children[i].min == T.children[i].max then
        Insert(T.aux, i)
end

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

削除

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

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

もT.min = T.max = x なら、x が唯一の要素であるから、木は空になり、T.min = M と T.max = −1 とする。
x == T.min なら vEB 木で 2 番目に小さい値 y を探してそれを削除し、T.min = y とする。y は T.children[T.aux.min].min を計算すれば求められるから、 $O (1)$ で求まって、あとは y を部分木から削除すればよいだけである。
x≠T.minかつ x≠T.max なら、T.children[i] から x を削除する。
もし x == T.max なら、vEB 木で 2 番目に大きい値 y を探して、T.max=y としなければならない。前の場合と同じように x を削除した後、2 番目に大きい値は T.min か T.children[T.aux.max].max であるから、 $O (1)$ で計算できる。
上のすべての場合において、削除によって T.children[i] が空になったら、i を T.aux から削除する。

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 * √M
        j = T.aux.min
        T.min = x = hi + T.children[j].min
    i = floor(x / √M)
    lo = x mod √M
    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 * √M
            j = T.aux.max
            T.max = hi + T.children[j].max
end

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

考察

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

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

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

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

空間計算量に対して漸化式を立てると $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}})$ となる。さらに、数学的帰納法により $S (M) = M -2$ も示される。

類似のデータ構造

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

実装

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

出典

^ Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF) (University of Aarhus, Department of Computer Science)

[1] Gudmund Skovbjerg Frandsen: Dynamic algorithms: Course notes on van Emde Boas trees (PDF) (University of Aarhus, Department of Computer Science)

[1]