トレップを使用する場合

Question

データを保存する最良の方法がトレップである場合は誰でも本当の例を提供できますか？

トレップがヒープやツリー構造よりも優れている状況を理解したいと思います。

可能であれば、実際の状況からいくつかの例を挙げてください。

ここでは、トレップを使用してグーグルで検索してみましたが、何も見つかりませんでした。

ありがとうございます。

Answer 1

実際の例はありません。しかし、私はプログラミングコンテストでいくつかの問題を解決するためにtreapsを使用してください：

• http://poj.org/problem?id=2761
• http://poj.org/problem?id=3481

これらは、実際に本物の問題ではありませんが、彼らは意味をなさない。

Answer 2

これをツリーベースのマップ実装として使用できます。アプリケーションによっては、fasterになる可能性があります。数年前、私はTreapとSkipのリストを自分で（Javaで）楽しいために実装し、TreeMapと比較していくつかの基本的なベンチマークを行い、Treapが最も速かった。結果はhereです。

たとえば、Red-Blackツリーと比較して実装が非常に簡単です。しかし、私が覚えている限り、Red-Blackツリーと比較して、そのオペレーション（探索はO（log n）であり、確率はhigh）で保証されているわけではありません。特定の時間制限が必要な安全性が重要なアプリケーションで使用します。

Answer 3

トレップは、バランスのとれたバイナリ検索ツリーの変種です。バイナリツリーのバランスを取るためのアルゴリズムはたくさんありますが、その大半は扱う特別なケースがたくさんある恐ろしいものです。一方、Treapsのコード作成は非常に簡単です。ランダム性を利用して、対数の高さが予想されるBBTがあります。 treapsをしている使用して解決する いくつかの良い問題 - http://www.spoj.com/problems/QMAX3VN/（イージーレベル） http://www.spoj.com/problems/GSS6/（中等度のレベル）

Answer 4

ハッシュ値が優先順位として使用されている場合は、treapsは、コンテンツのユニークな表現を提供します。

AVLツリーまたはrbツリーとして実装された項目の順序セットを考えてみましょう。異なる注文のアイテムを挿入すると、通常、異なる形状のツリーになります（ただし、すべてがバランスしています）。与えられたコンテンツについて、トレパルは歴史にかかわらず常に同じ形になるでしょう。

1. セキュリティ上の理由：

   私はユニークな表現が役に立つかもしれませんなぜのための2つの理由を見てきました。トレップには履歴に関する情報を入れることはできません。

2. 効率的なサブツリーの共有。私が見たセット操作のための最も速いアルゴリズムは、トレップを使用します。