java - IntervalTree DeleteNode Java 实现

Question

我需要一个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.
 */

尝试从树中删除节点最终会引发异常：

节点的最大端点未正确更新

delete在 sun.jvm.hotspot.utilities.IntervalTree 的子类中正确实现功能有多难？或者是否有另一个已经正确实现的间隔树实现？

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

score 5 · Accepted Answer

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

score 1 · Accepted Answer

这个项目有一个 RangeTree 实现，可能对你更有用。sun 包可能适合快速和肮脏的使用，但我不建议依赖它们构建任何重要的东西。Sun 可能无法让它们保持稳定。

score 0 · Accepted Answer

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

如果你决定自己动手，我可以建议开源吗？我很惊讶没有可用的开放且简单的间隔树。

score 0 · Accepted Answer

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

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

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

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

所以我认为只需一点点努力就可以重构代码并拥有这个 - '删除特定间隔'功能。最快和最肮脏的方法是只公开私有方法/节点类。但是由于它是一个开源项目，也许它将来会演变成一些好的间隔树的标准实现。

score 0 · Accepted Answer

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

java - IntervalTree DeleteNode Java 实现

5 回答 5

Related

Reference