java - IntervalTree DeleteNode Java实现

Question

我需要一个 IntervalTree或 Java 中的 RangeTree 实现，但很难找到具有有效删除支持的实现。

在 sun.jvm.hotspot.utilities.IntervalTree 处有一个内置的，但是 deleteNode RBTree 父类(super class)中的方法声明:

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

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

Node's max endpoint was not updated properly

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

目前我只是清除树并在每次删除时重新填充它，这远非理想(注意:在 RBTree 中设置 DEBUGGING=false 可以极大地加快速度)。

Answer 1

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