问题描述
我需要一个 IntervalTree 或Java中的RangeTree实现，并且很难找到一个工作删除支持.
I need an IntervalTree or RangeTree implementation in Java, and am having trouble finding one with working deletion support.
在 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.
*/
尝试从树中删除节点最终会引发异常:
Trying to delete nodes from a tree ends up throwing the exception:
在sun.jvm.hotspot.utilities.IntervalTree的子类中正确实现delete功能有多困难?还是有另一个Interval Tree实现已经正确实现了?
How difficult would it be to properly implement delete functionality in a subclass of the sun.jvm.hotspot.utilities.IntervalTree? Or is there another Interval Tree implementation which already implements this correctly?
当前，我只是清除树并在每次删除时重新填充它，这远非理想(请注意:在RBTree中将DEBUGGING = false设置为极大地加快了速度).
Currently I'm just wiping out the tree and re-populating it every time there's a deletion, which is far from ideal (note: setting DEBUGGING=false in the RBTree sped things up tremendously).
推荐答案
我最终修改了sun.jvm.hotspot.utilities.IntervalTree，以维护一组已删除的节点.进行搜索时，我会排除此集合中的所有项目.这并不理想，但是这比使真正的"删除工作容易得多.一旦删除的集变得太大，我就会重建树.
I ended up modifying the sun.jvm.hotspot.utilities.IntervalTree to maintain a Set of deleted nodes. When doing a search, I exclude any items in this set. Not ideal, but this was a lot easier than getting "real" deletion working. Once the deleted set gets too large, I rebuild the tree.
这篇关于IntervalTree DeleteNode Java实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！