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

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

結合操作は、同じバランス方式の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 ₂を持つ新しいノードを作成します。t _1がt ₂よりも重いと仮定します（この「重い」はバランス調整スキームによって異なります）。他のケースは対称です。join はt ₁の右スパインに沿って、t ₂とバランスの取れたノードcに到達するまで進みます。この時点で、左の子ノード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{expose}}(v)}$ノードの左の子、キー、右の子をタプルに抽出します。 ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,k,r)}$
• ${\displaystyle {\text{Node}}(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 = T'.right.right.color = red T'.right.right.color := 黒 rotateLeft(T') を返す、そうでない場合は T'を返す関数joinLeftRB(T L , k, T R ) /* joinRightRB と対称 */ĥ( T L ) > ĥ( T R )の場合、関数join( T L , k, 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{expose}}(v)}$ノードの左の子、キー、色、右の子をタプルに抽出します。 ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,\langle k,c\rangle ,r)}$
• ⁠ ⁠ は ${\displaystyle {\text{Node}}(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 ) 、 w(T L ) = α w(T R ) の場合、 Node(T L , k, T R ) を返し、そうでない場合は 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{expose}}(v)}$ノードの左の子、キー、右の子をタプルに抽出します。 ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,k,r)}$
• ${\displaystyle {\text{Node}}(l,k,r)}$左の子、キー、右の子を持つノードを作成します。 ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$

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

以下では、はノード の左の子、キー、右の子 をタプル に抽出します。は、左の子、キー、右の子を持つノードを作成します。 " " は、2 つのステートメントとを並列に実行できることを意味します。 ${\displaystyle {\text{expose}}(v)}$ ${\displaystyle l}$ ${\displaystyle k}$ ${\displaystyle r}$ ${\displaystyle v}$ ${\displaystyle (l,k,r)}$ ${\displaystyle {\text{Node}}(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) 、 if (T = nil) return (nil, false, nil) else (L, m, R) := 公開(T) k < mの場合 (L', b, R') := 分割(L, k) (L', b, join(R', m, R)) を返す。そうでない場合はk > m とする。 (L', b, R') := split(R, k) (join(L, m, L'), b, R') を返す。そうでない場合は (L, true, R)を返す。

参加2

この関数は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) := splitLast(L) join(L', k, R)を返す

料金はサイズ の木に対するものです。 ${\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を返すelse (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' = difference(l 1 , t < ) || r' = difference(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' := sort(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]

注記

参考文献

1. Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016)、「並列順序付きセットのためのJust Join」、並列アルゴリズムとアーキテクチャに関するシンポジウム、第28回ACMシンポジウム並列アルゴリズムとアーキテクチャ (SPAA 2016)講演論文集、ACM、pp.  253– 264、arXiv : 1602.02120、doi :10.1145/2935764.2935768、ISBN 978-1-4503-4210-0
2. Tarjan, Robert Endre (1983)、「データ構造とネットワークアルゴリズム」、データ構造とネットワークアルゴリズム、Siam、pp.  45– 56
3. スレイター、ダニエル・ドミニク、タージャン、ロバート・エンドレ（1985年）「自己調整型二分探索木」、Journal of the ACM、サイアム
4. Adams, Stephen (1992)、「関数型言語における集合の効率的な実装」、関数型言語における集合の効率的な実装、Citeseer、CiteSeerX 10.1.1.501.8427 。
5. Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018)、「PAM: 並列拡張マップ」、第23回ACM SIGPLAN並列プログラミングの原理と実践シンポジウム論文集、ACM、pp.  290– 304

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Join-based_tree_algorithms&oldid=1219527022"