IntervalTree DeleteNode Java实现
-
07-07-2019 - |
题
我需要在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会大大加快速度)。
解决方案
我最终修改了 sun.jvm.hotspot.utilities.IntervalTree
来维护一组已删除的节点。在进行搜索时,我会排除此集合中的所有项目。不理想,但这比获得“真实”要容易得多。删除工作。一旦删除的集合变得太大,我就会重建树。
其他提示
此项目有一个RangeTree实现,可能对您有用。太阳包可能适合快速和肮脏的使用,但我不建议建立任何重要的依赖它们。太阳可能无法保持稳定。
我不知道您的确切要求,但非静态段树可能适合您。如果是这样,请查看布局管理软件,特别是 SegmentTree包。它具有您需要的删除功能。
如果您决定推销自己,我可以建议开源吗?我很惊讶没有一个开放且简单的Interval Tree可用。
基于增强的AVL树的ac#实现@ http://code.google.com/ p / intervaltree / 。翻译成java应该不会太困难。
我发现了一个带删除的开源实现,但需要付出一些努力才能使其完全正常运行。
这是一个较大的开源项目 Gephi 的模块,但这里是来源和 javadoc 。如果你想要一个罐子,你可以安装Gephi,它位于:
/gephi/modules/org-gephi-data-attributes-api.jar
那里的删除方法删除与输入间隔重叠的所有间隔(而不仅仅是输入间隔)。但是我在soruces中发现有私有方法删除特定节点(存储一个间隔)。私有搜索方法也返回节点。
所以我认为通过一些小小的努力,可以重构代码并具有这个 - '删除特定间隔'功能。最快和最脏的方法是将私有方法/ Node类公开。但由于它是一个开源项目,未来它可能会演变为区间树的一些良好的标准实现。