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

尝试从树中删除节点最终会抛出异常:

节点的最大端点未正确更新

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

目前我只是在擦除树并在每次删除时重新填充它,这远非理想(注意:在RBTree中设置DEBUGGING = false会大大加快速度).

Answer 1

我最终修改了sun.jvm.hotspot.utilities.IntervalTree维护一组已删除的节点.在进行搜索时,我会排除此集合中的所有项目.不理想,但这比"真正的"删除工作容易得多.一旦删除的集合变得太大,我就重建了树.