問題タブ [treap]

二分探索木は、順序付けられたデータよりもランダムに選択されたデータから構築する方が速いといつも聞いています。これは、順序付けられたデータでは、ツリーの高さを最小限に保つために明示的な再調整が必要だからです。

最近、私は不変のtrapを実装しました。これは、ランダム化を使用して比較的バランスを保つ特別な種類の二分探索ツリーです。私が予想していたものとは対照的に、順序付けられていないデータよりも順序付けられたデータの方が約 2 倍速く、一般的によりバランスの取れた Treap を一貫して構築できることがわかりました。その理由はわかりません。

これが私の Treap の実装です。

• http://pastebin.com/VAfSJRwZ

そして、ここにテストプログラムがあります：

そして、ランダム挿入時間と順序付き挿入時間をミリ秒単位で比較したグラフを次に示します。

順序付けられた入力を順序付けられていない入力よりも漸近的に高速にするコードは何も見られないため、違いを説明するのに途方に暮れています。

ランダム入力よりも順序付けられた入力からトレプを構築する方がはるかに速いのはなぜですか?

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

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

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

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

PS私の英語が十分に理解できなかったらごめんなさい。

UPD：私が探している構造についてのいくつかの追加の説明。

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

各ノードにサブツリーサイズがある場合、キーを破棄して、treapが順序どおりにトラバーサルされたユーザーデータの配列を表すと想像できます。各要素の配列インデックスは、サブツリーのサイズから簡単に計算できます。これで、配列の途中で要素を追加/削除したり、この配列を分割したりできます-すべてO（log N）時間で。

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

UPD2：これがコードスニペットです-私が見つけた少量の情報の一部です。キリル文字に気付かないでください:)「снеявнымключом」という言葉は、直訳で「暗黙の鍵を使って」を意味します。

関数を再帰的に呼び出し、ノードのルートを左右のサブツリーのパラメーターとして毎回使用することで、バイナリ検索ツリーの高さを簡単に取得できる関数がたくさんあることを知っています。しかし、Treap でパラメーターを取得しない場合でも、int を返す場合はどうすればよいでしょうか。他のメソッドを再帰的に呼び出すことができましたが、これで停止しました。いくつかの助けをいただければ幸いです。

これは私が持っているものですが、私は主にそれが間違っていると信じています

どのバランスの取れた BST が C++ で簡単にコーディングできるかを知りたいのですが、それでも O(logn) とほぼ同じ複雑さがあります。

私はすでに Red Black ツリーを試しましたが、コーディングがより簡単な代替手段が必要です。私は過去にTreapsと仕事をしたことがありますが、パフォーマンスが向上するか、実装がより簡単なオプションを模索することに興味があります.

あなたの提案は何ですか？

どのような状況で、treap を使用するのに最適なデータ構造ですか? 私はこれに関する答えを探していましたが、具体的なものは何も見つかりませんでした。

stackoverflowいつトレプを使用するかを尋ねる別の質問がありますが、実際の例はそこに示されていません。

最も一般的な利点は、たとえば赤黒ツリーよりも実装がはるかに簡単であるように思われますが、ほとんどすべての人がとにかく事前に作成された実装を使用しているため、あまり関係がないようです.