IntervalTree DeleteNode Java实现

我需要在Java中使用IntervalTree或RangeTree实现，并且无法找到具有工作删除支持的实现。IntervalTree DeleteNode Java实现

有一个内置的一个在sun.jvm.hotspot.utilities.IntervalTree，但deleteNode方法在RBTree超指出：

/** 
* 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. 
*/

试图从树上最终抛出异常，就删除节点：

节点的最大终点没有更新正确

如何让pr在sun.jvm.hotspot.utilities.IntervalTree的子类中正确执行delete功能？或者是否有另一个Interval Tree实现已经正确实现了这个？

目前我只是在清除树并重新填充每次删除时，这是非常不理想的（注意：在RBTree中设置DEBUGGING = false会大大提高速度）。

来源

2009-09-13 Sam Barnum

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

来源

2009-10-01 14:43:21

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

来源

2009-09-13 18:55:32 Yishai

感谢您的链接，Yishai。我正在看文档http://olduvai.sourceforge.net/tj/tj-javadoc-public/TreeJuxtaposer/RangeTree.html，并没有看到任何方式来获取一个范围的节点列表，或修改树一旦创建。它也看起来像他们使用它的GUI项目有一些依赖泄漏。我的猜测是这个项目的需求非常具体，而不是一个通用的RangeTree。你有没有使用这个实现？ –

@Sam，不，我没有用过它。这只是我能找到的替代方案。由于它是开源的，它可能会给你一个更好的基础，而不是子类化太阳实现。 – Yishai

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

如果您决定推出自己的产品，我是否可以建议开源？我很惊讶没有一个开放和容易的间隔树已经可用。

来源

2009-09-14 12:43:35 GaryF

有一个基于增强AVL树@http://code.google.com/p/intervaltree/的c＃实现。翻译到Java应该不是太难。

来源

2012-07-24 23:43:06 cos

我发现了一个开源的实现与删除，但它需要一些努力，使其功能齐全。

这是一个较大的开源项目Gephi的模块，但这里是sources和javadoc。如果你愿意，你可以安装一个Gephi罐子，这是在：

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

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

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

来源

2012-08-11 19:12:51 Marcin

IntervalTree DeleteNode Java实现

回答

相关问题