我需要 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.
*/
尝试从树中删除节点最终会抛出异常：
节点的最大端点未更新
正确地
困难？或者是否有另一个区间树实现已经正确实现了这一点？
目前，我只是清除树并在每次删除时重新填充它，这远非理想（注意：在 RBTree 中设置 DEBUGGING=false 会极大地加快速度）。
I need an IntervalTree or RangeTree implementation in Java, and am having trouble finding one with working deletion support.
There's a built-in one at sun.jvm.hotspot.utilities.IntervalTree, but the deleteNode method in the RBTree superclass states:
/**
* 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.
*/
Trying to delete nodes from a tree ends up throwing the exception:
Node's max endpoint was not updated
properly
How difficult would it be to properly implement delete functionality in a subclass of the sun.jvm.hotspot.utilities.IntervalTree? Or is there another Interval Tree implementation which already implements this correctly?
Currently I'm just wiping out the tree and re-populating it every time there's a deletion, which is far from ideal (note: setting DEBUGGING=false in the RBTree sped things up tremendously).
发布评论
评论（5）
我最终修改了
sun.jvm.hotspot.utilities.IntervalTree以维护一组已删除的节点。进行搜索时，我会排除该集中的任何项目。并不理想，但这比“真正的”删除工作要容易得多。一旦删除的集合变得太大，我就会重建树。I ended up modifying the
sun.jvm.hotspot.utilities.IntervalTreeto maintain a Set of deleted nodes. When doing a search, I exclude any items in this set. Not ideal, but this was a lot easier than getting "real" deletion working. Once the deleted set gets too large, I rebuild the tree.此项目有一个 RangeTree 实现，可能对您更有用。 sun 包可能适合快速而肮脏的使用，但我不建议依赖它们构建任何重要的东西。阳光可能无法使它们保持稳定。
This project has a RangeTree implementation that might be of more use to you. The sun packages might be ok for quick-and-dirty use, but I would not recommend building anything important relying on them. Sun may not keep them stable.
我不知道您的确切要求，但非静态线段树可能适合您。如果是这样，请查看布局管理软件，特别是SegmentTree包。它具有您需要的删除功能。
如果您决定自己推出，我可以建议将其开源吗？我很惊讶还没有一个开放且简单的区间树可用。
I don't know your exact requirements but a non-static Segment Tree might work for you. If so, have a look at Layout Management SW, specifically the SegmentTree package. It has the remove feature you need.
If you decide to roll your own, might I suggest open sourcing it? I'm surprised there isn't an open and easy Interval Tree available already.
有基于增强 AVL 树的 ac# 实现 @ http://code.google.com/p/intervaltree / 。翻译成java应该不会太困难。
there's a c# implementation based on an augmented AVL tree @ http://code.google.com/p/intervaltree/ . translation to java shouldn't be too difficult.
我找到了一个带有删除功能的开源实现，但需要一些努力才能使其完全发挥作用。
它是大型开源项目 Gephi 的一个模块，但这里有 来源 和 javadoc。如果你想要一个 jar，你可以安装 Gephi，它位于：
那里的删除方法，删除与输入间隔重叠的所有间隔（而不仅仅是输入间隔）。但是我在源中发现有一些私有方法可以删除特定节点（存储一个间隔）。私有搜索方法也返回节点。
因此，我认为只需付出一些努力，就可以重构代码并拥有“删除特定间隔”功能。最快和最肮脏的方法是将私有方法/Node 类公开。但由于它是一个开源项目，也许它将来可能会发展成为区间树的一些良好的标准实现。
I found an open-source implementation with deletion, but it neeeds some effort to make it fully functional.
It's a module of larger open-source project Gephi, but here are the sources and javadoc. If you want a jar you can install the Gephi, and it's in:
The delete method there, removes all intervals overlapping with the input interval (instead of just the input one). However I found in the soruces that there are private methods that remove a specific node (which stores one interval). Also the private search methods return nodes.
So I think with some little effort it's possible to refactor the code and have this - 'delete specific interval' feature. The fastest and most dirty way would be to just make the private methods/Node class public. But since it's an open source project, maybe it could evolve in future into some good standard implementation of interval tree.