結合ベースのツリーアルゴリズム

コンピュータサイエンスにおいて、結合ベースのツリーアルゴリズムは、自己バランス型二分探索木のためのアルゴリズムの一種です。このフレームワークは、さまざまなバランス型二分探索木のための高度に並列化されたアルゴリズムを設計することを目的としています。アルゴリズムのフレームワークは、単一の操作joinに基づいています。^[1]このフレームワークでは、結合操作は、さまざまなバランス調整スキームのすべてのバランス調整基準をキャプチャし、他のすべての関数join は、さまざまなバランス調整スキームにわたって汎用的に実装されています。結合ベースのアルゴリズムは、少なくとも 4 つのバランス調整スキーム、AVL ツリー、赤黒ツリー、重みバランスツリー、およびtreapに適用できます。

結合操作は、同じバランス方式の 2 つの二分バランス木と、キー を入力として受け取り、 の順序どおりの走査がの順序どおりの走査、次にの順序どおりの走査となる新しい二分バランス木を出力します。特に、木が検索木である場合、つまり木の順序がキーの完全順序付けを維持する場合、 のすべてのキーが より小さく、 のすべてのキーが より大きいという条件を満たす必要があります。 ${\displaystyle (L,k,R)}$${\displaystyle L}$${\displaystyle R}$${\displaystyle k}$${\displaystyle t}$${\displaystyle L}$${\displaystyle k}$${\displaystyle R}$${\displaystyle L}$${\displaystyle k}$${\displaystyle R}$${\displaystyle k}$

結合演算は、最初にTarjan ^{[2]によって}赤黒木に対して定義され、最悪の場合でも対数時間で実行されます。その後、Sleator と Tarjan ^[3]は、散布木に対して償却対数時間で実行される結合アルゴリズムを説明しました。その後、Adams ^[4]は結合を重みバランス木に拡張し、和集合、積集合、差集合などの高速な集合集合関数 に使用しました。1998 年、Blelloch と Reid-Miller は結合 をtreapsに拡張し、サイズ と の 2 つの木に対して集合関数の境界が となり、比較モデルで最適であることを証明しました。彼らはまた、分割統治方式 を使用して Adams のアルゴリズムに並列性をもたらしました。2016 年、Blelloch ら は結合ベースのアルゴリズムを正式に提案し、AVL 木、赤黒木、重みバランス木、treaps の4 つの異なるバランス方式に対して結合アルゴリズムを形式化しました。同じ研究で、彼らは、和集合、積集合、差集合に関するアダムスのアルゴリズムが、4 つのバランス調整スキームすべてにおいて作業最適であることを証明しました。 ${\displaystyle O(m\log(1+{\tfrac {n}{m}}))}$${\displaystyle m}$${\displaystyle n(\geq m)}$

関数join はツリーの再バランスを考慮しているため、入力バランス スキームに依存します。2 つのツリーのバランスが取れている場合、join は単に左サブツリーt ₁、ルートk、右サブツリーt _{2を持つ新しいノードを作成します。} t _1がt ₂よりも重い (この「重い」はバランス スキームによって異なります)と仮定します(他のケースは対称です)。join はt ₂とバランスが取れているノードcまでt ₁の右スパインをたどります。この時点で、左の子c、ルートk、右の子t ₂を持つ新しいノードが作成され、c が置き換えられます。新しいノードによってバランス不変条件が無効になる場合があります。これは回転によって修正できます。 ${\displaystyle (t_{1},k,t_{2})}$

以下は、さまざまなバランス調整スキームでの 結合アルゴリズムです。

AVLツリーの結合アルゴリズム:

関数joinRightAVL(T L , k, T R )h(c) ≤ h(T R ) + 1の場合、 
    (l, k', c) := expose(T L )
    
        T' := Node(c, k, T R )
         h(T') ≤ h(l) + 1 の
            場合はNode(l, k', T')
        を返し、それ以外の場合は
            rotateLeft(Node(l, k', rotateRight(T')))
    を返します。それ以外の場合は 
        T' := joinRightAVL(c, k, T R )
        T : = Node(l, k', T')
         h(T') ≤ h(l) + 1
            の場合はTを
        返し、それ以外の場合は
            rotateLeft(T)を返す

関数joinLeftAVL(T L , k, T R )
    /* joinRightAVL と対称 */

関数join(T L , k, T R )
     h(T L ) > h(T R ) + 1
        の場合、 joinRightAVL(T L , k, T R )
    を返し、そうでない場合はh(T L ) > h(T L ) + 1 の
        場合、 joinLeftAVL(T L , k, T R )
    を返し、そうでない場合はNode(T L , k, T R )
を返します。
        

どこ：

• ${\displaystyle h(v)}$ノードの高さです。${\displaystyle v}$
• ${\displaystyle {\text{露出する}}(v)}$ノードの左の子、キー、右の子をタプルに抽出します。${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$${\displaystyle v}$${\displaystyle (l,k,r)}$
• ${\displaystyle {\text{ノード}}(l,k,r)}$左の子、キー、右の子を持つノードを作成します。${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$

赤黒木の結合アルゴリズム:

関数joinRightRB(T L , k, T R )
     、 T L .color = blackかつĥ(T L ) = ĥ(T R )
        の場合、 Node(T L , ⟨k, red⟩, T R )
    を返し、そうでない場合は 
        (L', ⟨k', c'⟩, R') := expose(T L )
        T' := Node(L', ⟨k', c'⟩, joinRightRB(R', k, T R ))
         、 c' = blackかつT'.right.right.color = redの場合
            T'.right.right.color := 黒
            rotateLeft(T')
        を返す、そうで
            なければT' を返す

関数joinLeftRB(T L , k, T R )
    /* joinRightRB と対称 */

関数join(T L , k, T R )
     if ĥ(T L ) > ĥ(T R )
        T' := joinRightRB(T L , k, T R )
         (T'.color = red)かつ(T'.right.color = red)の場合
            T'.色:=黒
        ĥ(T R ) > ĥ(T L )の場合はT' を
    返す
        /* 対称 */
    そうでない場合、 T L .color = blackかつT R = black
        の場合はNode(T L , ⟨k, red⟩, T R )
    を返し、そうでない場合はNode(T L , ⟨k, black⟩, T R )
を返します。
        

どこ：

• ⁠ ⁠ は${\displaystyle {\hat {h}}(v)}$ノードの黒の高さです。${\displaystyle v}$
• ${\displaystyle {\text{露出する}}(v)}$ノードの左の子、キー、色、右の子をタプルに抽出します。${\displaystyle l}$${\displaystyle k}$${\displaystyle c}$${\displaystyle r}$${\displaystyle v}$${\displaystyle (l,\langle k,c\rangle ,r)}$
• ⁠ ⁠ は${\displaystyle {\text{ノード}}(l,\langle k,c\rangle ,r)}$、左の子、キー、色、右の子を持つノードを作成します。${\displaystyle l}$${\displaystyle k}$${\displaystyle c}$${\displaystyle r}$

重みバランスのとれたツリーの結合アルゴリズム:

関数joinRightWB(T L , k, T R )
    (l, k', c) := expose(T L )
     if w(T L ) = α w(T R )
         return Node(T L , k, T R )
     else  
        T' := joinRightWB(c, k, T R )
        (l 1 , k 1 , r 1 ) := expose(T')
         w(l) = α w(T')
            の場合、 Node(l, k', T')
        を返します。そうでない場合、 w(l) = α w(l 1 )かつw(l)+w(l 1 ) = α w(r 1 )
            の場合、 rotateLeft(Node(l, k', T'))
        を返します。そうでない場合、 rotateLeft(Node(l, k', rotateRight(T'))を返します。
            

関数joinLeftWB(T L , k, T R )
    /* joinRightWB と対称 */

関数join(T L , k, T R )
     、 w(T L ) > α w(T R )
        の場合はjoinRightWB(T L , k, T R )
    を返し、そうでない場合はw(T L ) > α w(T L )
        の場合はjoinLeftWB(T L , k, T R )
    を返し、そうでない場合はNode(T L , k, T R )
を返します。
        

どこ：

• ${\displaystyle w(v)}$ノードの重みです。${\displaystyle v}$
• ${\displaystyle w_{1}=_{\alpha }w_{2}}$重みを意味し、α重みバランスが取られています。${\displaystyle w_{1}}$${\displaystyle w_{2}}$
• ${\displaystyle w_{1}>_{\alpha }w_{2}}$α-重量バランスに関して、重量が重量より重いことを意味します。${\displaystyle w_{1}}$${\displaystyle w_{2}}$
• ${\displaystyle {\text{露出する}}(v)}$ノードの左の子、キー、右の子をタプルに抽出します。${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$${\displaystyle v}$${\displaystyle (l,k,r)}$
• ${\displaystyle {\text{ノード}}(l,k,r)}$左の子、キー、右の子を持つノードを作成します。${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$

以下では、はノード の左の子、キー、右の子をタプル に抽出します。左の子、キー、右の子を持つノードを作成します。" " は、2 つのステートメントとが並列に実行できること を意味します。${\displaystyle {\text{露出する}}(v)}$${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$${\displaystyle v}$${\displaystyle (l,k,r)}$${\displaystyle {\text{ノード}}(l,k,r)}$${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$${\displaystyle s_{1}||s_{2}}$${\displaystyle s_{1}}$${\displaystyle s_{2}}$

ツリーを、キーxより小さいツリーとキーxより大きいツリーの 2 つに分割するには、まずツリーにx を挿入してルートからのパスを描画します。この挿入後、 xより小さいすべての値はパスの左側に、xより大きいすべての値は右側に見つかります。Join を適用すると、パス上のキーを下から上への中間ノードとして使用して左側のすべてのサブツリーがボトムアップでマージされ、左側のツリーが形成され、右側の部分は非対称になります。一部のアプリケーションでは、Split はx がツリーに出現するかどうかを示すブール値も返します。 Splitのコストは、ツリーの高さのオーダー です。${\displaystyle O(\log n)}$

分割アルゴリズムは次のとおりです。

関数split(T, k)
    の場合(T = nil)、
        戻り値(nil, false, nil)
    それ以外の場合
        (L, m, R) := 公開(T)
        k < mの場合
            (L', b, R') := 分割(L, k)
            (L', b, join(R', m, R))
        を返す。そうでない場合はk > mである。
            (L', b, R') := 分割(R, k)
            (join(L, m, L'), b, R')
        を返す。そうでない場合は
            (L, true, R)
を返す。

この関数はjoinと同様に定義されますが、中間のキーはありません。最初に左のツリーの最後のキーを分割し、次に左のツリーの残りの部分を右のツリーと結合します。アルゴリズムは次のとおりです。 ${\displaystyle k}$${\displaystyle k}$

関数splitLast(T)
    (L, k, R) := 公開(T)
    R = nil
        の場合(L, k)
    を返し、そうでない場合は
        (T', k') := splitLast(R)
        戻り値(join(L, k, T'), k')

関数join2(L, R)
     L = nil
        の場合R
    を返し、そうでない場合は
        (L', k) := 分割最終(L)
        join(L', k, R)
を返す

料金はサイズの木 1 本あたりの料金です。 ${\displaystyle O(\log n)}$${\displaystyle n}$

挿入および削除アルゴリズムは、結合を使用する場合、バランス調整スキームとは独立して実行できます。挿入の場合、アルゴリズムは挿入するキーをルートのキーと比較し、キーがルートのキーより小さい/大きい場合は左/右のサブツリーに挿入し、2 つのサブツリーをルートに結合します。削除の場合、削除するキーをルートのキーと比較します。等しい場合は、2 つのサブツリーで join2 を返します。等しくない場合は、対応するサブツリーからキーを削除し、2 つのサブツリーをルートに結合します。アルゴリズムは次のとおりです。

関数insert(T, k)
     T = nil
        の場合、 Node(nil, k, nil)
    を返します。
        (L, k', R) := 公開(T)
        k < k'
            の場合はjoin(insert(L,k), k', R)
        を返し、そうでない場合はk > k' の
            場合はjoin(L, k', insert(R, k)) を
        返し、そうでない場合は
            Tを返します。

関数delete(T, k)
     T = nil
        の場合nil
    を返し、そうでない場合は
        (L, k', R) := 公開(T)
        k < k' の
            場合はjoin(delete(L, k), k', R)
        を返し、そうでない場合はk > k' の
            場合はjoin(L, k', delete(R, k))
        を返し、そうでない場合は
            join2(L, R)
を返します。

挿入と削除の両方に時間がかかります。 ${\displaystyle O(\log n)}$${\displaystyle |T|=n}$

重みバランスの取れた木には、和集合、積集合、差集合といういくつかの集合演算が定義されています。集合AとB を表す2 つの重みバランスの取れた木t ₁とt _{2の和集合は、} A ∪ B を表す木tです。次の再帰関数は、この和集合を計算します。

関数union(t 1 , t 2 )
     t 1 = nil
        の場合t 2を返し、そうでない場合はt 2 = nil
        の場合t 1を返し、そうでない場合は
        (l 1 , k 1 , r 1 ) := expose(t 1 )
    
    
        (t < , b, t > ) := split(t 2 , k 1 )
        l' := union(l 1 , t < ) || r' := union(r 1 , t > )
        戻り値 join(l', k 1 , r')

同様に、交差と差集合のアルゴリズムは次のとおりです。

関数intersection(t 1 , t 2 )
     t 1 = nilまたはt 2 = nil
        の場合はnil
    を返し、そうでない場合は
        (l 1 , k 1 , r 1 ) := expose(t 1 )
        (t < , b, t > ) = 分割(t 2 , k 1 )
        l' := 交差点(l 1 , t < ) || r' := 交差点(r 1 , t > )
         bの
            場合はjoin(l', k 1 , r')
        を返し、そうでない場合はjoin2(l', r')を返します
            

関数difference(t 1 , t 2 )
     t 1 = nil
         の場合はnil
    を返し、そうでない場合はt 2 = nilの
         場合はt 1を返し、そうでない場合は
        (l 1 , k 1 , r 1 ) := expose(t 1 )
    
        (t < , b, t > ) := split(t 2 , k 1 )
        l' = 差(l 1 , t < ) || r' = 差(r 1 , t > )
         b
            の場合はjoin2(l', r')
        を返し、そうでない
            場合はjoin(l', k 1 , r')
を返します

和集合、積集合、差集合のそれぞれの計算量は、サイズがとの 2 つの重みバランスの取れた木に対してです。この計算量は、比較回数の点では最適です。さらに重要なのは、和集合、積集合、差集合への再帰呼び出しは互いに独立しているため、並列深度で並列実行できることです。^[1]のとき、結合ベースの実装では、大きい方の木のルートを使用して小さい方の木を分割する場合、単一要素の挿入または削除と同じ計算が適用されます。 ${\displaystyle O\left(m\log \left({\tfrac {n}{m}}+1\right)\right)}$${\displaystyle m}$${\displaystyle n(\geq m)}$ ${\displaystyle O(\log m\log n)}$${\displaystyle m=1}$

ツリーを構築するためのアルゴリズムでは、結合アルゴリズムを利用し、分割統治方式を使用できます。

function build(A[], n)
     if n = 0
         return nil
     else if n = 1
         return Node(nil, A[0], nil)
     else
        l' := build(A, n/2) || r' := (A+n/2, nn/2)
        ユニオン(L, R)
を返す

このアルゴリズムは作業コストが高く、深みがあります。より効率的なアルゴリズムでは、並列ソート アルゴリズムを使用します。 ${\displaystyle O(n\log n)}$${\displaystyle O(\log ^{3}n)}$

function buildSorted(A[], n)
     if n = 0
         return nil
     else if n = 1
         return Node(nil, A[0], nil)
     else
        l' := build(A, n/2) || r' := (A+n/2+1, nn/2-1)
        join(l', A[n/2], r')を返す

関数build(A[], n)
    A' := ソート(A, n)
    buildSorted(A, n)
を返す

このアルゴリズムは、ソート アルゴリズムに作業と深さがあると仮定すると、作業コストと深さを持ちます。 ${\displaystyle O(n\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(\log n)}$

この関数は、述語 を満たすツリー内のすべてのエントリを選択し、選択されたすべてのエントリを含むツリーを返します。 2 つのサブツリーを再帰的にフィルタリングし、ルートが を満たす場合はそれらをルートと結合し、そうでない場合は2 つのサブツリー を join2 します。${\displaystyle p}$${\displaystyle p}$

関数filter(T, p)
     T = nil
        の場合nil
    を返し、そうでない場合は
        (l, k, r) := 公開(T)
        l' := フィルター(l, p) || r' := フィルター(r, p)
        p(k)
            の場合はjoin(l', k, r')
        を返し、それ以外の場合は
            join2(l', R)
を返します。

このアルゴリズムは、コストが一定であると仮定して、サイズ のツリーに対して作業と深さのコストがかかります。 ${\displaystyle O(n)}$${\displaystyle O(\log ^{2}n)}$${\displaystyle n}$${\displaystyle p}$

結合ベースのアルゴリズムは、Hackage、SML/NJ、PAMなどのライブラリのセット、マップ、拡張マップ ^[5]のサポートインターフェースに適用されています。^[5]

• PAM、並列拡張マップライブラリ
• Hackage、Hackage のコンテナ