暗黙ツリーリスト

conc -tree ^{[ 1 ] [ 2 ]}は、要素シーケンスを格納するデータ構造であり、償却時間O (1) の追加および先頭への追加操作、 O (log n ) の挿入および削除操作、O (log n ) の連結操作を提供します。このデータ構造は、関数型タスク並列およびデータ並列プログラミングに特に適しており、漸近的複雑性が類似する他のデータ構造と比較して実装が比較的簡単です。^{[ 1 ]} Conc-tree は、左から右への逐次反復順序を必要としないデータ並列操作の効率を向上させ、^{[ 3 ]}不要なデータのコピーを回避することでこれらの操作の定数係数を改善するように設計されました。^{[ 2 ]}直交的に、conc-listデータ抽象化の実装として、関数型タスク並列アルゴリズムでデータを効率的に集約するために使用されます。^{[ 4 ]} Conc-list は関数型 cons-listの並列プログラミング版であり、元々はFortress 言語で導入されました。

conc-treeの基本的な操作は連結です。conc-treeは、以下の基本データ型で動作します。

trait Conc [ T ] { def left : Conc [ T ] def right : Conc [ T ] def level : Int def size : Int }case class Empty [ T ] extends Conc [ T ] { def level = 0 def size = 0 }case class Single [ T ]( elem : T ) extends Conc [ T ] { def level = 0 def size = 1 }case class <> [ T ]( left : Conc [ T ], right : Conc [ T ]) extends Conc [ T ] { val level = 1 + math . max ( left . level , right . level ) val size = left . size + right . size }

< >型は内部ノードを表し、関数型リストの:: ( cons型)にヒントを得て、concと発音され、逐次プログラミングに使用されます。

O(log n) の時間で連結を行うには、AVL ツリーで維持される不変条件と同様に、任意の 2 つの兄弟ツリー間のレベル (つまり高さ) の差が 1 以下であることを保証する必要があります。この不変条件により、ツリーの高さ (ルートからいずれかの葉までの最長パスの長さ) は、ツリー内の要素数に対して常に対数的になります。連結は次のように実装されます。

defconcat(xs:Conc[T],ys:Conc[T]){valdiff=ys.level-xs.levelif(math.abs(diff)<=1)new<>(xs,ys)elseif(diff<-1){if(xs.left.level>=xs.right.level){valnr=concat(xs.right,ys)new<>(xs.left,nr)}else{valnrr=concat(xs.right.right,ys)if(nrr.level==xs.level-3){valnr=new<>(xs.right.left,nrr)new<>(xs.left,nr)}else{valnl=new<>(xs.left,xs.right.left)new<>(nl,nrr)}}}else{// symmetric case}}

Amortized O(1) time appends (or prepends) are achieved by introducing a new inner node type called Append, and using it to encode a logarithmic-length list of conc-trees, strictly decreasing in height. Every Append node ap must satisfy the following invariants:

1. ap.left.rightのレベルは常にap.rightのレベルより厳密に大きい。

2. ツリーap.right にはAppendノードが一切含まれません(つまり、正規化された形式で、<>、Single、Emptyのみで構成されています)。

これらの不変条件により、要素の追加は二進数の加算と同型になります。つまり、同じ高さの隣接する2つのツリーは定数時間でリンクでき、桁上げ操作は最大でも対数回数で済みます。次の図は、二進数11に対応するconc-treeに要素が追加されている様子を示しています。

このバイナリ数表現は、岡崎^{[ 5 ]}による純粋関数型ランダムアクセスリストの表現と似ていますが、ランダムアクセスリストではすべての木が完全二分木である必要があるのに対し、conc-treesはより緩やかで、バランスのとれた木のみを必要とします。これらのより緩やかな不変条件により、conc-treesは対数時間連結を維持できますが、ランダムアクセスリストではO ( n )の連結しかできません。

以下は、最悪の場合O (log n )時間、償却時間O (1)となるappendメソッドの実装例です。

case class Append [ T ]( left : Conc [ T ], right : Conc [ T ]) extends Conc [ T ] { val level = 1 + math . max ( left . level , right . level ) val size = left . size + right . size }private def append [ T ]( xs : Append [ T ], ys : Conc [ T ]) = if ( xs . right . level > ys . level ) new Append ( xs , ys ) else { val zs = new <> ( xs . right , ys ) xs . left match { case ws @ Append ( _ , _ ) => append ( ws , zs ) case ws => if ( ws . level <= xs . level ) concat ( ws , zs ) else new Append ( ws , zs ) } } }

このように構築された Conc-tree は、追加ノードがO (log n )個を超えることはなく、正規化された形式 ( <>、単一ノード、および空のノードのみを使用する形式)にO (log n ) 時間で変換できます。

これらの操作の詳細な説明は、オンラインのリソース^{[ 6 ] [ 7 ]}、または元のconc-tree論文^{[ 1 ]}で見つけることができます。これらの基本操作は、すべての操作の定数係数を増やすという代償を伴いながら、O(log n)の連結時間制限を維持しながら、最悪の場合O(1)のdeque操作をサポートするように拡張できることが示されました^{[ 2 ]}。