3

どんな助けでもいただければ幸いです。

4

2 に答える 2

2

線形時間で任意の2つの並べ替えられたリストを交差させることができます。

  • 両方のAVLツリーの順序どおり（左の子、次に親データ、次に右の子）のイテレーターを取得します。
  • 両方のイテレータの先頭をのぞきます。
    • 1つのイテレータが使い果たされた場合は、結果セットを返します。
    • 両方の要素が等しいか、和集合が計算されている場合は、それらの最小値を結果セットに追加します。
    • 最も低い（イテレータが昇順の場合）要素をポップします。両方が等しい場合は、両方をポップします

これはO（n1 + n2）で実行され、（出力サイズによって制限される）ユニオン操作に最適です。

または、小さいツリーのすべての要素を調べて、大きいツリーに存在するかどうかを確認することもできます。これはO（n1 log n2）で実行されます。

これは、GoogleがBigTableエンジンで交差点を見つけるために使用する（または使用を検討している）アルゴリズムです。

  • すべてのソースのイテレータを取得する
  • ピボット=nullで開始
  • n個のイテレータのいずれかが使い果たされるまで、すべてのイテレータを順番にループします。
    • このイテレータでピボットよりも大きい最小の要素を見つけます。
    • 要素がピボットの場合
      • ピボットが含まれるイテレータの数をインクリメントします
      • このピボットがすべてのイテレータにある場合は、ピボットを結果セットに追加します。
    • そうしないと
      • ピボットが含まれるイテレータの数をリセットします
      • 見つかった要素を新しいピボットとして使用します。

二分木イテレータで要素または次に大きい要素を見つけるには、次のようにします。

  • 現在の要素から開始
  • 現在の要素が検索対象の要素よりも大きくなるか、ルートに入るまで上に移動します
  • 要素が見つかるまで、または左に行けなくなるまで歩きます
  • 現在の要素が検索対象の要素よりも小さい場合は、nullを返します（このイテレータは使い果たされています）
  • それ以外の場合は、現在の要素を返します

これは、完全に混合された同様のサイズのセットの場合はO（n1 + n2）に減衰し、2番目のツリーがはるかに大きい場合はO（n1 log n2）に減衰します。1つのツリーのサブツリーの範囲が、他のツリー/他のすべてのツリーのノードと交差しない場合、このサブツリーの最大1つの要素がアクセスされます（最小）。これはおそらく利用可能な最速のアルゴリズムです。

于 2012-11-21T10:05:20.880 に答える
0

これは、AVLツリー（またはその他の種類のツリー、およびその他の操作）の共通部分と和集合を見つけるための効率的なアルゴリズムを備えた論文です。

関数型言語で効率的にセットを実装する

このテーマを研究しているときにこの論文を見つけました。アルゴリズムはHaskellにあり、主に不変のツリー用に設計されていますが、どの種類のツリーでも同様に機能します（ただし、一部の言語ではオーバーヘッドが発生する可能性があります）。それらのパフォーマンス保証は、上記のアルゴリズムと同様です。

于 2013-12-02T20:23:05.007 に答える