ファン・エムデ・ボアスの木

ファン・エムデ・ボアスの木
タイプ	非バイナリツリー
発明された	1975
発明者	ピーター・ファン・エムデ・ボアス
ビッグ O 記法による時間計算量 手術 平均 最悪の場合 検索 ${\displaystyle O(\log \log M)}$ ${\displaystyle O(\log \log M)}$ 入れる ${\displaystyle O(\log \log M)}$ ${\displaystyle O(\log \log M)}$ 消去 ${\displaystyle O(\log \log M)}$ ${\displaystyle O(\log \log M)}$ 空間の複雑さ 空間 ${\displaystyle O(M)}$ ${\displaystyle O(M)}$

ファン・エムデ・ボアス木（オランダ語発音: [vɑn ˈɛmdə ˈboːɑs] ）は、 vEB木やファン・エムデ・ボアス優先キューとも呼ばれ、mビットの整数キーを持つ連想配列を実装する木構造です。これは、オランダのコンピュータ科学者ピーター・ファン・エムデ・ボアス率いるチームによって1975年に発明されました。 ^[1]この木構造では、すべての操作がO (log  m )時間（ビット操作が定数時間で実行できると仮定）で実行されます。つまり、は木に格納できる最大の要素です。このパラメータは、他の木構造のパフォーマンスの尺度としてよく使用される、木に格納されている実際の要素数と混同しないでください。 ${\displaystyle m}$${\displaystyle O(\log \log M)}$${\displaystyle M=2^{m}}$${\displaystyle M}$

標準の vEB ツリーは、スペース効率が不十分です。たとえば、32 ビットの整数 (つまり、 のとき) を格納する場合、 ビットのストレージが必要です。ただし、時間効率が同等で、スペース効率が である類似のデータ構造が存在し、 は格納される要素の数であり、vEB ツリーは必要なスペースが のみになるように変更できます。 ${\displaystyle m=32}$${\displaystyle M=2^{32}}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle O(n\log M)}$

vEBは順序付き連想配列の操作をサポートしており、これには通常の連想配列操作に加えて、さらに2つの順序操作であるFindNextとFindPreviousが含まれています。^[2]

• 挿入: mビットのキーを持つキー/値のペアを挿入します。
• 削除: 指定されたキーのキー/値のペアを削除します
• 検索: 指定されたキーに関連付けられた値を見つける
• FindNext : 指定されたkより大きい最小のキーを持つキー/値のペアを検索します。
• FindPrevious : 指定されたkより小さい最大のキーを持つキー/値のペアを検索します。

vEBツリーは、それぞれツリーに格納されている最小要素と最大要素を返すMinimumとMaximum という操作もサポートしています。 ^[3]最小要素と最大要素は各ツリーの属性として格納されるため、 これらは両方とも時間内に実行されます。${\displaystyle O(1)}$

をある整数 とします。 を定義します。宇宙上のvEB ツリーT には、長 さ の配列T.childrenを格納するルート ノードがあります。T.children[i] は、値 を担当する vEB ツリーへのポインタです。さらに、T には2 つの値T.minとT.maxのほか、補助的な vEB ツリーT.auxも格納されます。 ${\displaystyle \log_{2}m=k}$${\displaystyle k}$${\displaystyle M=2^{m}}$${\displaystyle \{0,\ldots,M-1\}}$${\displaystyle {\sqrt {M}}}$${\displaystyle \{i{\sqrt {M}},\ldots ,(i+1){\sqrt {M}}-1\}}$

データは次のように vEB ツリーに格納されます。ツリー内の現在の最小値はT.minに格納され、最大値はT.maxに格納されます。T.minはvEB ツリーの他の場所には格納されませんが、T.maxは格納されることに注意してください。T が空の場合、 T.max=−1およびT.min=Mという規則を使用します。その他の値は、サブツリーT.children [i]に格納されます。補助ツリーT.aux は、どの子が空でないかを追跡するため、T.children[j]が空でない 場合のみ、T.aux に値が含まれます。${\displaystyle x}$${\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor }$${\displaystyle j}$

vEB ツリーで要素xの後続要素を検索する操作FindNext(T, x)は、次のように進行します。 x <T.minの場合、検索は完了し、答えはT.minです。x≥T.maxの場合、次の要素が存在しない場合は、 M を返します。それ以外の場合は、とします。x<T.children[i].maxの場合、検索対象の値はT.children[i]に含まれているため、検索はT.children[i]で再帰的に進みます。それ以外の場合は、値iの後続要素をT.auxで検索します。これにより、 xより大きい要素を含む最初のサブツリーのインデックスjが得られます。次に、アルゴリズムはT.children[j].minを返します。children レベルで見つかった要素は、完全な次の要素を形成するために上位ビットと合成する必要があります。 ${\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor }$

function FindNext(T, x)
     if x < T.min then 
        return T.min
     if x ≥ T.max then  // 次の要素はありません
        return M
    i = 床(x/ )${\displaystyle {\sqrt {M}}}$
    lo = x mod${\displaystyle {\sqrt {M}}}$
    
    lo < T.children[i].maxの場合は(
         i ) + FindNext(T.children[i], lo)を返す${\displaystyle {\sqrt {M}}}$
    j = FindNext(T.aux, i)
    戻り値( j) + T.children[j].min
終了${\displaystyle {\sqrt {M}}}$

いずれの場合でも、アルゴリズムは作業を実行し、その後、サイズのユニバース（ビットユニバース）上のサブツリーを再帰する可能性があることに注意してください。これにより、 の実行時間の再帰が得られ、 に解決されます。 ${\displaystyle O(1)}$${\displaystyle M^{1/2}}$${\displaystyle m/2}$${\displaystyle T(m)=T(m/2)+O(1)}$${\displaystyle O(\log m)=O(\log \log M)}$

値x をvEB ツリーTに挿入する呼び出しinsert(T, x) は次のように動作します。

1. Tが空の場合は、 T.min = T.max = xを設定して完了です。
2. それ以外の場合、x<T.minであれば、 T.minを担当するサブツリーiにT.minを挿入し、T.min = xに設定します。T.children [i]が以前は空だった場合は、 iをT.auxにも挿入します。
3. それ以外の場合、x>T.maxであれば、 xを担当するサブツリーiにxを挿入し、T.max = xを設定します。T.children [i]が以前は空だった場合は、 iをT.auxにも挿入します。
4. それ以外の場合、T.min< x < T.maxなので、 xを担当するサブツリーiにx を挿入します。T.children[i] が以前は空だった場合は、i をT.auxにも挿入します。

コードでは:

function Insert(T, x)
     if T.min == x || T.max == x then  // x はすでに挿入されています
        return 
    if T.min > T.max then  // T は空です
        T.min = T.max = x;
        
    x < T.minの場合、
        スワップ(x, T.min)
    x > T.maxの場合
        T.max = x
    i = フロア(x / )${\displaystyle {\sqrt {M}}}$
    lo = x mod${\displaystyle {\sqrt {M}}}$
    挿入(T.children[i], lo)
    T.children[i].min == T.children[i].maxの場合
        挿入(T.aux, i)
終わり

この手順の効率性の鍵は、空の vEB ツリーに要素を挿入するのにO (1)時間がかかることです。そのため、アルゴリズムが 2 回の再帰呼び出しを行うことはありますが、これは最初の再帰呼び出しが空のサブツリーに対して行われた場合にのみ発生します。これにより、以前と同じ実行時間の再帰が得られます${\displaystyle T(m)=T(m/2)+O(1)}$。

vEB ツリーからの削除は、最も難しい操作です。vEBツリー T から 値xを削除する呼び出しDelete(T, x)は、次のように動作します。

1. T.min = T.max = xの場合、x はツリーに格納されている唯一の要素であり、ツリーが空であることを示すためにT.min = MおよびT.max = −1を設定します。
2. それ以外の場合、x == T.minであれば、 vEBツリーで2番目に小さい値y を見つけて、現在の場所から削除し、 T.min=yに設定する必要があります。 2番目に小さい値yはT.children[T.aux.min].minなので、 O (1)時間で見つけることができます。 y を含むサブツリーからy を削除します。
3. x≠T.minかつx≠T.maxの場合、 xを含むサブツリーT.children[i]からxを削除します。
4. x == T.maxの場合、 vEBツリーで2番目に大きい値y を見つけて、 T.max=yに設定する必要があります。前の場合と同様に、 x を削除することから始めます。すると、値y はT.minまたはT.children[T.aux.max].maxのいずれかになるため、 O (1)時間で見つけることができます。
5. 上記のいずれの場合でも、任意のサブツリーT.children[i]から最後の要素xまたはy を削除すると、 T.auxからもi が削除されます。

コードでは:

関数Delete(T, x)
     T.min == T.max == xの場合
        T.min = M
        T.max = −1
        
    x == T.minの場合、 
        hi = T.aux.min *を返します。${\displaystyle {\sqrt {M}}}$
        j = T.aux.min
        T.min = x = hi + T.children[j].min
    i = フロア(x / )${\displaystyle {\sqrt {M}}}$
    lo = x mod${\displaystyle {\sqrt {M}}}$
    削除(T.children[i], lo)
    T.children[i]が空の場合
        削除(T.aux, i)
    x == T.maxの場合、
         T.auxが空の場合、
            T.max = T.min
        それ以外の場合、 
            hi = T.aux.max *${\displaystyle {\sqrt {M}}}$
            j = T.aux.max
            T.max = hi + T.children[j].max
終わり

繰り返しになりますが、この手順の効率は、1 つの要素のみを含む vEB ツリーからの削除には定数時間しかかからないという事実にかかっています。特に、2 番目の Delete 呼び出しは、削除前に xがT.children[i]内の唯一の要素であった場合にのみ実行されます。

log mが整数であるという仮定は不要です。演算とを、それぞれxの上位⌈ m /2⌉ビットと下位⌊ m /2⌋ビットのみを取ることに置き換えることができます。既存のマシンでは、これは除算や剰余の計算よりも効率的です。 ${\displaystyle x{\sqrt {M}}}$${\displaystyle x{\bmod {\sqrt {M}}}}$

実際の実装では、特にk シフト命令と最初のゼロ検索命令を備えたマシンでは、ワード サイズ(またはその小さな倍数)に等しいmに達したらビット配列に切り替えることでパフォーマンスをさらに向上できます。1 つのワードに対するすべての操作は一定時間であるため、これは漸近的なパフォーマンスには影響しませんが、ポインター ストレージの大部分といくつかのポインター参照を回避し、このトリックによって時間とスペースを大幅に節約できます。

vEB ツリーの最適化では、空のサブツリーを破棄します。これにより、多くの要素が含まれている場合、vEB ツリーは非常にコンパクトになります。これは、何かを追加する必要が生じるまでサブツリーが作成されないためです。最初に、追加された各要素は、合計で約m /2 個のポインターを含む約log( m ) 個の新しいツリーを作成します。ツリーが大きくなるにつれて、特に大きなサブツリーがますます再利用されます。M個の要素の完全なツリーでは、O( M ) 個のスペースのみが使用されます。さらに、バイナリ検索ツリーとは異なり、このスペースの大部分はデータの格納に使用されます。要素が数十億個であっても、完全な vEB ツリー内のポインターの数は数千個になります。

上記の実装ではポインタを使用し、キーユニバースのサイズに比例して、合計でO ( M ) = O (2 ^m )のスペースを占有します。これは次のように見ることができます。再帰は です。これを解決することで になります。幸いなことに、帰納法によってS ( M ) = M −2であることを示すこともできます。^[4]${\displaystyle S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})}$${\displaystyle S(M)\in (1+{\sqrt {M}})^{\log \log M}+\log \log M\cdot O({\sqrt {M}})}$

vEB ツリーのO ( M )のスペース使用量は、キー全体の大部分が格納されているのでない限り、膨大なオーバーヘッドになります。これが、vEB ツリーが実際には普及していない理由の 1 つです。この制限は、子を格納するために使用される配列を別のデータ構造に変更することで対処できます。1 つの可能性は、レベルごとに固定数のビットのみを使用することです。これにより、トライ が作成されます。または、各配列をハッシュ テーブルに置き換えて、データ構造をランダム化することを犠牲にして、スペースをO ( n log log M ) (ここで、nはデータ構造に格納される要素の数) に削減することもできます。

x-fast 試行と、より複雑なy-fast 試行は、 vEB ツリーと同等の更新時間とクエリ時間を持ち、ランダム化されたハッシュ テーブルを使用して、使用されるスペースを削減します。x-fast 試行はO ( n log M )のスペースを使用し、y-fast 試行はO ( n )のスペースを使用します。

フュージョンツリーは、有限の宇宙上のwビット整数の連想配列を実装する別のタイプのツリーデータ構造です。ワードレベルの並列処理とビット操作技術を使用して、先行/後続クエリと更新にO（log _w n）時間を実現します。ここで、wはワードサイズです。^{[5]フュージョンツリーは}O（n）のスペースを使用し、ハッシュツリーまたは指数ツリーを使用して動的にすることができます。

Isabelle（証明支援システム）には検証済みの実装があります。^[6]機能の正しさと時間制限の両方が証明されています。効率的な命令型の標準MLコードを生成できます。

• 整数ソート
• タンゴの木