2

私が Web で見たほとんどの例では、ランダムな (異なる!) 優先順位を生成するある種の外部乱数ジェネレーターがあると見なされています。

私が覚えていることから、優先順位を実際にランダムに生成し、それらをトレプに挿入して、可能な優先順位の衝突を解き放つ方法がありました。

では、2 つの質問があります。

  1. Treap は実際にすべての優先度を個別に持つ必要がありますか、それとも最終的に比較される可能性のあるノードの優先度のみを持つ必要がありますか? つまり、優先度のある 2 つのノードがあり、pそれらが決して接触しないことを確認できる場合、それらに同じ優先度を持たせることに問題はありますか?
  2. Treap で優先順位を生成および解除するにはどうすればよいですか?

ありがとう

編集：これが私が話していることの説明です：

問題 8.12 @ランダム化されたアルゴリズム

次に、treap の操作を実装するために必要なランダム ビットの数を分析してみましょう。単位間隔 [0,1] から各優先度 Pi を一様にランダムに選択するとします。次に、各 Pi のバイナリ表現は、偏りのないコイン投げの結果である (潜在的に無限の) ビット シーケンスとして生成できます。アイデアは、異なる優先度間の比較を解決するために必要な数のビットのみをこのシーケンスで生成することです。ツリー T 内の要素の優先順位のバイナリ表現のプレフィックスをいくつか生成しただけだとします。ここで、項目 y を挿入しながら、その優先順位 Py を他の優先順位と比較して、y をどのようにローテーションするかを決定します。PyをいくつかのPIと比較しながら。現在の部分バイナリ表現で比較を解決できる場合は、完了です。さもないと。それらは同じ部分バイナリ表現を持ち、最初に異なるまで、それぞれに対してより多くのビットを生成し続けます。

4

2 に答える 2

1

  1. 正確性に影響を与えることなく、優先順位を使用して好きなことを行うことができます。これは依然として、すべての下にある二分探索ツリーです。O(log n) 漸近境界を犠牲にすることなく、実行時間分析をやり直して、優先度衝突の小さな確率を処理することは可能です (ただし、より複雑です)。

  2. Python での比較演算子は次のようになります。最初の優先順位は[]、空のリストであり、説明されているように、ビットは遅延して埋められます。ビットのリストを使用しています。より効率的にするには、それらをより大きな整数型にパックするのが賢明です。

    import random

def less(lst1, lst2):
    j = 0
    while True:
        if j >= len(lst1):
            lst1.append(random.randrange(2))  # random bit
        if j >= len(lst2):
            lst2.append(random.randrange(2))
        if lst1[j] != lst2[j]:
            return lst1[j] < lst2[j]
        j += 1
于 2015-04-28T03:44:58.713 に答える