区间树删除节点的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.
 */

尝试从树中删除节点会导致抛出异常：“节点的最大端点未正确更新”。在sun.jvm.hotspot.utilities.IntervalTree子类中正确实现“delete”功能有多难？或者是否已经有另一个Interval Tree实现正确地实现了这个功能？目前，每次进行删除操作时，我只是清空整个树并重新填充，这远非理想（注意：在RBTree中设置DEBUGGING=false可以极大地提高速度）。

- Sam Barnum

Answer 1

我最终修改了sun.jvm.hotspot.utilities.IntervalTree，以维护一组已删除节点。在搜索时，我排除了此集合中的任何项。虽然不是理想的解决方案，但这比实现“真正”的删除要容易得多。一旦删除集合变得过大，我就会重新构建树。

- Sam Barnum

Answer 2

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

- Yishai

---

谢谢你的链接，Yishai。我正在查看文档 http://olduvai.sourceforge.net/tj/tj-javadoc-public/TreeJuxtaposer/RangeTree.html ，但没有找到获取范围节点列表或修改树的方法。它似乎还有一些依赖泄漏在他们使用的GUI项目上。我猜想这非常特定于该项目的需求，不是通用的 RangeTree。你使用过这个实现吗？ - Sam Barnum

@Sam，不，我没有用过它。这只是我能找到的替代方案。由于它是开源的，可能比子类化sun实现更好地为您提供起点。 - Yishai

Answer 3

我发现了一个带有删除功能的开源实现，但需要一些努力才能使其完全可用。

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

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

在那里的删除方法会删除所有与输入区间重叠的区间（而不仅仅是输入的区间）。然而，我在源代码中发现了一些私有方法，可以删除特定节点（存储一个区间）。此外，私有搜索方法返回节点。

因此，我认为只需花费一点点功夫就可以重构代码并具有“删除特定区间”功能。最快且最简单的方法是将私有方法/节点类公开。但由于这是一个开源项目，也许它未来可以演变成为一种良好标准的区间树实现。

- Marcin

Answer 4

在http://code.google.com/p/intervaltree/上，有一个基于增广AVL树的C#实现。将其翻译为Java应该不太困难。

- cos

Answer 5

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

如果您决定自己开发，请考虑开源。我很惊讶竟然没有一个开放且易用的区间树可用。

- GaryF