16

CLR の赤黒間隔ツリーに似た間隔ツリー アルゴリズムを探していますが、既定で間隔のマージをサポートしているため、間隔が重複することはありません。

つまり、2 つの間隔 [2,3] と [5,6] を含むツリーがあり、間隔 [4,4] を追加すると、結果は 1 つの間隔 [2,6] のみを含むツリーになります。

ありがとう

更新: 私が検討しているユース ケースは、推移閉包の計算です。間隔セットは、非常にコンパクトであることがわかっているため、後続セットを格納するために使用されます。しかし、間隔セットをリンクされたリストとして表すと、状況によっては間隔セットが非常に大きくなり、挿入ポイントを見つけるのに必要な時間がかかることがわかりました。したがって、インターバルツリーに興味があります。また、1 つのツリーを別のツリーとマージする (つまり、セット OR 操作) ことが非常に多い場合があります。両方のツリーが大きい場合は、各間隔の挿入を繰り返すよりも、両方のツリーの順序どおりのウォークを使用して新しいツリーを作成する方がよい場合があります。

4

1 に答える 1

4

私が見ている問題は、大きな間隔を挿入すると、ツリーの大部分が消去され、赤黒の不変条件を回復するのが難しくなることです。

次のように、スプレイツリーを使用する方が簡単だと思います。簡単にするために、各ツリーには 2 つのセンチネル (A他のすべての間隔の左側の間隔とZ右側の間隔) が含まれています。interval を挿入するときは、ツリーのルートにIsplayIの先行オブジェクトを表示します。H木は次のように見えます

   H
  / \
...  X
    / \
  ... ...

Xここで、Iの後継者を切り離しJてルートに展開します。

   H       J
  /       / \
...     ... ...

この時点で、オーバーラップする間隔はすべてIのJ左側のサブツリーにあります。そのサブツリーを切り離し、そのすべてのノードをフリー リストに入れ、I必要に応じて拡張します。andIの親にHするJ

     I
    / \
   H   J
  /     \
...     ...

楽しい道を進みましょう。この操作は O(log n) 償却されます。ここで、n はツリー ノードの数です (これは、スプレイ ツリー ポテンシャル関数を調べて、多くの代数を実行することで証明できます)。

1 つのツリーのルートを挿入し、左右のサブツリーをマージすることにより、自然な再帰的なツリーからツリーへのマージがあることを付け加えておきます。私はそれをオフハンドで分析する方法がわかりません。

于 2010-04-09T15:39:12.633 に答える