DeleTeNoDE Java实现

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

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

我不知道您的确切要求,但是非静态的段树可能对您有用。如果是,请看一下 Layout Management SW 特别是 SegmentTree package . 它具有您需要的删除功能。

如果你决定自己动手,我可以建议你公开采购吗?我很惊讶现在还没有一个开放的简单的间隔树。

有一个基于扩充的AVL树的C实现@ http://code.google.com/p/intervaltree/ . 翻译到Java不应该太困难。

我发现了一个带有删除功能的开放源码实现,但是它需要一些努力才能使它完全正常工作。

它是一个大型开源项目的模块 Gephi ,但这是 sources 和 javadoc . 如果你想要一个罐子,你可以安装gephi,它在:

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

这里的delete方法删除了与输入间隔重叠的所有间隔(而不仅仅是输入间隔)。不过,我在SORUCE中发现,有一些私有方法可以删除特定的节点(存储一个间隔)。另外,私有搜索方法返回节点。

因此,我认为只要稍加努力,就可以重构代码,并具有“删除特定间隔”功能。最快也是最脏的方法就是将私有方法/节点类公开。但由于它是一个开放源码的项目,将来可能会演变成一些很好的间隔树标准实现。