IntervalTree DeleteNode Java实现
我需要在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. */ 尝试从树中删除节点最终会抛出exception：
节点的最大端点未正确更新
在sun.jvm.hotspot.utilities.IntervalTree的子类中正确实现deletefunction有多难？ 或者是否有另一个Interval Tree实现已经正确实现了这个？
目前我只是在擦除树并在每次删除时重新填充它，这远非理想（注意：在RBTree中设置DEBUGGING = false会大大加快）。
我最终修改了sun.jvm.hotspot.utilities.IntervalTree以维护一组已删除的节点。 在进行搜索时，我会排除此集合中的所有项目。 不理想，但这比“真正的”删除工作容易得多。 一旦删除的集合变得太大，我就重建了树。
该项目有一个RangeTree实现，可能对您有用。 太阳包可能适合快速和肮脏的使用，但我不建议建立任何重要的依赖它们。 太阳可能无法保持稳定。
我不知道您的确切要求，但非静态段树可能适合您。 如果是这样，请查看布局管理SW ，特别是SegmentTree包 。 它具有您需要的删除function。
如果你决定推销自己的，我可以建议开源吗？ 我很惊讶没有一个开放的，简单的Interval Tree可用。
有一个基于增强AVL树的ac＃实现@ http://code.google.com/p/intervaltree/ 。 翻译成java应该不会太难。
我找到了一个带删除的开源实现，但需要付出一些努力才能使其完全正常运行。
它是较大的开源项目Gephi的一个模块，但这里有源 代码和javadoc 。 如果你想要一个jar子，你可以安装Gephi，它在：
/gephi/modules/org-gephi-data-attributes-api.jar
删除方法，删除与输入间隔重叠的所有间隔（而不仅仅是输入间隔）。 但是我在soruces中发现有私有方法删除特定节点（存储一个间隔）。 私有搜索方法也返回节点。
所以我认为通过一些小小的努力，可以重构代码并具有 – “删除特定间隔”function。 最快和最脏的方法是将私有方法/ Node类公开。 但由于它是一个开源项目，也许它可能在未来发展为区间树的一些良好的标准实现。