IntervalTree DeleteNode Java実装

Question

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

に組み込みのものがありますsun.jvm.hotspot.utilities.IntervalTree 、ただし 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.
 */

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

  

ノードの最大エンドポイントは更新されませんでした   適切に

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

現在、削除するたびにツリーを一掃し、再配置するだけです。これは理想とはほど遠いです（注：RBTreeでDEBUGGING = falseを設定すると、物事が大幅に高速化されます）。

Answer 1

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

Answer 2

このプロジェクトには、より有用なRangeTree実装があります。 sunパッケージは手っ取り早く使用しても大丈夫かもしれませんが、それらに依存する重要なものをビルドすることはお勧めしません。 Sunはそれらを安定させない場合があります。

Answer 3

私はあなたの正確な要件を知りませんが、非静的セグメントツリーがあなたのために働くかもしれません。その場合は、レイアウト管理ソフトウェア、特に SegmentTreeパッケージ。必要な削除機能があります。

自分でロールバックすることに決めた場合、オープンソース化することをお勧めしますか？オープンで簡単なインターバルツリーがまだ用意されていないことに驚いています。

Answer 4

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

Answer 5

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

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

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

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

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