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 功能有多难？或者是否有另一个Interval Tree实现已经正确实现了这个？

目前我只是在擦除树并在每次删除时重新填充它，这远非理想（注意：在RBTree中设置DEBUGGING = false会大大加快速度）。

Answer 1

我最终修改了 sun.jvm.hotspot.utilities.IntervalTree 来维护一组已删除的节点。在进行搜索时，我会排除此集合中的所有项目。不理想，但这比获得“真实”要容易得多。删除工作。一旦删除的集合变得太大，我就会重建树。

Answer 2

此项目有一个RangeTree实现，可能对您有用。太阳包可能适合快速和肮脏的使用，但我不建议建立任何重要的依赖它们。太阳可能无法保持稳定。

Answer 3

我不知道您的确切要求，但非静态段树可能适合您。如果是这样，请查看布局管理软件，特别是 SegmentTree包。它具有您需要的删除功能。

如果您决定推销自己，我可以建议开源吗？我很惊讶没有一个开放且简单的Interval Tree可用。

Answer 4

基于增强的AVL树的ac＃实现@ http://code.google.com/ p / intervaltree / 。翻译成java应该不会太困难。

Answer 5

我发现了一个带删除的开源实现，但需要付出一些努力才能使其完全正常运行。

这是一个较大的开源项目 Gephi 的模块，但这里是来源和 javadoc 。如果你想要一个罐子，你可以安装Gephi，它位于：

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

那里的删除方法删除与输入间隔重叠的所有间隔（而不仅仅是输入间隔）。但是我在soruces中发现有私有方法删除特定节点（存储一个间隔）。私有搜索方法也返回节点。

所以我认为通过一些小小的努力，可以重构代码并具有这个 - '删除特定间隔'功能。最快和最脏的方法是将私有方法/ Node类公开。但由于它是一个开源项目，未来它可能会演变为区间树的一些良好的标准实现。