暗黙のキーを備えたTREAP

Question

Treapと呼ばれるデータ構造があります。これは、ランダム化されたバイナリ検索ツリーであり、ランダムに生成されたいわゆる「優先順位」のヒープでもあります。

キーが暗黙的であり、ツリーに保存されていないこの構造にはバリエーションがありますが、ツリー内のノードの順序付けられたインデックスはこのノードのキーと考えています。キーではなく、各ノードにサブツリーのサイズを保存する必要があります。この手法により、TREAPについて何らかのアレイのように考えることができます。これは、O（log n）時間の多くの動作をサポートします。挿入、削除、サブアレイの復帰、間隔の変更などです。

私はこの構造について少し知っていますが、それほど多くはありません。私はそれをグーグルしようとしましたが、Treap自体に関する多くの記事だけを見つけましたが、この「暗黙のTreap」 /「インデックス付きリスト」については何もありませんでした。私の母国語は英語ではないので、私はその名前さえ知りません。私が聴いた講義は、英語の元の用語ではなく、構造のネイティブ用語を使用しました。このネイティブの用語は、「暗黙のキーのTREAP」または「暗黙のキーのデカルトツリー」として英語で直接翻訳できます。

誰かがこの構造についての記事で私を指し示したり、元の名前を教えてもらえますか？ありがとうございました。

私の英語が十分に理解できなかった場合、PS申し訳ありません。

UPD： 私が探している構造についてのいくつかの特別な説明。

ツリーに保存されている実際のユーザーデータであるランダムに選択された優先順位とキーを備えた通常のTREAPを検討してください。次に、すべてのノードに他のユーザー情報が保存されていることを想像してみましょう。キーは検索キーに他なりません。次のステップは、各ノードのサブツリーサイズの計算と維持です。マージ/分割/追加/削除ごとにこのパラメーターを更新する必要がありますが、たとえば、O（log n）のツリーのkth要素を見つけることができます。時間。

各ノードにサブツリーサイズがある場合、キーを捨てて、TreapがInorder Traversalのユーザーデータの配列を表すことを想像できます。各要素の配列インデックスは、サブツリーサイズから簡単に計算できます。これで、配列の中央に要素を追加/削除するか、この配列を分割することができます。すべてO（log n）時間です。

また、「複数の」操作を行うこともできます。たとえば、「配列」のすべての要素に一定の値を追加することもできます。これを実装するには、この操作を遅延させる必要があります。すべてのノードにパラメーターを追加し、このノードのサブアレイのすべての要素に「後で」追加する必要がある遅延定数を表し、変更を下に「プッシュ」する必要があります。必要。サブアレイまたは塗装（マーキング）に定数を追加すると、サブアレイを遅らせることができます。サブアレイを逆にするため（ここでは、「サブアレイを逆にする必要がある」というビットのノードの遅延情報など）などです。

Upd2： これがそうです コードスニペット - 私が見つけた少量の情報の一部。キリル語に気付かないでください:)単語「暗黙のキーを使用した直接翻訳では「もっと翻訳」という単語「「暗黙のキー」」という言葉に気づきます。

Answer 1

このデータ構造は、逆転による署名された順列の並べ替えについて、カプランとヴェルビンによる論文で見つけることができます（7ページ、セクション3.1）： http://www.math.jussieu.fr/~fouquet/enseignement/projets/kaplan.pdf.

Answer 2

TREAPSの重要なアイデア（しゃれは意図していません！）は、ランダム化されたキーを使用することです。キーを削除した場合、どのようにしてTREAPを持つことができるかわかりません。だから、おそらくあなたの質問を誤解しました。または、おそらくあなたはTREAPSの代替案について言及しています、 ランダム化されたバイナリ検索ツリー. 。どちらのデータ構造でも、（病理学的なケースの代わりに）ツリーが平均的なツリーのように見えることを確認することで、平均ケースの複雑さを達成できるのと同じアイデアを使用しています。

TREAPSを使用すると、ランダムな優先順位とバランスを使用してこれを行います。

ランダム化されたバイナリツリーを使用すると、ランダム性は構造中にのみ含まれています。つまり、ツリーTにノードを挿入すると、確率1/（サイズ（t） + 1）がルートになり、サイズ（t）があります。 tのノードの数です。そしてもちろん、ノードがルートに挿入されていない場合、追加されるまで再帰的に続行します。 （これらの木の詳細な研究については、私のC.マルティネスの記事を参照してください。）

このデータ構造は、TREAPとまったく同じように動作しますが、キーを必要としない別のメカニズムを使用します。

これがあなたが探していたものではない場合、おそらくあなたはいくつかの追加情報を共有できます。あなたの講師はこの構造に取り組んだかもしれない人に言及しましたか？それはそうではないように思えるかもしれませんが、あなたの母国語を知ることは、一般的にそれを発生した特定の国にアルゴリズム/データ構造をペグダウンすることができるので、重要な手がかりになる可能性があります。

Answer 3

多分あなたはを探しています ロープ （複雑な形式の文字列）遅延操作のニーズに合わせて変更されました。興味深いことは、ロープに関する未解決の質問があるということです いまここで.

Answer 4

そのデータ構造には、2つの直交概念の組み合わせであるため、そのデータ構造には名前はないと思います。このような暗黙のキーを使用して、ほぼ自己バランスの取れたツリーデータ構造を使用できます。

スケープゴートの木を見てみたいと思うかもしれません。なぜなら、スケープゴートの木はすでにリバランスのためにサブツリーサイズを使用しており、ノードごとのオーバーヘッドを必要としないからです。