トレップ

トレップ
タイプ	ランダム二分探索木
ビッグ O 記法による時間計算量 手術 平均 最悪の場合 検索 O (log n ) の上）​ 入れる O (log n ) の上）​ 消去 O (log n ) の上）​ 空間の複雑さ 空間 の上）​ の上）​

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

ツリーは、1989 年にRaimund SeidelとCecilia R. Aragonによって初めて説明されました。 ^{[1] [2]}その名前はtreeとheapを組み合わせた造語です。これは、各キーに (ランダムに選択された) 数値の優先度が与えられたデカルト木です。他の二分探索木と同様に、ノードのインオーダー走査順序はキーのソート順序と同じです。ツリーの構造は、ヒープ順序であるという要件によって決定されます。つまり、リーフ ノード以外のすべての優先度番号は、その子ノードの優先度以上である必要があります。したがって、より一般的なデカルト木と同様に、ルート ノードが最大優先度のノードであり、その左と右のサブツリーは、そのノードの左と右のソート順序の部分列から同じ方法で形成されます。

treap を説明する同等の方法は、再バランス調整を行わずに、ノードを優先度の高い順にバイナリ検索木に挿入することによって形成できることです。したがって、優先度が独立した乱数 (2 つのノードが同じ優先度を持つ可能性が非常に低いことを保証する、十分に大きな可能な優先度の空間にわたる分布から) である場合、treap の形状は、ランダム バイナリ検索木 (ランダムに選択された挿入順序で再バランス調整を行わずにノードを挿入することによって形成される検索木) の形状と同じ確率分布を持ちます。ランダム バイナリ検索木は高い確率で対数高さを持つことが知られているため、treap についても同じことが言えます。これは、クイックソートが期待時間内に実行されるというバイナリ検索木の議論を反映しています。バイナリ検索木がソートの動的問題バージョンに対するソリューションである場合、Treap は、優先度がピボット選択をガイドする動的クイックソートに具体的に対応します。 ${\displaystyle O(n\log n)}$

アラゴン氏とザイデル氏は、頻繁にアクセスされるノードに高い優先順位を割り当てることも提案しています。たとえば、アクセスのたびにランダムな数字を選択し、その数字が以前の優先順位よりも高い場合は、その数字でノードの優先順位を置き換えるというプロセスです。この変更により、ツリーのランダムな形状が失われ、頻繁にアクセスされるノードがツリーのルートの近くにある可能性が高くなり、それらの検索が高速化されます。

NaorとNissim ^[3]は、公開鍵暗号システムにおける認証証明書の維持管理への応用について説明しています。

Treaps は次の基本操作をサポートします。

• 特定のキー値を検索するには、優先順位を無視して、バイナリ検索ツリーで標準のバイナリ検索アルゴリズムを適用します。
• 新しいキーx をツリーに挿入するには、xのランダムな優先度y を生成します。ツリー内でxをバイナリ検索し、バイナリ検索によってxのノードが存在するはずであると判断されたリーフの位置に新しいノードを作成します。次に、 x がツリーのルートではなく、その親zよりも優先度番号が大きい限り、xとzの親子関係を逆にするツリー回転を実行します。
• ツリーからノードx を削除するには、 x がツリーのリーフである場合は、単にそれを削除します。xに 1 つの子zがある場合は、ツリーからx を削除し、 z をxの親の子にします(または、xに親がない場合は、 z をツリーのルートにします)。最後に、 xに 2 つの子がある場合は、ツリー内の位置を、ソート順で直後の後続ノードzの位置と交換します。結果は、前のケースのいずれかになります。この最後のケースでは、交換によってzのヒープ順序プロパティが違反する可能性があるため、このプロパティを復元するには追加の回転を実行する必要がある場合があります。

• treap を構築するには、それぞれに時間がかかる n 個の値を treap に挿入するだけです。したがって、リスト値から時間内に treap を構築できます。${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$

単一要素の挿入、削除、および検索操作に加えて、いくつかの高速な「一括」操作が treaps で定義されています: union、intersection、set Difference 。これらは、 splitとjoin という2 つのヘルパー操作に依存します。

• treap を 2 つの小さな treap (キーxより小さい treapとキーxより大きい treap ) に分割するには、最大優先度 (treap 内のどのノードよりも優先度が高い) でx をtreap に挿入します。この挿入後、 x はtreap のルート ノードになり、xより小さいすべての値は左のサブ treap に、 xより大きいすべての値は右のサブ treap にそれぞれ格納されます。このコストは、treap への 1 回の挿入と同じになります。
• 以前の分割の結果である 2 つの treap を結合する場合、最初の treap の最大値は 2 番目の treap の最小値よりも小さいと想定しても問題ありません。値xを持つ新しいノードを作成します。このxは最初の treap の最大値よりも大きく、2 番目の treap の最小値よりも小さく、最小の優先度を割り当ててから、その左の子を最初のヒープに、右の子を 2 番目のヒープに設定します。ヒープの順序を修正するために、必要に応じてローテーションします。その後、それはリーフ ノードになり、簡単に削除できます。結果は、元の 2 つの treap から結合された 1 つの treap になります。これは、分割を事実上「元に戻す」ことであり、コストは同じです。より一般的には、結合操作は、2 つの treap と任意の優先度 (つまり、最高である必要はない) のキーで実行できます。

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

関数join(L, k, R)
     、prior(k, k(L))かつprior(k, k(R))の場合、 Node(L, k, R)
    を返します。prior(k(L), k(R))の場合、 Node(left(L), k(L), join(right(L), k, R))
    を返します。Node (join(L, k, left(R)), k(R), right(R)) を
返します。

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

関数split(T, k) が
    (T = nil)の場合、 (nil, false, nil)を返します。
    (L, (m, c), R) = 露出(T)
    (k = m)の場合、 (L, true, R)
    を返します(k < m)の場合、
        (L', b, R') = 分割(L, k)
        (k > m)の場合、 (L', b, join(R', m, R))
    を返します。
        (L', b, R') = 分割(R, k)
        戻り値(join(L, m, L'), b, R'))

集合AとBを表す2 つのトレップt ₁とt _{2の和集合は、} A ∪ B を表すトレップtです。次の再帰アルゴリズムは、この和集合を計算します。

関数union(t 1 , t 2 ):
     t 1 = nil
        の場合: t 2を返すt 2 = nil の
        場合: t 1を返すpriority(t 1 ) < priority(t 2 ):
         t 1と t 2 を入れ替える
    t < , t > ← t 2 をkey(t 1 )
    で分割するjoin(union(left(t 1 ), t < ), key(t 1 ),を返す
    
    
                    結合(右(t 1 )、t > ))

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

交差のアルゴリズムも同様ですが、結合ヘルパールーチンが必要です。和集合、交差、差集合のそれぞれの複雑さはO ( m log ⁠ん/メートル⁠）は、サイズがmとnのtreapsに対して実行され、 m≤nである。さらに、unionへの再帰呼び出しは互いに独立しているため、並列に実行することができる。 ^[4]

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

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

この手法は、2 つのセットの差が小さい場合にも、マージ アルゴリズムを高速に実行できるように強化するために使用できます。入力セットが等しい場合、和集合関数と積集合関数は、結果として入力セットの 1 つを返すことですぐに中断する可能性がありますが、差集合関数は空のセットを返す必要があります。

対称差の大きさをdとします。修正されたマージアルゴリズムもO ( d log ⁠ん/d⁠）。 ^{[5] [6]}

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

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

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

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

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

暗黙のtreap ^{[8] [信頼できない情報源? ] は}通常のtreapの単純なバリエーションであり、次の操作をサポートする動的配列として見ることができます。 ${\displaystyle O(\log n)}$

• 任意の位置に要素を挿入する
• 任意の位置から要素を削除する
• 指定された範囲内で合計、最小、または最大要素を見つけます。
• 加算、指定された範囲のペイント
• 指定された範囲内の要素を反転する

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

ノード T のキー値 (暗黙のキー)は、そのノードより少ないノードの数に 1 を加えた数です。T が P の右サブツリーにある場合、このようなノードは、その左サブツリーだけでなく、その祖先 P の左サブツリーにも存在する可能性があることに注意してください。

したがって、ツリーを下っていきながらすべてのノードの合計を累積することで操作を実行すると、現在のノードの暗黙的なキーをすばやく計算できます。この合計は、左のサブツリーにアクセスしたときには変化しませんが、右のサブツリーにアクセスしたときには増加することに注意してください。 ${\displaystyle cnt(T\rightarrow L)+1}$

暗黙的な treap の結合アルゴリズムは次のとおりです。

void join ( pitem & t 、pitem l 、pitem r ) {         
    もし( ! l || ! r )   
        t = l ? l : r ;      
    そうでない場合( l -> prior > r -> prior )    
        結合( l -> r 、l -> r 、r )、t = l ;       
    それ以外
        結合( r -> l 、l 、r -> l )、t = r ;       
    upd_cnt ( t ); 
}

^[8] 暗黙のtreapの分割アルゴリズムは以下の通りである。

void分割( pitem t 、pitem & l 、pitem & r 、intキー、int追加= 0 ) {                
    もし( ! t ) 
        voidを返します( l = r = 0 );       
    int cur_key = add + cnt ( t -> l ); //暗黙のキー      
    (キー<= cur_key )の場合   
        分割( t -> l 、l 、t -> l 、キー、追加)、r = t ;         
    それ以外
        split ( t -> r 、t -> r 、r 、key 、add + 1 + cnt ( t -> l ))、l = t ;             
    upd_cnt ( t ); 
}

^[8]

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

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

この計算を実行するには、次のように進めます。

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

この操作を実行するには、次の手順に従います。

• サブツリーに追加された値を格納する追加のフィールド D を作成します。ノードからその子にこの変更を伝播するために使用される関数pushを作成します。ツリーを変更するすべての関数 (つまり、split と join)の最初にこの関数を呼び出します。これにより、ツリーに変更が加えられた後でも情報が失われることはありません。

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

• 合計、最小値、最大値のセグメントツリー。Wikipediaのセグメントツリーは計算幾何学に関するもので、合計などの要求はフェンウィックツリーで記述されますが、これは暗黙のツリーであり、途中の挿入や削除には対応していません。暗黙のツリーが不可能な場合は、セグメントツリーと呼ばれる明示的なツリーが使用されますが、Wikipediaには適切なページがありません。
• インデックス用の順序統計ツリー。これは、すべてのノードで「1」を合計するように設計されたセグメントツリーのようなものです。

• 指で探す

ウィキメディア・コモンズには、 Treapに関連するメディアがあります。

• セシリア・アラゴンによるトリップの参考資料と情報のコレクション
• オープン データ構造 - セクション 7.2 - Treap: ランダム化バイナリ検索ツリー、Pat Morin
• アニメーションのトリップ
• ランダム化バイナリ検索ツリー。UIUC の Jeff Erickson によるコースの講義ノート。タイトルにもかかわらず、これは主にトリップとスキップ リストに関するもので、ランダム化バイナリ検索ツリーについては簡単に触れられているだけです。
• Junyi Sun による treap に基づく高性能キーバリューストア
• treaps の VB6 実装。COM オブジェクトとしての treaps の Visual Basic 6 実装。
• ActionScript3によるトリップの実装
• 純粋な Python と Cython のインメモリ treap と duptreap
• C# での Treaps。Roy Clemmons 著
• 純粋なGoインメモリ、不変のトラップ
• 純粋な Go 永続 treap キー値ストレージ ライブラリ