トレアップ

コンピュータサイエンスにおいて、ツリーとランダム化二分探索木は、順序付けられたキーの動的なセットを維持し、キー間の二分探索を可能にする、密接に関連した2つの二分探索木データ構造です。キーの挿入と削除のシーケンスの後、木の形状はランダム二分木と同じ確率分布を持つ確率変数になります。特に、高い確率でその高さはキーの数の対数に比例するため、各検索、挿入、または削除操作の実行には対数時間かかります。

説明

ツリーは、1989 年にRaimund SeidelとCecilia R. Aragonによって初めて記述されました。 ^{[ 1 ]}^{[ 2 ]}その名前は、treeとheapの合成語です。これは、各キーに (ランダムに選択された) 数値優先度が割り当てられたデカルト木です。任意の二分探索木と同様に、ノードの順序走査は、キーのソート順と同じです。木の構造は、ヒープ順序付けされているという要件によって決定されます。つまり、葉以外のノードの優先度番号は、その子の優先度以上でなければなりません。したがって、より一般的なデカルト木と同様に、ルートノードは最大優先度のノードであり、その左および右のサブツリーは、そのノードの左および右へのソート順のサブシーケンスから同じ方法で形成されます。

トレアプを説明する同等の方法は、優先順位が最も高いノードをリバランスせずに二分探索木に挿入することによって形成される、というものです。したがって、優先順位が独立した乱数（2つのノードが同じ優先順位を持つ可能性が非常に低いことを保証できる、十分な大きさの優先順位の分布から得られる）である場合、トレアプの形状は、ランダムに選択された挿入順序でリバランスせずにノードを挿入することによって形成される探索木であるランダム二分探索木の形状と同じ確率分布を持ちます。ランダム二分探索木は高い確率で対数的な高さを持つことが知られているため、トレアプについても同様です。これは、クイックソートが期待値で実行されるという二分探索木の議論を反映しています。 $O(n\log n)$ 時間。二分探索木がソートの動的問題バージョンの解であるとすれば、Treapsは特に、優先順位がピボットの選択を導く動的クイックソートに対応します。

Aragon and Seidel also suggest assigning higher priorities to frequently accessed nodes, for instance by a process that, on each access, chooses a random number and replaces the priority of the node with that number if it is higher than the previous priority. This modification would cause the tree to lose its random shape; instead, frequently accessed nodes would be more likely to be near the root of the tree, causing searches for them to be faster.

Naor and Nissim^[3] describe an application in maintaining authorization certificates in public-key cryptosystems.

Operations

Basic operations

Treaps support the following basic operations:

To search for a given key value, apply a standard binary search algorithm in a binary search tree, ignoring the priorities.
To insert a new key x into the treap, generate a random priority y for x. Binary search for x in the tree, and create a new node at the leaf position where the binary search determines a node for x should exist. Then, as long as x is not the root of the tree and has a larger priority number than its parent z, perform a tree rotation that reverses the parent-child relation between x and z.
To delete a node x from the treap, if x is a leaf of the tree, simply remove it. If x has a single child z, remove x from the tree and make z be the child of the parent of x (or make z the root of the tree if x had no parent). Finally, if x has two children, swap its position in the tree with the position of its immediate successor z in the sorted order, resulting in one of the previous cases. In this final case, the swap may violate the heap-ordering property for z, so additional rotations may need to be performed to restore this property.

Building a treap

To build a treap we can simply insert n values in the treap where each takes $O(\log n)$ time. Therefore a treap can be built in $O(n\log n)$ time from a list values.

Bulk operations

In addition to the single-element insert, delete and lookup operations, several fast "bulk" operations have been defined on treaps: union, intersection and set difference. These rely on two helper operations, split and join.

トレアプを、キーxより小さいトレアプとキーxより大きいトレアプの 2 つに分割するには、トレアプ内のどのノードよりも高い優先度（最大優先度）でx をトレアプに挿入します。この挿入後、 xはトレアプのルートノードとなり、 xより小さい値はすべて左サブトレアプに、 xより大きい値はすべて右サブトレアプに格納されます。この操作にかかるコストは、トレアプへの 1 回の挿入と同じです。
以前の分割によって生成された 2 つの treap を結合する場合、最初の treap の最大値が 2 番目の treap の最小値よりも小さいと安全に仮定できます。値xを持つ新しいノードを作成します。xは最初の treap の最大値よりも大きく、2 番目の treap の最小値よりも小さく、最小優先度を割り当て、その左の子を最初のヒープに、右の子を 2 番目のヒープに設定します。必要に応じて回転して、ヒープの順序を修正します。その後、それはリーフノードとなり、簡単に削除できます。結果として、2 つの元の treap からマージされた 1 つの treap が得られます。これは実質的に分割を「取り消す」ことであり、コストは同じです。より一般的には、結合操作は 2 つの treap と任意の優先度 (つまり、最高優先度である必要はありません) を持つキーに対して実行できます。

{\displaystyle T_{1}} — トレアプスで行われた参加 $T_{1}$ そして $T_{2}$ 右の子供 $T_{1}$ 結合は、以前の右子の結合として定義され、 $T_{2}$ 。

結合アルゴリズムは以下のとおりです。

function join(L, k, R) if prior(k, k(L)) and prior(k, k(R)) return Node(L, k, R) if prior(k(L), k(R)) return Node(left(L), k(L), join(right(L), k, R)) return Node(join(L, k, left(R)), k(R), right(R))

{\displaystyle T} — 分割する $T$ による $x$ 再帰的な分割呼び出しは、左または右の子に対して行われます。 $T$ 。

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

function split(T, k) if (T = nil) return (nil, false, nil) (L, (m, c), R) = expose(T) (k = m)の場合、(L, true, R) を返します。 (k < m)の場合、 (L', b, R') = split(L, k) (k > m)の場合、(L', b, join(R', m, R)) を返します。 (L', b, R') = split(R, k) return (join(L, m, L'), b, R'))

$集合A$ と $B$ を表す2 つのトレアプ $t 1$ と $t 2$ の和集合は、 $A$ $\cup$ $B$ を表すトレアプ $t$ です。次の再帰アルゴリズムは、この和集合を計算します。

function union(t ₁ , t ₂ ): if t ₁ = nil: return t ₂if t ₂ = nil: return t ₁if priority(t ₁ ) < priority(t ₂ ): swap t ₁ and t ₂ t _< , t _> ← split t ₂ on key(t ₁ ) return join(union(left(t ₁ ), t _< ), key(t ₁ ), union(right(t ₁ ), t _> ))

ここでは、split関数は2つのツリーを返すものと想定されています。1つは入力キーより小さいキーを保持するツリー、もう1つは入力キーより大きいキーを保持するツリーです。（このアルゴリズムは非破壊的ですが、インプレース破壊型のバージョンも存在します。）

交差のアルゴリズムも同様ですが、結合ヘルパールーチンが必要です。和集合、交差、差集合のそれぞれの計算量は、サイズが $m$ と $n$ のトリープに対して $O (m log (⁠ n / m ⁠ + 1))$ であり、 $m$ $\leq$ $n$ です。さらに、和集合への再帰呼び出しは互いに独立しているため、並列に実行できます。^[⁴^]

Split と Union は Join を呼び出しますが、treaps のバランス基準を直接処理しません。このような実装は通常「結合ベース」の実装と呼ばれます。

キーのハッシュ値を優先順位として使用し、構造的に等しいノードを構築時にマージする場合、マージされた各ノードはキーセットの一意の表現となります。特定のキーセットを表すルートノードは同時に1つしか存在できないため、2つのキーセットはポインタ比較によって等価性をテストできます。この比較は時間的に一定です。

この手法を用いることで、2つのセット間の差が小さい場合でも、マージアルゴリズムの高速性を向上させることができます。入力セットが等しい場合、和集合関数と積集合関数はすぐに処理を中断し、いずれかの入力セットを結果として返しますが、差集合関数は空集合を返す必要があります。

$d$ を対称差のサイズとする。修正されたマージアルゴリズムもO $(d log ⁠ n / d ⁠) で$ 制限される。^{[ 5 ]}^{[ 6 ]}

ランダム化二分探索木

マルティネスとロウラがアラゴンとセイデルのツリーに関する研究に続いて導入したランダム化二分探索木^{[ 7 ]}は、同じランダム分布の木の形状を持つ同じノードを格納しますが、ランダム化された構造を維持するために木のノード内に異なる情報を保持します。

ランダムな優先順位を各ノードに格納する代わりに、ランダム化二分探索木は各ノードに小さな整数、つまり子孫の数（自身を 1 と数える）を格納します。これらの数値は、回転ごとに一定の追加時間だけで、木の回転操作中に維持できます。既にn個のノードを持つ木にキーxを挿入する場合、挿入アルゴリズムは確率 1/( n + 1)でxを木の新しいルートとして配置することを選択し、そうでない場合は、挿入手順を再帰的に呼び出して、左または右のサブツリー内にxを挿入します(キーがルートより小さいか大きいかによって異なります)。子孫の数は、アルゴリズムによって各ステップでのランダムな選択に必要な確率を計算するために使用されます。サブツリーのルートにxを配置するには、treap のように葉に挿入してから上方向に回転させるか、Martínez と Roura によって記述された代替アルゴリズムを使用してサブツリーを 2 つの部分に分割し、新しいノードの左と右の子として使用するかのいずれかを実行できます。

ランダム化二分探索木の削除手順では、挿入手順と同じノードごとの情報を使用しますが、挿入手順とは異なり、削除されたノードの左と右の子から派生する2つのサブツリーを1つのツリーに結合するために必要なランダムな決定回数は平均でO(1)回だけです。これは、結合されるサブツリーの平均深さがΘ(log n)であるためです。サイズがnとmの2つのツリーを結合するには、平均でΘ(log(n+m))回のランダムな選択が必要です。削除されるノードの左または右のサブツリーが空の場合、結合操作は自明です。そうでない場合は、削除されたノードの左または右の子が、その子孫の数に比例する確率で新しいサブツリーのルートとして選択され、結合は再帰的に進行します。

比較

ランダム化二分木では、ノードごとに格納される情報はトレアプよりも単純ですが（高精度の乱数ではなく小さな整数）、乱数生成器への呼び出し回数は多く（挿入または削除ごとに O(log n ) 回の呼び出し、挿入ごとに 1 回の呼び出し）、ノードごとの子孫数を更新する必要があるため、挿入手順はやや複雑になります。技術的な違いとしては、トレアプでは衝突（2 つのキーが同じ優先順位になる）が発生する可能性がわずかにあります。また、どちらの場合も、真の乱数生成器と、デジタルコンピュータで一般的に使用される擬似乱数生成器との間には統計的な違いが生じます。しかし、いずれの場合も、アルゴリズムの設計に使用される完全なランダム選択の理論モデルと実際の乱数生成器の機能との差は極めて小さいです。

ツリーとランダム化二分探索木はどちらも、更新ごとにツリーの形状がランダムに分布するという点では同じですが、挿入と削除操作のシーケンスでこれら2つのデータ構造によって実行されるツリーの変更履歴は異なる場合があります。たとえば、ツリーでは、1、2、3の3つの数値が1、3、2の順に挿入され、その後数値2が削除された場合、残りの2つのノードは、中央の数値が挿入される前と同じ親子関係を持ちます。ランダム化二分探索木では、削除後のツリーは、中央の数値が挿入される前のツリーの形状に関係なく、2つのノード上の2つの可能なツリーのいずれかになる可能性が等しくなります。

暗黙の報酬

暗黙の treap ^{[ 8 ]}は、通常の treap の単純な変形であり、次の操作をサポートする動的配列と見なすことができます。 $O(\log n)$ :

任意の位置に要素を挿入する
任意の位置から要素を削除する
指定された範囲内の要素の合計、最小値、最大値を求める。
さらに、特定の範囲での塗装
指定された範囲内の要素を反転する

暗黙的なtreapの背後にある考え方は、配列インデックスをキーとして使用するが、それを明示的に保存しないことである。そうしないと、更新（挿入/削除）によってキーが変更されることになる。 $O(n)$ ツリーのノード。

ノード T のキー値（暗黙のキー）は、そのノードより小さいノードの数に 1 を加えた数です。なお、このようなノードは、T が P の右部分木に含まれる場合、T の左部分木だけでなく、T の祖先 P の左部分木にも存在し得ます。

したがって、ツリーを下っていく際にすべてのノードの合計を累積することで、操作を実行する際に現在のノードの暗黙のキーを素早く計算できます。この合計は左サブツリーを訪問しても変化しませんが、増加します。 $cnt(T\rightarrow L)+1$ 適切なサブツリーを訪れるとき。

次の定義を考えてみましょう。

import std ;class ImplicitTreap { private : int key ; int prior ; ImplicitTreap * left ; ImplicitTreap * right ; public : explicit ImplicitTreap ( int key = 0 , int prior = std :: rand ()) : key { key }, prior { std :: rand ()}, left { nullptr }, right { nullptr } {}// ゲッターint count () const ; void updateCount (); void join ( ImplicitTreap * left , ImplicitTreap * right ); void split ( ImplicitTreap *& left , ImplicitTreap *& right ; int key , int add = 0 ); };

暗黙のtreapの結合アルゴリズムは次のとおりです。^{[ 8 ]}

void ImplicitTreap::join ( ImplicitTreap * left , ImplicitTreap * right ) { if ( ! left || ! right ) { this = left ? left : right ; } else if ( left -> getPrior () > right -> getPrior ()) { left -> getRight (). join ( left -> getRight , right ); this = left ; } else { right -> getLeft (). join ( left , right -> getLeft ()); this = right ; } updateCount (); }

暗黙のtreapの分割アルゴリズムは次のとおりです。^{[ 8 ]}

void ImplicitTreap::split ( ImplicitTreap *& left , ImplicitTreap *& right , int key , int add = 0 ) { int currentKey = add + this -> left . count (); //暗黙のキーif ( key <= currentKey ) { this -> left . split ( left , this -> left , key , add ); right = this ; } else { this -> right . split ( this -> right , right , key , add + 1 + this -> left . count ()); left = this ; } updateCount (); }

業務

要素を挿入する

位置posに要素を挿入するには、split関数を呼び出して配列を[0...pos-1]と[pos..sz]の 2 つのサブセクションに分割し、2 つのツリーを取得します。 $T1$ そして $T2$ .次にマージします $T1$ join関数を呼び出すことで新しいノードと結合します。最後に、join 関数を呼び出してマージします。 $T1$ そして $T2$ 。

要素を削除

削除対象の要素を見つけ、その子要素であるLとRに対して結合操作を実行します。次に、削除対象の要素を、結合操作によって得られたツリーに置き換えます。

指定された範囲内で合計、最小値、または最大値を求めます。

この計算を行うには、以下の手順で進めます。

まず、そのノードが表す範囲のターゲット関数の値を格納するための追加フィールドFを作成します。次に、ノードのLとRの子ノードの値に基づいて値Fを計算する関数を作成します。このターゲット関数は、ツリーを変更するすべての関数（分割と結合）の最後に呼び出します。
次に、指定された範囲 [A..B] のクエリを処理する必要があります。sのsplit関数を 2 回呼び出し、treap を分割します。 $T1$ 含まれる $\{1..A-1\}$ 、 $T2$ 含まれる $\{A..B\}$ 、そして $T3$ 含まれる $\{B+1..n\}$ クエリへの回答後、結合関数を2回呼び出して元のtreapを復元します。

指定された範囲での追加/塗装

この操作を実行するには、以下の手順で進めます。

サブツリーに追加された値を格納するフィールドDを新たに作成します。この変更をノードから子ノードに伝播するために使用する関数pushを作成します。ツリーを変更するすべての関数（ splitとjoinなど）の先頭でこの関数を呼び出すことで、ツリーに変更が加えられた後も情報が失われないようにします。

指定された範囲内で反転する

特定のノードのサブツリーを各ノードごとに反転させる必要があることを示すために、追加のブール型フィールドRを作成し、その値をtrueに設定します。この変更を反映させるために、ノードの子ノードを入れ替え、すべての子ノードのRをtrueに設定します。

参考文献

↑ Aragon, Cecilia R.; Seidel, Raimund (1989)、「ランダム化探索木」(PDF)、第30回コンピュータサイエンス基礎に関する年次シンポジウム、ワシントンDC：IEEEコンピュータソサエティプレス、pp. 540–545、doi：10.1109/SFCS.1989.63531、ISBN 0-8186-1982-1
↑ Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees" , Algorithmica , 16 (4/5): 464–497 , doi : 10.1007/BF01940876
↑ Naor, M. ; Nissim, K. (2000年4月)、「証明書の失効と証明書の更新」(PDF)、IEEE Journal on Selected Areas in Communications、18 (4): 561–570、doi : 10.1109/49.839932、S2CID 13833836 。
↑ Blelloch, Guy E.; Reid-Miller, Margaret (1998)、「treaps を用いた高速集合演算」、第 10 回 ACM 並列アルゴリズムおよびアーキテクチャに関するシンポジウム - SPAA '98 議事録、ニューヨーク州ニューヨーク、米国: ACM、pp. 16–26、doi : 10.1145/277651.277660、ISBN 0-89791-989-0S2CID 7342709 。
↑ Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）
↑ GitHub上のConfluent Sets and Maps
↑ Martínez, Conrado; Roura, Salvador (1997)、「ランダム化二分探索木」、Journal of the ACM、45 (2): 288–323、doi : 10.1145/274787.274812、S2CID 714621
1 2 3 "Treap - 競争プログラミングアルゴリズム" . cp-algorithms.com . 2021-11-21に取得.

外部リンク

セシリア・アラゴンによるトレアプに関する参考文献と情報のコレクション
オープンデータ構造 - セクション 7.2 - Treap: ランダム化二分探索木、Pat Morin
アニメーション化されたトリープは、 2005年3月15日にWayback Machineにアーカイブされました。
ランダム化二分探索木。イリノイ大学アーバナ・シャンペーン校のジェフ・エリクソンによる講義ノート。タイトルとは裏腹に、内容は主にトレアプとスキップリストに関するもので、ランダム化二分探索木についてはごく簡単に触れているだけである。
Junyi Sunによるtreapベースの高性能キーバリューストア
VB6 による treaps の実装。COM オブジェクトとしての Visual Basic 6 による treaps の実装。
ActionScript3によるtreapの実装
純粋なPythonとCythonによるインメモリtreapとduptreap
C# の Treats。ロイ・クレモンズ著
純粋なGoのインメモリ、不変のトレップス
純粋なGo言語による永続的なtreapキーバリューストレージライブラリ

[paper89-1] Aragon, Cecilia R.; Seidel, Raimund (1989)、「ランダム化探索木」(PDF)、第30回コンピュータサイエンス基礎に関する年次シンポジウム、ワシントンDC：IEEEコンピュータソサエティプレス、pp. 540–545、doi：10.1109/SFCS.1989.63531、ISBN 0-8186-1982-1

[paper96-2] Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees" , Algorithmica , 16 (4/5): 464–497 , doi : 10.1007/BF01940876

[3] Naor, M. ; Nissim, K. (2000年4月)、「証明書の失効と証明書の更新」(PDF)、IEEE Journal on Selected Areas in Communications、18 (4): 561–570、doi : 10.1109/49.839932、S2CID 13833836 。

[4] Blelloch, Guy E.; Reid-Miller, Margaret (1998)、「treaps を用いた高速集合演算」、第 10 回 ACM 並列アルゴリズムおよびアーキテクチャに関するシンポジウム - SPAA '98 議事録、ニューヨーク州ニューヨーク、米国: ACM、pp. 16–26、doi : 10.1145/277651.277660、ISBN 0-89791-989-0S2CID 7342709 。

[5] Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）

[Confluent_Sets_and_Maps-6] GitHub上のConfluent Sets and Maps

[7] Martínez, Conrado; Roura, Salvador (1997)、「ランダム化二分探索木」、Journal of the ACM、45 (2): 288–323、doi : 10.1145/274787.274812、S2CID 714621

[:0-8] 1 2 3 "Treap - 競争プログラミングアルゴリズム" . cp-algorithms.com . 2021-11-21に取得.

[ 1 ]

[ 2 ]

[3]

[

[ 5 ]

[ 6 ]

[ 7 ]