IntervalTree DeleteNode Javaインプリメンテーション

Question

JavaでIntervalTreeまたはRangeTreeの実装が必要ですが、削除をサポートしているものを見つけるのが難しいです。

あり、内蔵1 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. 
*/ 

が例外をスロー終わる：

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

sun.jvm.hotspot.utilities.IntervalTreeのサブクラスにdelete機能を実装していますか？あるいは、これを既に正しく実装している別のインターバルツリーの実装がありますか？

現在のところ、削除があるたびにツリーを一掃し、理想から離れているだけです（注：RBTreeのDEBUGGING = falseを設定するとすばらしいことになります）。

Answer 1

削除されたノードのセットを維持するようにsun.jvm.hotspot.utilities.IntervalTreeを修正しました。検索を行うときに、このセット内のアイテムを除外します。理想的ではありませんが、これは "本当の"削除作業をするよりもずっと簡単でした。削除したセットが大きすぎると、私はツリーを再構築します。

Answer 2

This projectには、より多くの用途に使用できるRangeTreeの実装があります。太陽のパッケージは素早く汚れても大丈夫かもしれませんが、私はそれらに頼って重要なものを作ることはお勧めしません。 Sunはそれらを安定に保つことはできません。

Answer 3

正確な要件はわかりませんが、非静的なセグメントツリーが役立つかもしれません。その場合はLayout Management SW、具体的にはSegmentTree packageをご覧ください。あなたに必要な削除機能があります。

自分でロールすることを決めた場合は、オープンソーシングをお勧めしますか？オープンで簡単なインターバルツリーは利用できません。

Answer 4

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

Answer 5

私はオープンソースの実装で削除されていますが、完全に機能するように努力しています。

これは、より大きなオープンソースプロジェクトGephiのモジュールですが、ここではsourcesとjavadocです。あなたはGephiをインストールすることができますjarファイルをしたい、それが中にいた場合：

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

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

だから少しの努力で、コードをリファクタリングし、これを持つことができると思います。「特定の間隔を削除する」機能。最も高速で最も汚い方法は、privateメソッド/ Nodeクラスをpublicにすることです。しかし、それはオープンソースプロジェクトなので、将来的にはインターバルツリーのいくつかの良い標準実装に進化する可能性があります。