7

JavaでIntervalTreeまたはRangeTreeの実装が必要ですが、削除サポートが機能しているものを見つけるのに問題があります。

sun.jvm.hotspot.utilities.IntervalTreeに組み込みのものがありますが、RBTreeスーパークラスのdeleteNodeメソッドは次のように述べています。

/**
 * FIXME: this does not work properly yet for augmented red-black
 * trees since it doesn't update nodes. Need to figure out exactly
 * from which points we need to propagate updates upwards.
 */

ツリーからノードを削除しようとすると、例外がスローされます。

ノードの最大エンドポイントが正しく更新されませんでした

deletesun.jvm.hotspot.utilities.IntervalTreeのサブクラスに機能を適切に実装することはどれほど難しいでしょうか。または、これをすでに正しく実装している別の区間木実装はありますか？

現在、私はツリーを一掃し、削除があるたびに再入力しています。これは理想からはほど遠いです（注：RBTreeでDEBUGGING = falseを設定すると、処理が大幅に高速化されます）。

4

5 に答える 5

5

sun.jvm.hotspot.utilities.IntervalTree削除されたノードのセットを維持するようにを変更することになりました。検索を行うときは、このセットのアイテムを除外します。理想的ではありませんが、これは「実際の」削除を機能させるよりもはるかに簡単でした。削除したセットが大きくなりすぎたら、ツリーを再構築します。

于 2009-10-01T14:43:21.543 に答える
1

このプロジェクトには、より役立つ可能性のあるRangeTree実装があります。Sunパッケージは、すぐに汚い使用でも問題ないかもしれませんが、それらに依存して重要なものを構築することはお勧めしません。太陽はそれらを安定させないかもしれません。

于 2009-09-13T18:55:32.970 に答える
0

削除されたオープンソースの実装を見つけましたが、完全に機能させるにはある程度の努力が必要です。

これは、より大きなオープンソースプロジェクトGephiのモジュールですが、ここにソースとjavadocがあります。jarが必要な場合は、Gephiをインストールできます。次の場所にあります。

/gephi/modules/org-gephi-data-attributes-api.jar

そこでのdeleteメソッドは、（入力間隔だけでなく）入力間隔と重複するすべての間隔を削除します。ただし、ソースで、特定のノード（1つの間隔を格納する）を削除するプライベートメソッドがあることがわかりました。また、プライベート検索メソッドはノードを返します。

したがって、少しの努力でコードをリファクタリングして、「特定の間隔を削除する」機能を使用できると思います。最も速くて汚い方法は、プライベートメソッド/ノードクラスをパブリックにすることです。しかし、これはオープンソースプロジェクトであるため、将来的には区間木の優れた標準実装に進化する可能性があります。

于 2012-08-11T19:12:51.393 に答える
0

正確な要件はわかりませんが、非静的セグメントツリーが機能する可能性があります。その場合は、Layout Management SW、特にSegmentTreeパッケージをご覧ください。必要な削除機能があります。

あなたがあなた自身を転がすことを決心するならば、私はそれをオープンソーシングすることを提案することができますか？オープンで簡単な区間木がまだ利用できないことに驚いています。

于 2009-09-14T12:43:35.873 に答える
0

拡張AVLツリーに基づくac＃実装があります@http://code.google.com/p/intervaltree/。Javaへの翻訳はそれほど難しくないはずです。

于 2012-07-24T23:43:06.280 に答える